Title: When and Why is Persuasion Hard? A Computational Complexity Result Show Chinese title

Title: 当说服为何困难？ 一种计算复杂性结果

Abstract: As generative foundation models improve, they also tend to become more persuasive, raising concerns that AI automation will enable governments, firms, and other actors to manipulate beliefs with unprecedented scale and effectiveness at virtually no cost. The full economic and social ramifications of this trend have been difficult to foresee, however, given that we currently lack a complete theoretical understanding of why persuasion is costly for human labor to produce in the first place. This paper places human and AI agents on a common conceptual footing by formalizing informational persuasion as a mathematical decision problem and characterizing its computational complexity. A novel proof establishes that persuasive messages are challenging to discover (NP-Hard) but easy to adopt if supplied by others (NP). This asymmetry helps explain why people are susceptible to persuasion, even in contexts where all relevant information is publicly available. The result also illuminates why litigation, strategic communication, and other persuasion-oriented activities have historically been so human capital intensive, and it provides a new theoretical basis for studying how AI will impact various industries. Show Chinese abstract

Abstract: 随着生成基础模型的进步，它们也倾向于变得更加具有说服力，这引发了担忧，即人工智能自动化将使政府、公司和其他行为者以空前的规模和效果几乎无需成本地操纵信念。 这一趋势的全部经济和社会影响一直难以预见，然而，因为我们目前缺乏对为什么说服对于人类劳动来说本身是昂贵的完整理论理解。 本文通过将人类和AI代理置于共同的概念基础上，将信息说服形式化为一个数学决策问题，并对其计算复杂性进行描述。 一项新的证明表明，有说服力的信息难以发现（NP难），但如果由他人提供，则容易采用（NP）。 这种不对称性有助于解释为什么人们容易受到说服，即使在所有相关信息都公开可用的情况下也是如此。 这一结果还阐明了为什么诉讼、战略沟通和其他以说服为导向的活动历史上如此依赖人力资本，并为研究人工智能如何影响各个行业提供了新的理论基础。