When and Why is Persuasion Hard? A Computational Complexity Result

Advocates argue that artificial intelligence will simultaneously accelerate the pace of scientific discovery and make existing knowledge more accessible (e.g., by translating medical information into people’s native languages; Vieira et al., 2021). However, the generality of artificial intelligence raises dual-use concerns: similar to how a predictive model intended to avoid drug toxicity can be “inverted” to increase the potency of chemical weapons (Urbina et al., 2022), systems that are capable of explanation and creativity will also generally be potent instruments of manipulation and disinformation. A comprehensive assessment of the technology requires that we anticipate both its potential epistemic costs and benefits, ideally maximizing the latter while minimizing the former.

Recent work has demonstrated that large language models are highly effective at persuading people across a variety of tasks and domains (Matz et al., 2024; Durmus et al., 2024; Burtell and Woodside, 2023; Shin and Kim, 2023; Ahn et al., 2021; Karinshak et al., 2023; Carrasco-Farre, 2024; Breum et al., 2023), raising concerns about their potential use for widespread misinformation, manipulation, and deception (Allen and Weyl, 2024; Kreps et al., 2022; Zellers et al., 2019). These concerns are especially acute for people whose identifiable characteristics—such as race, gender, or sexual identity—subject them to higher rates of algorithmic persuasion and bias (Bar-Gill et al., 2023; Speicher et al., 2018; Hannak et al., 2014; Mikians et al., 2012).

Large language models and other innovations have significantly enhanced the persuasive capacities of machines in recent years, but humans have been refining their powers of persuasion since antiquity (Aristotle’s Rhetoric dates from the 4th century BCE). The large-scale manufacture of persuasion is, perhaps unsurprisingly, a well-developed fixture of modern economies. One frequently-cited estimate holds that “one-quarter of GDP is persuasion” (McCloskey and Klamer, 1995): law, advertising, politics, science, public relations, and many other professions revolve—in whole or in part—around changing other people’s minds. The advent of targeted digital advertising has, moreover, expanded the specificity and scope of persuasion (Wu, 2017; Zuboff, 2019).

The economics of persuasion raise three important questions: (1) what does persuasion accomplish to justify such enormous expenditures; (2) why has persuasion historically commanded so much brain power; and (3) how will AI automation reshape persuasion and, with it, the broader epistemic landscape of society?

A variety of authors have advanced theories of the benefits of persuasion—i.e., what persuaders can achieve in various circumstances (e.g., Milgrom and Roberts, 1986; Grossman and Hart, 1980; Crawford and Sobel, 1982; Kamenica and Gentzkow, 2011; Schwartzstein and Sunderam, 2021; Aina, 2021). Relatively few, however, have focused on the cost of generating persuasive messages. In practice, such costs play an important role in determining when, where, and how persuasion takes place. The purpose of this paper is to formally establish a key driver of these costs—namely, the computational resources (natural or artificial) required to generate persuasive messages.

Given a suitable formalization of the persuasion problem, computational complexity theory can be used to characterize its production function. This approach has previously been applied to explain a variety of economic and social phenomena, such as incomplete uptake of public information (Aragones et al., 2005), slow convergence to Nash equilibrium (Daskalakis et al., 2009), narrow choice bracketing (Camara, 2022), and persistent market inefficiencies (Spear, 1989). Closest to the present paper is that of Dughmi and Xu (2016), who characterize the complexity of the model introduced by Kamenica and Gentzkow (2011).

“1.11 The world is determined by the facts, and by these being all the facts.” (emphasis added)

—Ludwig Wittgenstein, 1922

The present paper studies informational persuasion: the selective disclosure of private information or the use of models (narratives, stories, etc.) to “frame” public information with the intention of increasing a counter-party’s belief in a focal claim. This formalization of persuasion is highly general in that it assumes little structure beyond the standard probability axioms and naturally captures a wide variety of applications. It can be cast as a formal decision problem as follows.

Although some instances of data withholding are nefarious (e.g., a scientist omitting disconfirmatory evidence from their report), attention and other constraints mean that informational persuasion is a normalized feature of many interactions (e.g., “please submit no more than three letters of recommendation”). The use of models (narratives, stories, etc.) to characterize publicly available information is a frequent practice among lawyers, politicians, academics, and other professional persuaders, as has been documented extensively elsewhere (Shiller, 2017; Spiegler, 2016; Eliaz and Spiegler, 2020; Roos and Reccius, 2021; Andre et al., 2023; Bénabou et al., 2018; Graeber et al., 2024). Informational persuasion is isomorphic to the following problem, which asks whether a model can be used to “frame” public information (see, e.g., Schwartzstein and Sunderam, 2021).

Our main result, Theorem 1, shows that informational persuasion is NP-Complete. Problems in this complexity class share two principle features: proposed solutions can be quickly verified but they cannot, in general, be quickly discovered.¹¹1The idea that this class of problems cannot be solved quickly (i.e., in polynomial time) is the famous $P\neq NP$ conjecture. Although open, it is widely believed to be true among computer scientists (Gasarch, 2019) on account of how strange the implications of its converse would be, among other reasons (Aaronson, 2016). Informational persuasion is therefore structurally similar to mathematical proof in the sense that solutions are categorically easier to check than to construct. Indeed, proving theorems in an axiomatic system such as Zermelo-Frankel is likewise NP-Complete, which implies that a fast algorithm for informational persuasion, were it to exist, could be be used to quickly prove arbitrary theorems, and vice-versa.

A central puzzles in the persuasion literature is why people are susceptible to persuasion in the first place, especially in contexts where all information is publicly available? More specifically, why do people accept externally supplied persuasion rather than coming up with their own models, narratives, and stories?

Many existing theories do not address this question, but rather directly assume that people are persuadable. The proof of Theorem 1 provides some indication of why this might be the case. The essential insight is that, in unrestricted inferential contexts, each new fact casts every other fact in a new light, shifting the credence it lends to the focal event. Translating this idea into Kolmogorov’s set-theoretic model of probability theory reveals that informational persuasion is, in the worst case, a highly non-convex optimization problem.

Let $(\Omega,\mathcal{G},\pi)$ be a probability space. We study communication between a sender $s$ and receiver $r$. The sender has access to a collection of private facts $\mathcal{F}=\{F_{1},F_{2},\dots,F_{N}\}$ for $N\in\mathbb{N}$, each of which is a subset of $\Omega$. The sender selectively reports a subset of the facts $\mathcal{R}\subseteq\mathcal{F}$ to the receiver. The receiver updates beliefs on the basis of the newly reported facts.

There is a focal event $E\subseteq\Omega$. The sender is concerned with maximizing the receiver’s posterior belief in $E$. Let $\pi(\cdot|\mathcal{R})$ denote the sender’s expectation of the receiver’s posterior conditional on a report $\mathcal{R}$.

Rational theories of belief formation (such as those typically assumed in statistical decision theory and economics) assume that people instantaneously update their internal state of belief to reflect the sum total of information they possess.²²2Attention is generally conceived of as a “bottleneck” interposed between an economic agent and the external world (Loewenstein and Wojtowicz, 2023). Even models which incorporate attentional frictions typically assume that people update instantaneously once information makes it through the bottleneck, however. The ramifications of even readily available information are not always apparent, however: it takes time to notice patterns, generate good explanations, rule out bad explanations, separate signal from noise, and generally transform the “raw material” of information into the “finished products” of knowledge and understanding.

Characterizing the computational complexity of informational persuasion directly informs our understanding of this process by characterizing the production technology of informational persuasion. Theorem 1 shows that the computational resource cost of informational persuasion can, in the worst case, grow exponentially in the number of facts considered. This helps explain why industries centered around persuasion, such as those identified by (McCloskey and Klamer, 1995), are human-capital intensive. It also informs conversations about how artificial intelligence, social media, and other information technologies will impact our shared “epistemic commons.”

Not all persuasion problems are equally difficult, however. There are clearly situations where it is easy to “cherry-pick” examples to support a particular conclusion—for example, if each “fact” is a Gaussian draw and the focal belief is a one-tailed hypothesis test concerning the distribution’s mean. Although left to future work, the present approach frames informational persuasion directly in terms of the Kolmogorov probability axioms, and therefore naturally bridges persuasion with statistical theory. The simplicity of persuasion in the above example, for example, follows directly from statistical sufficiency.