Abstract
We consider a multireceivers Bayesian persuasion model where an informed sender tries to persuade a group of receivers to take a certain action. The state of nature is known to the sender, but it is unknown to the receivers. The sender is allowed to commit to a signaling policy where she sends a private signal to every receiver. This work studies the computation aspects of finding a signaling policy that maximizes the sender's revenue.
We show that if the sender's utility is a submodular function of the set of receivers that take the desired action, then we can efficiently find a signaling policy whose revenue is at least (11/e) times the optimal. We also prove that approximating the sender's optimal revenue by a factor better than (11/e) is NPhard and, hence, the developed approximation guarantee is essentially tight. When the sender's utility is a function of the number of receivers that take the desired action (i.e., the utility function is anonymous), we show that an optimal signaling policy can be computed in polynomial time. Our results are based on an interesting connection between the Bayesian persuasion problem and the evaluation of the concave closure of a set function.
BibTeX  Entry
@InProceedings{babichenko_et_al:LIPIcs:2017:8150,
author = {Yakov Babichenko and Siddharth Barman},
title = {{Algorithmic Aspects of Private Bayesian Persuasion}},
booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
pages = {34:134:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770293},
ISSN = {18688969},
year = {2017},
volume = {67},
editor = {Christos H. Papadimitriou},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/8150},
URN = {urn:nbn:de:0030drops81502},
doi = {10.4230/LIPIcs.ITCS.2017.34},
annote = {Keywords: Economics of Information, Bayesian Persuasion, Signaling, Concave Closure}
}
Keywords: 

Economics of Information, Bayesian Persuasion, Signaling, Concave Closure 
Collection: 

8th Innovations in Theoretical Computer Science Conference (ITCS 2017) 
Issue Date: 

2017 
Date of publication: 

28.11.2017 