Shaddin Dughmi: Algorithmic Bayesian Persuasion

Persuasion is intrinsic to many human endeavors. For example, merchants persuade customers through advertising campaigns which selectively highlight a product's positive attributes and obscure its defects, lawyers persuade judges and juries through oral arguments which selectively highlight some pieces of evidence and downplay others, and political candidates persuade voters by framing the debate on issues of the day in order to further their political aspirations. In all these cases, and many others, persuasion can be viewed as the act of exploiting an informational advantage in order to effect change in the decisions of others through communication. For such communication to  be credible, and hence persuasive, it must be grounded in truth, and yet it may cherry-pick the truths revealed while obscuring others.

 

The ubiquity of persuasive communication has spawned a vast literature concerned with understanding and exploring the space of information structures in strategic interactions. Perhaps no model is more basic and fundamental than the 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. The sender, on the other hand, has access to additional information regarding the payoffs of the various actions for both players. The sender can commit to revealing a noisy signal regarding the realization of the payoffs of various actions, and in doing so would like to maximize her payoff in expectation assuming that the receiver rationally acts to maximize his own payoff. 

 

This paper studies the optimization task facing the sender, that of designing a near optimal signaling scheme, from an algorithmic perspective. Despite being the fundamental building block for the study of signaling in strategic settings, the Bayesian Persuasion problem has not been examined algorithmically prior to our work. A-priori, it is unclear whether the sender's optimal signaling strategy can be succinctly represented, let alone efficiently computed. Somewhat surprisingly, we nevertheless discover that optimal or near optimal signaling schemes can be computed efficiently --- in time polynomial in the number of actions --- under fairly general conditions. We consider two models: one in which action payoffs are i.i.d from an explicitly-described marginal distribution, and another in which the joint distribution of action payoffs is arbitrary and given by a black-box sampling oracle.  

 

We show two results for the case in which the payoffs of different actions are i.i.d and given explicitly: a polynomial-time (exact) algorithmic solution, and a “simple” (1 − 1/e) approximation algorithm. Both results hinge on a “symmetry characterization” of the optimal signaling scheme. The former result also involves a connection to auction theory, and in particular to Border’s characterization of the space of feasible reduced-form auctions. We then consider general distributions given by a black-box sampling oracle. We show that, even in this very general setting, the persuasion problem admits a fully polynomial-time approximation scheme (FPTAS) in a bi-criteria sense. As our main technical tool to prove this theorem, we study the algorithmics of a natural and abstract question on vector spaces, which we term dispersion testing: Given two distributions A and B supported on a finite-dimensional vector space, decide whether A is a mean-preserving spread of B, and if so compute the inverse of the associated spreading map. We employ tools from convex optimization and optimal transport theory to design an approximate test for the dispersion testing problem, and relate the persuasion problem to dispersion testing via a randomized Turing reduction employing the Ellipsoid method.

 

Paper: http://www-bcf.usc.edu/~shaddin/papers/abp.pdf

 

This is joint work with Haifeng Xu.