Babichenko, Yakov ;
TalgamCohen, Inbal ;
Xu, Haifeng ;
Zabarnyi, Konstantin
MultiChannel Bayesian Persuasion
Abstract
The celebrated Bayesian persuasion model considers strategic communication between an informed agent (the sender) and uninformed decision makers (the receivers). The current rapidlygrowing 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 multichannel 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 informationdominates 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 informationdominating 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 cryptographicinspired 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 informationtheoretical 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 informationdominating 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 polynomialtime constantfactor 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 multichannel 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 nonnegative 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 multichannel persuasion.
BibTeX  Entry
@InProceedings{babichenko_et_al:LIPIcs.ITCS.2022.11,
author = {Babichenko, Yakov and TalgamCohen, Inbal and Xu, Haifeng and Zabarnyi, Konstantin},
title = {{MultiChannel Bayesian Persuasion}},
booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
pages = {11:111:2},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772174},
ISSN = {18688969},
year = {2022},
volume = {215},
editor = {Braverman, Mark},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/15607},
URN = {urn:nbn:de:0030drops156072},
doi = {10.4230/LIPIcs.ITCS.2022.11},
annote = {Keywords: Algorithmic game theory, Bayesian persuasion, Private Bayesian persuasion, Public Bayesian persuasion, Secret sharing, Networks}
}
25.01.2022
Keywords: 

Algorithmic game theory, Bayesian persuasion, Private Bayesian persuasion, Public Bayesian persuasion, Secret sharing, Networks 
Seminar: 

13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

Issue date: 

2022 
Date of publication: 

25.01.2022 