Multi-Channel Bayesian Persuasion

Authors Yakov Babichenko, Inbal Talgam-Cohen, Haifeng Xu, Konstantin Zabarnyi



PDF
Thumbnail PDF

File

LIPIcs.ITCS.2022.11.pdf
  • Filesize: 338 kB
  • 2 pages

Document Identifiers

Author Details

Yakov Babichenko
  • Technion - Israel Institute of Technology, Haifa, Israel
Inbal Talgam-Cohen
  • Technion - Israel Institute of Technology, Haifa, Israel
Haifeng Xu
  • University of Virginia, Charlottesville, VA, USA
Konstantin Zabarnyi
  • Technion - Israel Institute of Technology, Haifa, Israel

Acknowledgements

The authors thank Fedor Sandomirskiy for his helpful remarks on the connection of our main result proof to secret sharing protocols. The authors are also grateful to the anonymous reviewers for their suggestions on improving the paper.

Cite AsGet BibTex

Yakov Babichenko, Inbal Talgam-Cohen, Haifeng Xu, and Konstantin Zabarnyi. Multi-Channel Bayesian Persuasion. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 11:1-11:2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ITCS.2022.11

Abstract

The celebrated Bayesian persuasion model considers strategic communication between an informed agent (the sender) and uninformed decision makers (the receivers). The current rapidly-growing literature assumes a dichotomy: either the sender is powerful enough to communicate separately with each receiver (a.k.a. private persuasion), or she cannot communicate separately at all (a.k.a. public persuasion). We propose a model that smoothly interpolates between the two, by introducing a natural multi-channel communication structure in which each receiver observes a subset of the sender’s communication channels. This captures, e.g., receivers on a network, where information spillover is almost inevitable. Our main result is a complete characterization specifying when one communication structure is better for the sender than another, in the sense of yielding higher optimal expected utility universally over all prior distributions and utility functions. The characterization is based on a simple pairwise relation among receivers - one receiver information-dominates another if he observes at least the same channels. We prove that a communication structure M₁ is (weakly) better than M₂ if and only if every information-dominating pair of receivers in M₁ is also such in M₂. This result holds in the most general model of Bayesian persuasion in which receivers may have externalities - that is, the receivers' actions affect each other. The proof is cryptographic-inspired and it has a close conceptual connection to secret sharing protocols. As a surprising consequence of the main result, the sender can implement private Bayesian persuasion (which is the best communication structure for the sender) for k receivers using only O(log k) communication channels, rather than k channels in the naive implementation. We provide an implementation that matches the information-theoretical lower bound on the number of channels - not only asymptotically, but exactly. Moreover, the main result immediately implies some results of [Kerman and Tenev, 2021] on persuading receivers arranged in a network such that each receiver observes both the signals sent to him and to his neighbours in the network. We further provide an additive FPTAS for an optimal sender’s signaling scheme when the number of states of nature is constant, the sender has an additive utility function and the graph of the information-dominating pairs of receivers is a directed forest. We focus on a constant number of states, as even for the special case of public persuasion and additive sender’s utility, it was shown by [Shaddin Dughmi and Haifeng Xu, 2017] that one can achieve neither an additive PTAS nor a polynomial-time constant-factor optimal sender’s utility approximation (unless P=NP). We leave for future research studying exact tractability of forest communication structures, as well as generalizing our result to more families of sender’s utility functions and communication structures. Finally, we prove that finding an optimal signaling scheme under multi-channel persuasion is computationally hard for a general family of sender’s utility functions - separable supermajority functions, which are specified by choosing a partition of the set of receivers and summing supermajority functions corresponding to different elements of the partition, multiplied by some non-negative constants. Note that one can easily deduce from [Emir Kamenica and Matthew Gentzkow, 2011] and [Itai Arieli and Yakov Babichenko, 2019] that finding an optimal signaling scheme for such utility functions is computationally tractable for both public and private persuasion. This difference illustrates both the conceptual and the computational hardness of general multi-channel persuasion.

Subject Classification

ACM Subject Classification
  • Theory of computation → Algorithmic game theory
Keywords
  • Algorithmic game theory
  • Bayesian persuasion
  • Private Bayesian persuasion
  • Public Bayesian persuasion
  • Secret sharing
  • Networks

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Itai Arieli and Yakov Babichenko. Private Bayesian persuasion. Journal of Economic Theory, 182:185-217, 2019. Google Scholar
  2. Shaddin Dughmi and Haifeng Xu. Algorithmic persuasion with no externalities. In Proceedings of the 2017 ACM Conference on Economics and Computation EC, pages 351-368, 2017. Google Scholar
  3. Emir Kamenica and Matthew Gentzkow. Bayesian persuasion. American Economic Review, 101(6):2590-2615, 2011. Google Scholar
  4. Toygar Kerman and Anastas P. Tenev. Persuading communicating voters. Available at SSRN 3765527, 2021. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail