{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:26:41Z","timestamp":1787340401812,"version":"build-2736575974"},"reference-count":49,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2021,1]]},"abstract":"<jats:p>Persuasion, defined as the act of exploiting an informational advantage in order to influence the decisions of others, is ubiquitous. Indeed, persuasive communication has been estimated to account for almost a third of all economic activity in the U.S. This paper examines persuasion through a computational lens, focusing on what is perhaps the most basic and fundamental model in this space: the celebrated Bayesian persuasion model of Kamenica and Gentzkow [ Am. Econ. Rev., 101 (2011), pp. 2590--2615]. Here there are two players, a sender and a receiver. The receiver must take one of a number of actions with an a priori unknown payoff, and the sender has access to additional information regarding the payoffs of the various actions for both players. The sender can commit to revealing a noisy signal regarding the realization of the payoffs of various actions, and would like to do so to maximize her own payoff in expectation assuming that the receiver rationally acts to maximize his own payoff. When the payoffs of various actions follow a joint distribution (the common prior), the sender's problem is nontrivial, and its computational complexity depends on the representation of this prior. We examine the sender's optimization task in three of the most natural input models for this problem, and essentially pin down its computational complexity in each. When the payoff distributions of the different actions are independently and identically distributed (i.i.d.) and given explicitly, we exhibit a polynomial-time (exact) algorithmic solution, and a \u201csimple\u201d $(1-1\/e)$-approximation algorithm. Our optimal scheme for the i.i.d. setting involves an analogy to auction theory, and makes use of Border's characterization of the space of reduced-forms for single-item auctions. When action payoffs are independent but nonidentical with marginal distributions given explicitly, we show that it is \\#P-hard to compute the optimal expected sender utility. In doing so, we rule out a generalized Border's theorem, in the sense of Gopalan, Nisan, and Roughgarden [ Public projects, boolean functions, and the borders of Border's theorem, in Proceedings of the Sixteenth ACM Conference on Economics and Computation, EC '15, ACM, New York, 2015, p. 395], for this setting. Finally, we consider a general (possibly correlated) joint distribution of action payoffs presented by a black box sampling oracle, and exhibit a fully polynomial-time approximation scheme (FPTAS) with a bicriteria guarantee. Our FPTAS is based on Monte Carlo sampling, and its analysis relies on the principle of deferred decisions. Moreover, we show that this result is the best possible in the black-box model for information-theoretic reasons.<\/jats:p>","DOI":"10.1137\/16m1098334","type":"journal-article","created":{"date-parts":[[2019,10,24]],"date-time":"2019-10-24T09:06:41Z","timestamp":1571908001000},"page":"STOC16-68-STOC16-97","source":"Crossref","is-referenced-by-count":12,"title":["Algorithmic Bayesian Persuasion"],"prefix":"10.1137","volume":"50","author":[{"given":"Shaddin","family":"Dughmi","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Haifeng","family":"Xu","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2019,10,21]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1110.1011"},{"key":"atypb2","first-page":"17","author":"Alaei S.","year":"2012","journal-title":"New York"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1257\/aer.20140737"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1257\/000282806776157632"},{"key":"atypb5","first-page":"1","author":"Antioch G.","year":"2013","journal-title":"Economic Roundup"},{"key":"atypb6","unstructured":"R. Aumann and M. Maschler,\n                      Repeated Games with Incomplete Information\n                      , MIT Press, Cambridge, MA, 1995."},{"key":"atypb7","first-page":"92","author":"Babaioff M.","year":"2012","journal-title":"New York"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1257\/mic.20140155"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.3982\/TE1808"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1016\/j.jet.2007.02.001"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1257\/aer.20130848"},{"key":"atypb12","doi-asserted-by":"crossref","unstructured":"D. Bergemann, A. Bonatti, and A. Smolin,\n                      The designing and pricing information\n                      , Working Paper, 2016.","DOI":"10.2139\/ssrn.2811839"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1007\/s00199-006-0080-z"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.2307\/2938181"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1111\/j.0741-6261.2007.00119.x"},{"key":"atypb16","first-page":"459","author":"Cai Y.","year":"2012","journal-title":"New York"},{"key":"atypb17","doi-asserted-by":"crossref","unstructured":"Y. Cai, C. Daskalakis, and S. M. Weinberg,\n                      Optimal multi-dimensional mechanism design: Reducing revenue to welfare maximization\n                      , in Proceedings of the 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science (FOCS), IEEE, 2012\\natexlabb, pp. 130-139.","DOI":"10.1109\/FOCS.2012.88"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1287\/mksc.2013.0826"},{"key":"atypb19","first-page":"1426","author":"Cheng Y.","year":"2015","journal-title":"Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS), IEEE"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.2307\/1913390"},{"key":"atypb21","first-page":"370","author":"Daskalakis C.","year":"2012","journal-title":"New York"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1146\/annurev.economics.102308.124309"},{"key":"atypb23","doi-asserted-by":"crossref","unstructured":"S. Dughmi,\n                      On the hardness of signaling\n                      , in Proceedings of the 55th Symposium on Foundations of Computer Science, FOCS '14. IEEE, 2014.","DOI":"10.1109\/FOCS.2014.45"},{"key":"atypb24","doi-asserted-by":"crossref","unstructured":"S. Dughmi, N. Immorlica, and A. Roth,\n                      Constrained signaling in auction design\n                      , in Proceedings of the Twenty-fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '14, SIAM, Philadelphia, 2014.","DOI":"10.1137\/1.9781611973402.99"},{"key":"atypb25","first-page":"514","author":"Emek Y.","year":"2012","journal-title":"New York"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-937X.2007.00442.x"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1257\/aer.104.5.457"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1093\/restud\/rdw052"},{"key":"atypb29","doi-asserted-by":"crossref","unstructured":"W. Gick and T. Pausch,\n                      Persuasion by stress testing: Optimal disclosure of supervisory information in the banking sector\n                      , Number 32\/2012. Discussion Paper, Deutsche Bundesbank, 2012.","DOI":"10.2139\/ssrn.2796887"},{"key":"atypb30","doi-asserted-by":"crossref","unstructured":"I. Goldstein and Y. Leitner,\n                      Stress tests and information disclosure\n                      , Working Paper, 2015.","DOI":"10.21799\/frbp.wp.2015.10"},{"key":"atypb31","first-page":"395","author":"Gopalan P.","year":"2015","journal-title":"New York"},{"key":"atypb32","doi-asserted-by":"crossref","unstructured":"M. Gr\u00f6tschel, L. Lov\u00e1sz, and A. Schrijver,\n                      Geometric Algorithms and Combinatorial Optimization\n                      , Algorithms and Combinatorics 2, Springer-Verlag, Berlin, Heidelberg, 1988.","DOI":"10.1007\/978-3-642-97881-4"},{"key":"atypb33","unstructured":"M. Guo and A. Deligkas,\n                      Revenue maximization via hiding item attributes\n                      , in Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence (IJCAI), 2013, AAAI Press, pp. 157-163."},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1257\/aer.96.3.756"},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1257\/aer.101.6.2590"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2015.02.006"},{"key":"atypb37","doi-asserted-by":"crossref","unstructured":"A. Kolotilin, M. Li, T. Mylovanov, and A. Zapechelnyuk,\n                      Persuasion of a privately informed receiver\n                      , Working paper, 2016.","DOI":"10.2139\/ssrn.2913916"},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.1086\/676597"},{"key":"atypb39","first-page":"565","author":"Mansour Y.","year":"2015","journal-title":"New York"},{"key":"atypb40","first-page":"661","author":"Mansour Y.","year":"2016","journal-title":"New York"},{"key":"atypb41","first-page":"191","volume":"85","author":"McCloskey D.","year":"1995","journal-title":"Am. Econ. Rev."},{"key":"atypb42","first-page":"234","author":"Miltersen P. B.","year":"2012","journal-title":"New York"},{"key":"atypb43","doi-asserted-by":"publisher","DOI":"10.1287\/moor.6.1.58"},{"key":"atypb44","doi-asserted-by":"crossref","unstructured":"Z. Rabinovich, A. X. Jiang, M. Jain, and H. Xu,\n                      Information disclosure as a means to security\n                      , in Proceedings of the 14th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2015, pp. 645-653.","DOI":"10.65109\/CYNE5395"},{"key":"atypb45","doi-asserted-by":"publisher","DOI":"10.1086\/657922"},{"key":"atypb46","unstructured":"A. Schrijver,\n                      Combinatorial Optimization - Polyhedra and Efficiency\n                      , Springer-Verlag, Berlin, Heidelberg, 2003."},{"key":"atypb47","unstructured":"S. M. Weinberg,\n                      Algorithms for Strategic Agents\n                      , Ph.D. thesis, Massachusetts Institute of Technology, Cambridge, MA, 2014."},{"key":"atypb48","doi-asserted-by":"crossref","unstructured":"H. Xu, Z. Rabinovich, S. Dughmi, and M. Tambe,\n                      Exploring information asymmetry in two-stage security games\n                      , in AAAI Conference on Artificial Intelligence (AAAI), AAAI Press, 2015.","DOI":"10.1609\/aaai.v29i1.9290"},{"key":"atypb49","first-page":"710","author":"Yan Q.","year":"2011","journal-title":"Philadelphia"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/16M1098334","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:33:27Z","timestamp":1787337207000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/16M1098334"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,10,21]]},"references-count":49,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["10.1137\/16M1098334"],"URL":"https:\/\/doi.org\/10.1137\/16m1098334","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,10,21]]}}}