Document Open Access Logo

Algorithmic Aspects of Private Bayesian Persuasion

Authors Yakov Babichenko, Siddharth Barman

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2017.34.pdf
  • Filesize: 0.5 MB
  • 16 pages

Document Identifiers

Author Details

Yakov Babichenko
Siddharth Barman

Cite As Get BibTex

Yakov Babichenko and Siddharth Barman. Algorithmic Aspects of Private Bayesian Persuasion. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 34:1-34:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ITCS.2017.34

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.

Subject Classification

Keywords
  • Economics of Information
  • Bayesian Persuasion
  • Signaling
  • Concave Closure

Metrics

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

References

  1. Ricardo Alonso and Odilon Câmara. On the value of persuasion by experts. Technical report, University of Southern California, Marshall School of Business, 2014. Google Scholar
  2. Ricardo Alonso and Odilon Câmara. Persuading voters. Available at SSRN 2688969, 2015. Google Scholar
  3. Simon P Anderson and Régis Renault. The advertising mix for a search good. Management Science, 59(1):69-83, 2013. Google Scholar
  4. Itai Arieli and Yakov Babichenko. Private bayesian persuasion. Available at SSRN 2721307, 2016. Google Scholar
  5. Robert J Aumann, Michael Maschler, and Richard E Stearns. Repeated games with incomplete information. MIT press, 1995. Google Scholar
  6. David Austen-Smith and Jeffrey S Banks. Information aggregation, rationality, and the condorcet jury theorem. American political science review, 90(01):34-45, 1996. Google Scholar
  7. Dirk Bergemann and Martin Pesendorfer. Information structures in optimal auctions. Journal of economic theory, 137(1):580-609, 2007. Google Scholar
  8. Fernando Branco, Monic Sun, and J Miguel Villas-Boas. Too much information? information provision and search costs. Marketing Science, 2015. Google Scholar
  9. Peter Bro Miltersen and Or Sheffet. Send mixed signals: earn more, work less. In Proceedings of the 13th ACM Conference on Electronic Commerce, pages 234-247. ACM, 2012. Google Scholar
  10. Gruia Calinescu, Chandra Chekuri, Martin Pál, and Jan Vondrák. Maximizing a monotone submodular function subject to a matroid constraint. SIAM Journal on Computing, 2011. Google Scholar
  11. Jimmy Chan, Fei Li, and Yun Wang. Discriminatory persuasion: How to convince a group. Available at SSRN, 2015. Google Scholar
  12. Vincent P Crawford and Joel Sobel. Strategic information transmission. Econometrica: Journal of the Econometric Society, 1982. Google Scholar
  13. Shaddin Dughmi. Submodular functions: Extensions, distributions, and algorithms. a survey. arXiv preprint arXiv:0912.0322, 2009. Google Scholar
  14. Shaddin Dughmi, Nicole Immorlica, and Aaron Roth. Constrained signaling in auction design. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1341-1357. Society for Industrial and Applied Mathematics, 2014. Google Scholar
  15. Shaddin Dughmi and Haifeng Xu. Algorithmic bayesian persuasion. STOC 2016, 2016. Google Scholar
  16. Yuval Emek, Michal Feldman, Iftah Gamzu, Renato PaesLeme, and Moshe Tennenholtz. Signaling schemes for revenue maximization. ACM Transactions on Economics and Computation, 2(2):5, 2014. Google Scholar
  17. Uriel Feige, Magnús M Halldórsson, Guy Kortsarz, and Aravind Srinivasan. Approximating the domatic number. SIAM Journal on computing, 2002. Google Scholar
  18. Matthew Gentzkow and Emir Kamenica. Bayesian persuasion. American Economic Review, 2011. Google Scholar
  19. Matthew Gentzkow and Emir Kamenica. Competition in persuasion. Technical report, National Bureau of Economic Research, 2011. Google Scholar
  20. Matthew Gentzkow and Emir Kamenica. Costly persuasion. The American Economic Review, 2014. Google Scholar
  21. Itay Goldstein and Yaron Leitner. Stress tests and information disclosure. Technical report, FRB of Philadelphia Working Paper, 2015. Google Scholar
  22. Mingyu Guo and Argyrios Deligkas. Revenue maximization via hiding item attributes. arXiv preprint arXiv:1302.5332, 2013. Google Scholar
  23. David Kempe, Jon Kleinberg, and Éva Tardos. Maximizing the spread of influence through a social network. In Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 137-146. ACM, 2003. Google Scholar
  24. Subhash Khot, Richard J Lipton, Evangelos Markakis, and Aranyak Mehta. Inapproximability results for combinatorial auctions with submodular utility functions. In Internet and Network Economics. Springer, 2005. Google Scholar
  25. Kazuo Murota. Convexity and steinitz’s exchange property. In Integer Programming and Combinatorial Optimization, pages 260-274. Springer, 1996. Google Scholar
  26. Kazuo Murota. Discrete convex analysis. SIAM, 2003. Google Scholar
  27. Keith E Schnakenberg. Expert advice to a voting body. Journal of Economic Theory, 2015. Google Scholar
  28. Wataru Tamura. Optimal monetary policy and transparency under informational frictions. Available at SSRN 2191900, 2014. Google Scholar
  29. Ina A Taneva. Information design. Technical report, University of Edinburgh, 2015. Google Scholar
  30. Jan Vondrák. Submodularity in combinatorial optimization. PhD thesis, PhD thesis, Charles University, Prague, Czech Republic, 2007. Google Scholar
  31. Yun Wang. Bayesian persuasion with multiple receivers. Available at SSRN 2625399, 2013. 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
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact