{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,2]],"date-time":"2025-11-02T16:59:58Z","timestamp":1762102798978,"version":"3.37.3"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"9","license":[{"start":{"date-parts":[[2023,4,19]],"date-time":"2023-04-19T00:00:00Z","timestamp":1681862400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,4,19]],"date-time":"2023-04-19T00:00:00Z","timestamp":1681862400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100006690","name":"Politecnico di Milano","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100006690","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2023,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We study <jats:italic>algorithmic Bayesian persuasion<\/jats:italic> problems in which the principal (a.k.a.\u00a0the <jats:italic>sender<\/jats:italic>) has to persuade multiple agents (a.k.a.\u00a0<jats:italic>receivers<\/jats:italic>) by using public communication channels. Specifically, our model follows the multi-receiver model with no inter-agent externalities introduced by Arieli and Babichenko (J Econ Theory 182:185\u2013217, 2019). It is known that the problem of computing a sender-optimal public persuasive signaling scheme is not approximable even in simple settings. Therefore, prior works usually focus on determining restricted classes of the problem for which efficient approximation is possible. Typically, positive results in this space amounts to finding <jats:italic>bi-criteria<\/jats:italic> approximation algorithms yielding an almost optimal and almost persuasive solution in polynomial time. In this paper, we take a different perspective and study the persuasion problem in the general setting where the space of the states of nature, the action space of the receivers, and the utility function of the sender can be arbitrary. We fully characterize the computational complexity of computing a bi-criteria approximation of an optimal public signaling scheme in such settings. In particular, we show that, assuming the Exponential Time Hypothesis, solving this problem requires at least a quasi-polynomial number of steps even in instances with simple utility functions and binary action spaces such as an election with the <jats:italic>k<\/jats:italic>-voting rule. In doing so, we prove that a relaxed version of the <jats:sc>Maximum Feasible Subsystem of Linear Inequalities<\/jats:sc> problem requires at least quasi-polynomial time to be solved. Finally, we close the gap by providing a quasi-polynomial time bi-criteria approximation algorithm for arbitrary public persuasion problems that, under mild assumptions, yields a QPTAS.<\/jats:p>","DOI":"10.1007\/s00453-023-01123-1","type":"journal-article","created":{"date-parts":[[2023,4,19]],"date-time":"2023-04-19T20:32:58Z","timestamp":1681936378000},"page":"2885-2921","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Public Bayesian Persuasion: Being Almost Optimal and Almost Persuasive"],"prefix":"10.1007","volume":"85","author":[{"given":"Matteo","family":"Castiglioni","sequence":"first","affiliation":[]},{"given":"Andrea","family":"Celli","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7349-3932","authenticated-orcid":false,"given":"Nicola","family":"Gatti","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,4,19]]},"reference":[{"key":"1123_CR1","doi-asserted-by":"crossref","unstructured":"Badanidiyuru, A., Bhawalkar, K., Xu, H.: Targeting and signaling in ad auctions. In: SODA, pp. 2545\u20132563 (2018)","DOI":"10.1137\/1.9781611975031.163"},{"issue":"2","key":"1123_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2594564","volume":"2","author":"Y Emek","year":"2014","unstructured":"Emek, Y., Feldman, M., Gamzu, I., PaesLeme, R., Tennenholtz, M.: Signaling schemes for revenue maximization. ACM Trans. Econ. Comput. 2(2), 1\u201319 (2014)","journal-title":"ACM Trans. Econ. Comput."},{"key":"1123_CR3","unstructured":"Miltersen, P.B., Sheffet, O.: Send mixed signals: earn more, work less. In: ACM EC, pp. 234\u2013247 (2012)"},{"issue":"11","key":"1123_CR4","doi-asserted-by":"publisher","first-page":"3590","DOI":"10.1257\/aer.20140737","volume":"106","author":"R Alonso","year":"2016","unstructured":"Alonso, R., C\u00e2mara, O.: Persuading voters. Am. Econ. Rev. 106(11), 3590\u20133605 (2016)","journal-title":"Am. Econ. Rev."},{"key":"1123_CR5","doi-asserted-by":"crossref","unstructured":"Cheng, Y., Cheung, H.Y., Dughmi, S., Emamjomeh-Zadeh, E., Han, L., Teng, S.: Mixture selection, mechanism design, and signaling. In: FOCS, pp. 1426\u20131445 (2015)","DOI":"10.1109\/FOCS.2015.91"},{"key":"1123_CR6","doi-asserted-by":"crossref","unstructured":"Bhaskar, U., Cheng, Y., Ko, Y.K., Swamy, C.: Hardness results for signaling in Bayesian zero-sum and network routing games. In: ACM EC, pp. 479\u2013496 (2016)","DOI":"10.1145\/2940716.2940753"},{"key":"1123_CR7","unstructured":"Vasserman, S., Feldman, M., Hassidim, A.: Implementing the wisdom of waze. In: IJCAI (2015)"},{"key":"1123_CR8","doi-asserted-by":"crossref","unstructured":"Mansour, Y., Slivkins, A., Syrgkanis, V., Wu, Z.S.: Bayesian exploration: Incentivizing exploration in Bayesian games. In: ACM EC, pp. 661\u2013661 (2016)","DOI":"10.1145\/2940716.2940755"},{"key":"1123_CR9","unstructured":"Rabinovich, Z., Jiang, A.X., Jain, M., Xu, H.: Information disclosure as a means to security. In: AAMAS, pp. 645\u2013653 (2015)"},{"key":"1123_CR10","unstructured":"Xu, H., Freeman, R., Conitzer, V., Dughmi, S., Tambe, M.: Signaling in Bayesian Stackelberg games. In: AAMAS, pp. 150\u2013158 (2016)"},{"key":"1123_CR11","doi-asserted-by":"crossref","unstructured":"Xu, H., Rabinovich, Z., Dughmi, S., Tambe, M.: Exploring information asymmetry in two-stage security games. In: AAAI (2015)","DOI":"10.1609\/aaai.v29i1.9290"},{"key":"1123_CR12","unstructured":"Babichenko, Y., Barman, S.: Algorithmic aspects of private Bayesian persuasion. In: Innovations in Theoretical Computer Science Conference (2017)"},{"key":"1123_CR13","doi-asserted-by":"crossref","unstructured":"Candogan, O.: Persuasion in networks: Public signals and k-cores. Available at SSRN (2019)","DOI":"10.2139\/ssrn.3346144"},{"issue":"6","key":"1123_CR14","doi-asserted-by":"publisher","first-page":"2590","DOI":"10.1257\/aer.101.6.2590","volume":"101","author":"E Kamenica","year":"2011","unstructured":"Kamenica, E., Gentzkow, M.: Bayesian persuasion. Am. Econ. Rev. 101(6), 2590\u20132615 (2011)","journal-title":"Am. Econ. Rev."},{"issue":"2","key":"1123_CR15","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1145\/3055589.3055591","volume":"15","author":"S Dughmi","year":"2017","unstructured":"Dughmi, S.: Algorithmic information structure design: a survey. ACM SIGEC Exch 15(2), 2\u201324 (2017)","journal-title":"ACM SIGEC Exch"},{"issue":"5","key":"1123_CR16","doi-asserted-by":"publisher","first-page":"949","DOI":"10.1086\/657922","volume":"118","author":"L Rayo","year":"2010","unstructured":"Rayo, L., Segal, I.: Optimal information disclosure. J Polit Econ 118(5), 949\u2013987 (2010)","journal-title":"J Polit Econ"},{"key":"1123_CR17","doi-asserted-by":"crossref","unstructured":"Castiglioni, M., Gatti, N.: Persuading voters in district-based elections. In: The AAAI Conference on Artificial Intelligence, (AAAI 2021) (2021)","DOI":"10.1609\/aaai.v35i6.16662"},{"key":"1123_CR18","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1016\/j.jet.2019.04.008","volume":"182","author":"I Arieli","year":"2019","unstructured":"Arieli, I., Babichenko, Y.: Private Bayesian persuasion. J. Econ. Theory 182, 185\u2013217 (2019)","journal-title":"J. Econ. Theory"},{"key":"1123_CR19","unstructured":"Rubinstein, A.: Honest Signaling in Zero-Sum Games Is Hard, and Lying Is Even Harder. In: 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017), pp. 77\u201317713 (2017)"},{"key":"1123_CR20","unstructured":"Babichenko, Y., Barman, S.: Algorithmic aspects of private Bayesian persuasion. In: 8th Innovations in Theoretical Computer Science Conference (ITCS 2017) (2017)"},{"key":"1123_CR21","doi-asserted-by":"crossref","unstructured":"Dughmi, S., Xu, H.: Algorithmic persuasion with no externalities. In: ACM EC, pp. 351\u2013368 (2017)","DOI":"10.1145\/3033274.3085152"},{"key":"1123_CR22","doi-asserted-by":"crossref","unstructured":"Xu, H.: On the tractability of public persuasion with no externalities. In: Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 2708\u20132727 (2020). SIAM","DOI":"10.1137\/1.9781611975994.165"},{"key":"1123_CR23","doi-asserted-by":"crossref","unstructured":"Dughmi, S., Xu, H.: Algorithmic Bayesian persuasion. In: ACM STOC, pp. 412\u2013425 (2016)","DOI":"10.1145\/2897518.2897583"},{"key":"1123_CR24","doi-asserted-by":"crossref","unstructured":"Castiglioni, M., Celli, A., Gatti, N.: Persuading voters: It\u2019s easy to whisper, it\u2019s hard to speak loud. In: Proceedings of the AAAI Conference on Artificial Intelligence vol. 34, pp. 1870\u20131877 (2020)","DOI":"10.1609\/aaai.v34i02.5555"},{"issue":"1 &2","key":"1123_CR25","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1016\/0304-3975(94)00254-G","volume":"147","author":"E Amaldi","year":"1995","unstructured":"Amaldi, E., Kann, V.: The complexity and approximability of finding maximum feasible subsystems of linear relations. Theor. Comput. Sci. 147(1 &2), 181\u2013210 (1995)","journal-title":"Theor. Comput. Sci."},{"key":"1123_CR26","doi-asserted-by":"crossref","unstructured":"Daskalakis, C., De, A., Diakonikolas, I., Moitra, A., Servedio, R.: A polynomial-time approximation scheme for fault-tolerant distributed storage. In: SODA, pp. 628\u2013644 (2014)","DOI":"10.1137\/1.9781611973402.48"},{"key":"1123_CR27","doi-asserted-by":"crossref","unstructured":"Aaronson, S., Impagliazzo, R., Moshkovitz, D.: Am with multiple merlins. In: CCC, pp. 44\u201355 (2014)","DOI":"10.1109\/CCC.2014.13"},{"key":"1123_CR28","doi-asserted-by":"crossref","unstructured":"Deligkas, A., Fearnley, J., Savani, R.: Inapproximability results for approximate nash equilibria. In: International Conference on Web and Internet Economics, pp. 29\u201343 (2016). Springer","DOI":"10.1007\/978-3-662-54110-4_3"},{"issue":"1","key":"1123_CR29","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1257\/jel.20181489","volume":"57","author":"D Bergemann","year":"2019","unstructured":"Bergemann, D., Morris, S.: Information design: a unified perspective. J. Econ. Lit. 57(1), 44\u201395 (2019)","journal-title":"J. Econ. Lit."},{"key":"1123_CR30","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1146\/annurev-economics-080218-025739","volume":"11","author":"E Kamenica","year":"2018","unstructured":"Kamenica, E.: Bayesian persuasion and information design. Annu. Rev. Econ. 11, 249 (2018)","journal-title":"Annu. Rev. Econ."},{"issue":"2","key":"1123_CR31","doi-asserted-by":"publisher","first-page":"487","DOI":"10.3982\/TE1808","volume":"11","author":"D Bergemann","year":"2016","unstructured":"Bergemann, D., Morris, S.: Bayes correlated equilibrium and the comparison of information structures in games. Theor. Econ. 11(2), 487\u2013522 (2016)","journal-title":"Theor. Econ."},{"issue":"5","key":"1123_CR32","doi-asserted-by":"publisher","first-page":"586","DOI":"10.1257\/aer.p20161046","volume":"106","author":"D Bergemann","year":"2016","unstructured":"Bergemann, D., Morris, S.: Information design, Bayesian persuasion, and Bayes correlated equilibrium. Am. Econ. Rev. 106(5), 586\u201391 (2016)","journal-title":"Am. Econ. Rev."},{"key":"1123_CR33","doi-asserted-by":"crossref","unstructured":"Brandt, F., Conitzer, V., Endriss, U., Lang, J., Procaccia, A.D.: Handbook of computational social choice. Cambridge University Press (2016)","DOI":"10.1017\/CBO9781107446984.002"},{"key":"1123_CR34","doi-asserted-by":"crossref","unstructured":"Babichenko, Y., Papadimitriou, C., Rubinstein, A.: Can almost everybody be almost happy? In: Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, pp. 1\u20139 (2016)","DOI":"10.1145\/2840728.2840731"},{"issue":"3","key":"1123_CR35","doi-asserted-by":"publisher","first-page":"504","DOI":"10.1002\/j.1538-7305.1952.tb01393.x","volume":"31","author":"EN Gilbert","year":"1952","unstructured":"Gilbert, E.N.: A comparison of signalling alphabets. Bell Syst. Tech. J. 31(3), 504\u2013522 (1952)","journal-title":"Bell Syst. Tech. J."},{"issue":"3","key":"1123_CR36","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1145\/1236457.1236459","volume":"54","author":"I Dinur","year":"2007","unstructured":"Dinur, I.: The PCP theorem by gap amplification. J. ACM 54(3), 12 (2007)","journal-title":"J. ACM"},{"issue":"2","key":"1123_CR37","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1016\/S0019-9958(84)80056-X","volume":"61","author":"S Even","year":"1984","unstructured":"Even, S., Selman, A.L., Yacobi, Y.: The complexity of promise problems with applications to public-key cryptography. Inf. Control 61(2), 159\u2013173 (1984)","journal-title":"Inf. Control"},{"key":"1123_CR38","doi-asserted-by":"crossref","unstructured":"Goldreich, O.: On promise problems: A survey. In: Theoretical Computer Science, pp. 254\u2013290 (2006)","DOI":"10.1007\/11685654_12"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-023-01123-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-023-01123-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-023-01123-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,22]],"date-time":"2023-09-22T15:04:17Z","timestamp":1695395057000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-023-01123-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,4,19]]},"references-count":38,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2023,9]]}},"alternative-id":["1123"],"URL":"https:\/\/doi.org\/10.1007\/s00453-023-01123-1","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2023,4,19]]},"assertion":[{"value":"7 December 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 February 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 April 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no conflicts of interest to declare that are relevant to the content of this article.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}