Algorithms for Persuasion with Limited Communication

• 成果类型: Article; Early Access
• 署名作者: Gradwohl, Ronen; Hahn, Niklas; Hoefer, Martin; Smorodinsky, Rann
• 署名单位: Ariel University; Goethe University Frankfurt; Technion Israel Institute of Technology
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2021.1218
• 发表日期: 2022
• 关键词: Bayesian persuasion

摘要

The Bayesian persuasion paradigm of strategic communication models interaction between a privately informed sender and an ignorant but rational receiver. The goal is typically to design a (near-)optimal communication (or signaling) scheme for the sender. It enables the sender to disclose information to the receiver in a way as to incentivize her to take an action that is preferred by the sender. Finding the optimal signaling scheme is known to be computationally difficult in general. This hardness is further exacerbated when the message space is constrained, leading to NP-hardness of approximating the optimal sender utility within any constant factor. In this paper, we show that in several natural and prominent cases the optimization problem is tractable even when the message space is limited. In particular, we study signaling under a symmetry or an independence assumption on the distribution of utility values for the actions. For symmetric distributions, we provide a novel characterization of the optimal signaling scheme. It results in a polynomial-time algorithm to compute an optimal scheme for many compactly represented symmetric distributions. In the independent cage, we design a constant-factor approximation algorithm, which stands in marked contrast to the hardness of approximation in the general case.