"Algorithmic Bayesian Persuasion"
Shaddin Dughmi
(University of Southern California)
Monday, May 4th, 2015, 2:00 pm
EBU3B, Room 4258
Abstract:
We consider the Bayesian Persuasion problem, as formalized by Kamenica and Gentzkow, from an algorithmic perspective in the presence of high dimensional and combinatorial uncertainty. Specifically, one player (the receiver ) must take one of a number of actions with a-priori unknown payoff; another player (the sender ) is privy 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 would like to do so as to maximize her own payoff in expectation assuming that the receiver rationally acts to maximize his own payoff. This models a number of natural strategic interactions, in domains as diverse as e-commerce, advertising, politics, law, security, finance, and others. When the payoffs of various actions follow a joint distribution (the common prior), the sender’s problem is nontrivial, and its complexity depends on the representation of the prior.
Assuming a Bayesian receiver, we study the sender’s problem with an algorithmic and approximation lens. 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. For the latter result, our algorithm decouples the signaling problem for the different actions and signals independently for each. This decoupling drives a larger, conceptual point: collaborative persuasion by multiple parties (the senders) is a parallelizable task, requiring no coordination when actions are identical and independent and only an approximate solution is sought. We leave open the intriguing question of whether either of these two results extends to independent yet not necessarily identical payoff distributions.
We then turn our attention to the general problem, and consider distributions over action payoffs given by a sampling oracle. Somewhat surprisingly, we show that even in this 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.