Source-linked AI summary
Algorithmic Bayesian Persuasion
Shaddin Dughmi, Haifeng Xu
TL;DR
The paper studies the computational complexity of optimizing Bayesian persuasion under three ways of representing action-payoff distributions. It obtains efficient algorithms for i.i.d. and black-box settings, but proves exact computation is #P-hard for independent non-identical actions and that black-box approximation trade-offs are information-theoretically unavoidable.
Problem
The paper asks how computationally tractable optimal Bayesian persuasion is under different representations of the prior distribution over states of nature.
Method
The paper analyzes direct signaling schemes across i.i.d., independent non-identical, and general black-box distribution models, drawing connections to auction-theoretic reduced forms.
Results
The paper gives a polynomial-time exact algorithm and a (1-1/e)-approximation for i.i.d. actions, proves #P-hardness for independent non-identical actions, and gives a black-box FPTAS with bicriteria guarantees.
Takeaways & Limitations
Persuasion complexity depends sharply on how the prior is presented: auction-theoretic structure enables efficient i.i.d. solutions, while non-identical and black-box settings impose computational or information-theoretic barriers.
Takeaways & Limitations
In the black-box model, no algorithm can approach optimality while maintaining incentive compatibility without a significant trade-off between the two guarantees.
Abstract
from arXiv · showhide
Persuasion, defined as the act of exploiting an informational advantage in order to effect the decisions of others, is ubiquitous. Indeed, persuasive communication has been estimated to account for almost a third of all economic activity in the US. This paper examines persuasion through a computational lens, focusing on what is perhaps the most basic and fundamental model in this space: the celebrated Bayesian persuasion model of Kamenica and Gentzkow. Here there are two players, a sender and a receiver. The receiver must take one of a number of actions with a-priori unknown payoff, and the sender has access to additional information regarding the payoffs. The sender can commit to revealing a noisy signal regarding the realization of the payoffs of various actions, and would like to do so as to maximize her own payoff assuming a perfectly rational receiver. We examine the sender's optimization task in three of the most natural input models for this problem, and essentially pin down its computational complexity in each. When the payoff distributions of the different actions are i.i.d. and given explicitly, we exhibit a polynomial-time (exact) algorithm, and a "simple" $(1-1/e)$-approximation algorithm. Our optimal scheme for the i.i.d. setting involves an analogy to auction theory, and makes use of Border's characterization of the space of reduced-forms for single-item auctions. When action payoffs are independent but non-identical with marginal distributions given explicitly, we show that it is #P-hard to compute the optimal expected sender utility. Finally, we consider a general (possibly correlated) joint distribution of action payoffs presented by a black box sampling oracle, and exhibit a fully polynomial-time approximation scheme (FPTAS) with a bi-criteria guarantee. We show that this result is the best possible in the black-box model for information-theoretic reasons.
1 Introduction
The paper studies the computational complexity of Bayesian persuasion, where an informed sender commits to signaling schemes that influence a rational receiver's action. Across three input models, it identifies efficient algorithms, hardness barriers, and information-theoretic limits.
- Model: Bayesian persuasion models an informed sender who commits to partially revealing the state of nature before a receiver chooses among actions.The sender designs the signaling policy to favor her payoff, while the receiver accounts for the policy when acting.
- Computational perspective: The paper analyzes optimal and near-optimal persuasion under i.i.d., independent non-identical, and general black-box payoff distributions.The input model determines how the prior distribution is represented and therefore affects computational complexity.
- i.i.d. actions: In the i.i.d. setting, the paper gives a polynomial-time exact algorithm and a simple polynomial-time (1-1/e)-approximation scheme.The simple scheme independently signals for each action, while the optimal scheme connects persuasion to Border’s characterization for single-item auctions.
- Independent non-identical actions: For independent non-identical actions, exactly computing the optimal expected sender utility is #P-hard, ruling out Border-theorem-like approaches unless the polynomial hierarchy collapses.The paper shows that the auction analogy does not generalize to this setting.
- Black-box distributions: For general distributions accessed through a black-box sampling oracle, the paper provides an FPTAS with additive ε losses in sender utility and incentive compatibility.The accompanying negative result says this bi-criteria loss is essentially unavoidable for information-theoretic reasons.
- Broader contribution: The paper presents connections between persuasion and auction design while showing that those connections can yield both positive algorithms and negative complexity results.These connections are treated as one of the paper’s contributions.
2 Preliminaries
The preliminaries formalize Bayesian persuasion as a signaling problem over states of nature, with receiver incentives evaluated after Bayesian updating. They define sender utility, direct schemes, and approximate incentive compatibility.
- Game and payoffs: A persuasion game has a sender and receiver, with state-dependent payoff vectors s(θ) and r(θ) over n actions.The state θ is drawn from a prior, and each player’s payoff depends on the selected action and realized state.
- Signaling schemes: The sender commits to a possibly randomized signaling scheme ϕ that maps each state of nature to signals.The receiver observes the signal before choosing an action.
- Receiver response: After observing a signal, the receiver updates beliefs and chooses an action maximizing expected receiver payoff, with ties broken in favor of the sender.The resulting action determines the sender’s expected utility under that signal.
- Optimization and direct schemes: The sender optimizes expected utility, and an optimal scheme can be represented using at most n direct signals, one recommending each action.A direct scheme must make the recommended action at least as attractive as every alternative for the receiver.
- Approximate incentives: An ε-incentive-compatible scheme allows the recommended action to fall within ε of the receiver’s best expected payoff.The paper evaluates such a scheme against the best exactly incentive-compatible scheme in a bi-criteria sense.
- Distribution dependence: Expected utility, incentive compatibility, and optimality are defined relative to the prior distribution over states of nature.The same signaling scheme may therefore have different properties under different input distributions.
3 Persuasion with I.I.D. Actions
For i.i.d. action payoffs with explicit distributions, optimal persuasion admits a symmetric formulation that can be solved exactly in polynomial time, while independent signaling gives a polynomial-time (1−1/e)-approximation.
- Computational setup: The i.i.d. model has exponentially many states and a natural linear program, but the goal is an efficient oracle implementing a signaling scheme.The algorithmic running time is polynomial in the number of actions and types rather than the explicit state space.
- Symmetry reduction: An optimal incentive-compatible scheme can be chosen symmetric, reducing each signal to two posterior type distributions: one for the recommended action and one for all others.Symmetric schemes send each signal with equal probability and are represented by an s-signature (x, y).
- Symmetry reduction: The reduced optimization maximizes nξ · x subject to ρ · x ≥ ρ · y and realizability of the symmetric signature.The realizability constraints also enforce ||x||1 = ||y||1 = 1 and x + (n−1)y = q.
- Auction-theoretic algorithm: Auction theory supplies the key computational connection: symmetric signaling signatures correspond to symmetric reduced forms of single-item auctions with i.i.d. bidders.This correspondence enables the Ellipsoid method and polynomial-time implementation of the optimal scheme.
- Approximation scheme: (1−1/e) is achieved by a polynomial-time scheme that signals independently for each action when payoffs are nonnegative.Despite potentially correlated posterior beliefs under the optimum, independent signaling supports approximate persuasion and can be parallelized across multiple senders.
4 Complexity Barriers to Persuasion with Independent Actions
For independent but non-identically distributed actions, the auction-theoretic tractability of the i.i.d. case breaks down: computing optimal expected sender utility is #P-hard.
- Model: With explicit action-specific marginal distributions, the problem gives each action its own finite distribution and sender payoff values.This is the independent non-identical setting, contrasting with the common marginal distribution used for i.i.d. actions.
- Complexity result: #P-hardness holds for computing the optimal expected sender utility in the independent non-identical setting.The hardness result applies when action payoff distributions are given explicitly.
- Implication: The hardness result rules out a generalized Border theorem for this persuasion setting unless the polynomial hierarchy collapses to P^NP.The authors interpret this separation as illustrating differences between persuasion and mechanism design.
- Proof strategy: The proof reduces from computing the Khintchine constant, using a Khintchine-like persuasion instance with i.i.d. actions and two action types.The constructed instance uses a state drawn uniformly from {−1,+1}^n, with entries specifying action types.
- Proof strategy: The reduction encodes signatures through a special action, two signals, and carefully chosen parameters that force optimal schemes to realize the tested signature.A sufficiently small positive ε prevents sacrificing utility from one signal to gain utility from the special action.
5 The General Persuasion Problem
For correlated action payoffs given by a black-box sampling oracle, the paper develops an FPTAS with additive losses in sender utility and incentive compatibility, and proves that this bicriteria trade-off is information-theoretically necessary.
- Problem setting: The black-box model permits arbitrary correlation among action payoffs, with the joint distribution supplied by a sampling oracle.Payoffs are normalized to a bounded interval.
- Positive result: The scheme loses an additive ǫ in both expected sender utility and incentive compatibility.The expected sender utility equals the expected optimal value of the sampled linear program, which is within ǫ of OPT under the stated sample-size condition.
- Positive result: An ǫ-incentive compatible signaling scheme is implemented in polynomial time, with approximate sender optimality guaranteed by the empirical linear program.The construction uses K = poly(n, 1/ǫ) samples and relaxed incentive-compatibility constraints.
- Algorithm: The algorithm samples prior states, augments them with the input state, and solves a linear program for an empirical signaling scheme.It then applies the resulting scheme to the input state rather than explicitly representing the entire signaling scheme.
- Connections: The black-box result is related to reduced-form mechanism-design methods but uses a single sampled linear program instead of the ellipsoid method.The approach is presented as simpler and more efficient than the cited alternative framework.
B.1 Symmetry of the Optimal Scheme (Theorem 3.2)
With i.i.d. action payoffs, permuting an optimal signaling scheme preserves feasibility, incentive compatibility, and sender utility; convex combinations of optimal incentive-compatible schemes retain those properties.
- Permutation closure: Permuting the signature of a signaling scheme produces a realizable permuted scheme under i.i.d. action payoffs.The transformed scheme maps permuted states and signals according to the same action permutation.
- Permutation closure: If the original scheme is incentive compatible and optimal, its permutation is also incentive compatible and optimal.The sender’s utility is unchanged by the permutation.
- Convexity: Convexly mixing two signaling schemes corresponds to randomly selecting one scheme with the mixture probability on each input state.The resulting signature is the componentwise convex combination of the two signatures.
- Convexity: A convex combination of optimal incentive-compatible schemes remains optimal and incentive compatible because the underlying optimization has a convex feasible set.This closure property follows from the linear-program formulation.
Proof of Theorem 3.2
The proof symmetrizes any optimal incentive-compatible signaling scheme by averaging over permutations, preserving optimality while making the scheme symmetric.
- Permuting an optimal scheme’s signature yields another optimal incentive-compatible scheme.The permuted scheme is denoted ϕπ.
- A uniformly random permutation followed by signaling according to the permuted scheme remains optimal and incentive compatible.
- The resulting signature is symmetric because permutation averaging makes the relevant quantities independent of the action indices.
- The constructed signature therefore describes an optimal, incentive-compatible, symmetric scheme with s-signature (x, y).
Proof of Lemma 3.5
The proof connects symmetric signaling schemes to symmetric reduced forms in single-item auctions, then uses this correspondence and an efficient separation oracle to compute the optimum.
- A symmetric signaling scheme’s s-signature can be interpreted as the reduced form of an allocation rule.Action types correspond to bidder types, signals correspond to assigning the item, and Bayes’ rule gives the reduced-form probabilities.
- Conversely, an allocation rule with symmetric reduced form induces a signaling scheme, which can be symmetrized by randomly permuting actions.
- The sender’s optimization reduces to a linear program over symmetric reduced forms with constraints ρ · x ≥ ρ · y, x + (n −1)y = q, and ||x||1 = 1.
- An efficient separation oracle for realizable symmetric reduced forms enables solving the linear program in polynomial time.The ellipsoid method gives runtime polynomial in n and m.
- A binary HIGH/LOW signaling scheme recommends a HIGH action whenever one exists, yielding at least a 1 −1/e fraction of the optimal LP value.The guarantee uses independent component signals and nonnegative payoffs.
C Proof of Theorem 4.1
The proof establishes #P-hardness by reducing Khintchine-polytope optimization to optimal sender-utility computation for persuasion with independent actions.
- The reduction proceeds through a Khintchine polytope whose linear optimization problem captures the Khintchine constant.Membership in this polytope is then connected to a carefully constructed persuasion instance.
- The Khintchine constant K(a) is represented by a two-signal persuasion scheme whose signals correspond to the sign of θ · a.Evaluating the associated linear program on the scheme’s signature gives Eθ[|θ · a|].
- The reverse inequality shows that every feasible two-signal signature has objective value at most K(a), completing the equivalence.
- Linear optimization over the realizable-signature polytope for i.i.d. persuasion is #P-hard even with m = 2 action types.
- This contrasts with i.i.d. single-item auctions, where Border’s theorem provides a polynomial-time separation oracle for the analogous reduced-form polytope.
Reduction
The reduction encodes Khintchine-polytope membership into a persuasion instance with one special action and regular zero-sum actions, forcing optimal schemes into a two-signal form.
- Reduction: The constructed instance has one special action with deterministic sender utility ǫ and n regular actions whose parameters encode the input vector.
- Reduction: The reduction’s goal is to determine Khintchine-polytope membership from the optimal sender utility of this instance.
- Reduction: The input vector parametrizes feasible two-signal signatures, with the two signal matrices constrained by the prior distribution.
- Reduction: Parameters a_i and b_i are chosen by solving two equations for each x_i, with boundary cases handled separately.
- Reduction: The construction preserves equal prior expected receiver utility across regular actions and makes both utility parameters nonzero.
- Reduction: An optimal incentive-compatible scheme uses at most two signals: one recommending the special action and one recommending a regular action.Merging all regular-action signals does not decrease sender utility.
- Reduction: The negative signal contributes at most −1/2 to sender utility, with equality forcing zero expected utility for every regular action under the positive signal.
- Reduction: The constructed linear program differs from its comparison program only by the additive pǫ term in the objective.
D Omitted Proofs from Section 5
Conditioning on the empirical sample makes the input state uniformly distributed among sampled states, allowing the LP solution to establish approximate incentive compatibility and sender utility by linearity of expectations.
- Conditioned on the empirical sample eλ, the input state θ is uniformly distributed among the sampled states.
- The LP solution eϕ is ε-incentive compatible for the empirical distribution eλ.
- Removing conditioning and applying linearity of expectations establishes that ϕ is ε-incentive compatible for λ.
- Conditioned sender utility equals the empirical average of eϕ’s sender utility across sampled states.
Proof of Lemma 5.4
The proof constructs a near-optimal scheme whose signals are either sufficiently frequent or receiver-optimal, then shows sampling approximately preserves incentive compatibility and sender utility.
- Sampling preserves honest-signal constraints exactly, while tail bounds and a union bound approximately preserve large-signal constraints.
- There exists an incentive-compatible scheme bϕ with sender utility at least OPT − ε/2, using only large or honest signals.
- Small signals are replaced with honest recommendations, preserving incentive compatibility while losing at most ε/4 in sender utility.
- The expected optimal value of LP (4) is at least OPT − ε.
Impossibility of Incentive Compatibility (Proof of Theorem 5.5 (a))
A black-box algorithm that remains incentive compatible and near-optimal would distinguish two nearly identical distributions, requiring many samples as their statistical distance shrinks.
- For the rainy distribution λr, incentive compatibility forces the scheme to recommend driving, yielding sender utility 0.
- For λs, always recommending walking is incentive compatible and yields sender utility 1.
- A c-optimal, incentive-compatible algorithm must therefore behave differently on λr and λs with constant probability.
- Because the distributions have total variation distance O(δ), distinguishing them requires Ω(1/δ) samples.
- Since δ can be arbitrarily small, the worst-case sample complexity is unbounded as a function of fixed accuracy parameters.
Impossibility of Optimality (Proof of Theorem 5.5 (b))
The proof shows that matching optimal sender utility under approximate incentive compatibility requires distinguishing distributions that differ only slightly, forcing sample complexity proportional to the inverse statistical distance.
- Under λ′, the optimal incentive-compatible scheme achieves sender utility 3δ by recommending action 3 in selected states.
- To match this utility with constant incentive compatibility, the scheme must recommend action 3 on θ2 with constant probability μ > 0.
- Under λ, approximate incentive compatibility prevents the scheme from recommending action 3.
- The contrasting recommendations distinguish λ from λ′ with constant probability, so sample complexity is Ω(1/δ).