On the Tractability of Public Persuasion with No Externalities

Persuasion studies how a principal can influence agents' decisions via strategic information revelation — often described as a signaling scheme — in order to yield the most desirable equilibrium outcome. A basic question that has attracted much recent attention is how to compute the optimal public signaling scheme, a.k.a., public persuasion, which is motivated by various applications including auction design, routing, voting, marketing, queuing, etc. Unfortunately, most algorithmic studies in this space exhibit quite negative results and are rifle with computational intractability. Given such background, this paper seeks to understand when public persuasion is tractable and how tractable it can be. We focus on a fundamental multi-agent persuasion model introduced by Arieli and Babichenko [3]: many agents, no inter-agent externalities and binary agent actions, and identify well-motivated circumstances under which efficient algorithms are possible. En route, we also develop new algorithmic techniques and demonstrate that they can be applicable to other public persuasion problems or even beyond. We start by proving that optimal public persuasion in our model is fixed parameter tractable. Our main result here builds on an interesting connection to a basic question in combinatorial geometry: how many cells can n hyperplanes divide ℝd into? We use this connection to show a new characterization of public persuasion, which then enables efficient algorithm design. Second, we relax agent incentives and show that optimal public persuasion admits a bi-criteria PTAS for the widely studied class of monotone submodular objectives, and this approximation is tight. To prove this result, we establish an intriguing “noise stability” property of submodular functions which strictly generalizes the key result of Cheraghchi et al. [15], originally motivated by applications of learning submodular functions and differential privacy. Finally, motivated by automated application of persuasion, we consider relaxing the equilibrium concept of the model to coarse correlated equilibrium. Here, using a sophisticated primal-dual analysis, we prove that optimal public persuasion admits an efficient algorithm if and only if the combinatorial problem of maximizing the sender's objective minus any linear function can be solved efficiently, thus establishing their polynomial-time equivalence.