License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2017.34
URN: urn:nbn:de:0030-drops-81502
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/8150/
Go to the corresponding LIPIcs Volume Portal

Babichenko, Yakov ; Barman, Siddharth

Algorithmic Aspects of Private Bayesian Persuasion

pdf-format:
LIPIcs-ITCS-2017-34.pdf (0.5 MB)

Abstract

We consider a multi-receivers 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 (1-1/e) times the optimal. We also prove that approximating the sender's optimal revenue by a factor better than (1-1/e) is NP-hard 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:1--34:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-029-3},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{67},
  editor =	{Christos H. Papadimitriou},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/8150},
  URN =		{urn:nbn:de:0030-drops-81502},
  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

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI