{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,10]],"date-time":"2026-03-10T21:54:13Z","timestamp":1773179653928,"version":"3.50.1"},"reference-count":34,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2024,11,7]],"date-time":"2024-11-07T00:00:00Z","timestamp":1730937600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-sa\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Econ. Comput."],"published-print":{"date-parts":[[2024,12,31]]},"abstract":"<jats:p>In a game of persuasion with evidence, a sender has private information. By presenting evidence on the information, the sender wishes to persuade a receiver to take a single action (e.g., hire a job candidate, or convict a defendant). The sender\u2019s utility depends solely on whether the receiver takes the action. The receiver\u2019s utility depends on both the action and the sender\u2019s private information.<\/jats:p>\n          <jats:p>We study three natural variations. First, we consider the problem of computing an equilibrium of the game without commitment power. Second, we consider a persuasion variant, where the sender commits to a signaling scheme and the receiver, after seeing the evidence, takes the action or not. Third, we study a delegation variant, where the receiver first commits to taking the action if being presented certain evidence, and the sender presents evidence to maximize the probability the action is taken. We study these variants through the computational lens, and give hardness results, optimal approximation algorithms, and polynomial-time algorithms for special cases. Among our results is an approximation algorithm that rounds a semidefinite program that might be of independent interest, since, to the best of our knowledge, it is the first such approximation algorithm in algorithmic economics.<\/jats:p>","DOI":"10.1145\/3696470","type":"journal-article","created":{"date-parts":[[2024,9,21]],"date-time":"2024-09-21T09:49:04Z","timestamp":1726912144000},"page":"1-34","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Algorithmic Persuasion with Evidence"],"prefix":"10.1145","volume":"12","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0131-5605","authenticated-orcid":false,"given":"Martin","family":"Hoefer","sequence":"first","affiliation":[{"name":"RWTH Aachen University, Aachen, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1052-2801","authenticated-orcid":false,"given":"Pasin","family":"Manurangsi","sequence":"additional","affiliation":[{"name":"Google Inc, Mountain View, United States"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7709-5058","authenticated-orcid":false,"given":"Alexandros","family":"Psomas","sequence":"additional","affiliation":[{"name":"Purdue University, West Lafayette, United States"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,11,7]]},"reference":[{"issue":"1","key":"e_1_3_4_2_2","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1016\/S0304-3975(98)00158-3","article-title":"Some APX-completeness results for cubic graphs","volume":"237","author":"Alimonti Paola","year":"2000","unstructured":"Paola Alimonti and Viggo Kann. 2000. Some APX-completeness results for cubic graphs. Theor. Comput. Sci. 237, 1-2 (2000), 123\u2013134.","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"e_1_3_4_3_2","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1137\/0805002","article-title":"Interior point methods in semidefinite programming with applications to combinatorial optimization","volume":"5","author":"Alizadeh Farid","year":"1995","unstructured":"Farid Alizadeh. 1995. Interior point methods in semidefinite programming with applications to combinatorial optimization. SIAM J. Opt. 5, 1 (1995), 13\u201351.","journal-title":"SIAM J. Opt."},{"key":"e_1_3_4_4_2","first-page":"189","volume-title":"Proceedings of the 39th Symposium on Theoretical Computing (STOC\u201907)","author":"Austrin Per","year":"2007","unstructured":"Per Austrin. 2007. Balanced MAX 2-SAT might not be the hardest. In Proceedings of the 39th Symposium on Theoretical Computing (STOC\u201907). 189\u2013197."},{"issue":"6","key":"e_1_3_4_5_2","doi-asserted-by":"crossref","first-page":"2430","DOI":"10.1137\/070711670","article-title":"Towards sharp inapproximability for any 2-CSP","volume":"39","author":"Austrin Per","year":"2010","unstructured":"Per Austrin. 2010. Towards sharp inapproximability for any 2-CSP. SIAM J. Comput. 39, 6 (2010), 2430\u20132463.","journal-title":"SIAM J. Comput."},{"key":"e_1_3_4_6_2","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/j.geb.2006.03.003","article-title":"Hard evidence and mechanism design","volume":"58","author":"Bull Jesse","year":"2007","unstructured":"Jesse Bull and Joel Watson. 2007. Hard evidence and mechanism design. Games Econ. Behav. 58 (2007), 75\u201393.","journal-title":"Games Econ. Behav."},{"issue":"6","key":"e_1_3_4_7_2","doi-asserted-by":"crossref","first-page":"1867","DOI":"10.3982\/ECTA15712","article-title":"Strategic communication with minimal verification","volume":"87","author":"Carroll Gabriel","year":"2019","unstructured":"Gabriel Carroll and Georgy Egorov. 2019. Strategic communication with minimal verification. Econometrica 87, 6 (2019), 1867\u20131892.","journal-title":"Econometrica"},{"key":"e_1_3_4_8_2","doi-asserted-by":"crossref","first-page":"609","DOI":"10.1016\/j.geb.2018.08.001","article-title":"On the hardness of designing public signals","volume":"118","author":"Dughmi Shaddin","year":"2019","unstructured":"Shaddin Dughmi. 2019. On the hardness of designing public signals. Games Econ. Behav. 118 (2019), 609\u2013625.","journal-title":"Games Econ. Behav."},{"key":"e_1_3_4_9_2","first-page":"663","volume-title":"Proceedings of the 17th Conference on Economics and Computation (EC\u201916)","author":"Dughmi Shaddin","year":"2016","unstructured":"Shaddin Dughmi, David Kempe, and Ruixin Qiang. 2016. Persuasion with limited communication. In Proceedings of the 17th Conference on Economics and Computation (EC\u201916). 663\u2013680."},{"key":"e_1_3_4_10_2","doi-asserted-by":"crossref","first-page":"142","DOI":"10.1007\/978-3-030-35389-6_11","volume-title":"Proceedings of the 15th International Conference Web & Internet Economics (WINE\u201919)","author":"Dughmi Shaddin","year":"2019","unstructured":"Shaddin Dughmi, Rad Niazadeh, Alexandros Psomas, and Matthew Weinberg. 2019. Persuasion and incentives through the lens of duality. In Proceedings of the 15th International Conference Web & Internet Economics (WINE\u201919). 142\u2013155."},{"key":"e_1_3_4_11_2","first-page":"412","volume-title":"Proceedings of the 48th Symposium on Theoretical Computing (STOC\u201916)","author":"Dughmi Shaddin","year":"2016","unstructured":"Shaddin Dughmi and Haifeng Xu. 2016. Algorithmic Bayesian persuasion. In Proceedings of the 48th Symposium on Theoretical Computing (STOC\u201916). 412\u2013425."},{"key":"e_1_3_4_12_2","first-page":"351","volume-title":"Proceedings of the 18th Conference on Economics and Computation (EC\u201917)","author":"Dughmi Shaddin","year":"2017","unstructured":"Shaddin Dughmi and Haifeng Xu. 2017. Algorithmic persuasion with no externalities. In Proceedings of the 18th Conference on Economics and Computation (EC\u201917). 351\u2013368."},{"issue":"2","key":"e_1_3_4_13_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2594564","article-title":"Signaling schemes for revenue maximization","volume":"2","author":"Emek Yuval","year":"2014","unstructured":"Yuval Emek, Michal Feldman, Iftah Gamzu, Renato PaesLeme, and Moshe Tennenholtz. 2014. Signaling schemes for revenue maximization. ACM Trans. Econom. Comput. 2, 2 (2014), 1\u201319.","journal-title":"ACM Trans. Econom. Comput."},{"key":"e_1_3_4_14_2","doi-asserted-by":"crossref","first-page":"182","DOI":"10.1109\/ISTCS.1995.377033","volume-title":"Proceedings of the 3rd Israel Symposium on Theoretical Computing Systems.","author":"Feige Uriel","year":"1995","unstructured":"Uriel Feige and Michel Goemans. 1995. Approximating the value of two power proof systems, with applications to MAX 2-SAT and MAX DI-CUT. In Proceedings of the 3rd Israel Symposium on Theoretical Computing Systems.182\u2013189."},{"issue":"6","key":"e_1_3_4_15_2","doi-asserted-by":"crossref","first-page":"1715","DOI":"10.1111\/j.1468-0262.2004.00551.x","article-title":"On optimal rules of persuasion","volume":"72","author":"Glazer Jacob","year":"2004","unstructured":"Jacob Glazer and Ariel Rubinstein. 2004. On optimal rules of persuasion. Econometrica 72, 6 (2004), 1715\u20131736.","journal-title":"Econometrica"},{"issue":"4","key":"e_1_3_4_16_2","first-page":"395","article-title":"A study in the pragmatics of persuasion: A game theoretical approach","volume":"1","author":"Glazer Jacob","year":"2006","unstructured":"Jacob Glazer and Ariel Rubinstein. 2006. A study in the pragmatics of persuasion: A game theoretical approach. Theor. Econ. 1, 4 (2006), 395\u2013410.","journal-title":"Theor. Econ."},{"key":"e_1_3_4_17_2","first-page":"422","volume-title":"Proceedings of the 26th Symposium on Theoretical Computing (STOC\u201994)","author":"Goemans Michel","year":"1994","unstructured":"Michel Goemans and David Williamson. 1994. .879-approximation algorithms for MAX CUT and MAX 2SAT. In Proceedings of the 26th Symposium on Theoretical Computing (STOC\u201994). 422\u2013431."},{"key":"e_1_3_4_18_2","doi-asserted-by":"crossref","unstructured":"Ronen Gradwohl Niklas Hahn Martin Hoefer and Rann Smorodinsky. 2022. Algorithms for persuasion with limited communication. Math. Oper. Res. 47 3 (2022) 2520\u20132545.","DOI":"10.1287\/moor.2021.1218"},{"issue":"3","key":"e_1_3_4_19_2","doi-asserted-by":"crossref","first-page":"461","DOI":"10.1086\/466995","article-title":"The informational role of warranties and private disclosure about product quality","volume":"24","author":"Grossman Sanford","year":"1981","unstructured":"Sanford Grossman. 1981. The informational role of warranties and private disclosure about product quality. J. Law Econ. 24, 3 (1981), 461\u2013483.","journal-title":"J. Law Econ."},{"key":"e_1_3_4_20_2","first-page":"175","volume-title":"Proceedings of the 29th International Joint Conference on Artificial Intelligence (IJCAI\u201920)","author":"Hahn Niklas","year":"2020","unstructured":"Niklas Hahn, Martin Hoefer, and Rann Smorodinsky. 2020. Prophet inequalities for bayesian persuasion. In Proceedings of the 29th International Joint Conference on Artificial Intelligence (IJCAI\u201920). 175\u2013181."},{"key":"e_1_3_4_21_2","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1145\/3391403.3399478","volume-title":"Proceedings of the 21st Conference on Economics and Computation (EC\u201920)","author":"Hahn Niklas","year":"2020","unstructured":"Niklas Hahn, Martin Hoefer, and Rann Smorodinsky. 2020. The secretary recommendation problem. In Proceedings of the 21st Conference on Economics and Computation (EC\u201920). 189."},{"issue":"1","key":"e_1_3_4_22_2","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1007\/BF02392825","article-title":"Clique is hard to approximate within  \\(n^{1-\\varepsilon }\\)","volume":"182","author":"H\u00e5stad Johan","year":"1999","unstructured":"Johan H\u00e5stad. 1999. Clique is hard to approximate within \\(n^{1-\\varepsilon }\\) . Acta Math. 182, 1 (1999), 105\u2013142.","journal-title":"Acta Math."},{"issue":"6","key":"e_1_3_4_23_2","doi-asserted-by":"crossref","first-page":"2590","DOI":"10.1257\/aer.101.6.2590","article-title":"Bayesian persuasion","volume":"101","author":"Kamenica Emir","year":"2011","unstructured":"Emir Kamenica and Matthew Gentzkow. 2011. Bayesian persuasion. Am. Econ. Rev. 101, 6 (2011), 2590\u20132615.","journal-title":"Am. Econ. Rev."},{"key":"e_1_3_4_24_2","first-page":"55:1\u201355:17","volume-title":"Proceedings of the 24th European Symposium on Algorithms (ESA\u201916)","author":"Khot Subhash","year":"2016","unstructured":"Subhash Khot and Rishi Saket. 2016. Hardness of bipartite expansion. In Proceedings of the 24th European Symposium on Algorithms (ESA\u201916). 55:1\u201355:17."},{"issue":"6","key":"e_1_3_4_25_2","doi-asserted-by":"crossref","first-page":"986","DOI":"10.1007\/s10458-013-9246-9","article-title":"On the value of commitment","volume":"28","author":"Letchford Joshua","year":"2014","unstructured":"Joshua Letchford, Dmytro Korzhyk, and Vincent Conitzer. 2014. On the value of commitment. Auton. Agents Multi-Agent Syst. 28, 6 (2014), 986\u20131016.","journal-title":"Auton. Agents Multi-Agent Syst."},{"key":"e_1_3_4_26_2","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1007\/3-540-47867-1_6","volume-title":"Proceedings of the International Conference on Integer Programming and Combinatorial Optimization (IPCO\u201902)","author":"Lewin Michael","year":"2002","unstructured":"Michael Lewin, Dror Livnat, and Uri Zwick. 2002. Improved rounding techniques for the MAX 2-SAT and MAX DI-CUT problems. In Proceedings of the International Conference on Integer Programming and Combinatorial Optimization (IPCO\u201902). 67\u201382."},{"key":"e_1_3_4_27_2","doi-asserted-by":"crossref","first-page":"380","DOI":"10.2307\/3003562","article-title":"Good news and bad news: Representation theorems and applications","author":"Milgrom Paul","year":"1981","unstructured":"Paul Milgrom. 1981. Good news and bad news: Representation theorems and applications. Bell J. Econ. (1981), 380\u2013391.","journal-title":"Bell J. Econ."},{"key":"e_1_3_4_28_2","first-page":"245","volume-title":"Proceedings of the 40th Symposium on Theoretical Computing (STOC\u201908)","author":"Raghavendra Prasad","year":"2008","unstructured":"Prasad Raghavendra. 2008. Optimal algorithms and inapproximability results for every CSP?. In Proceedings of the 40th Symposium on Theoretical Computing (STOC\u201908). 245\u2013254."},{"key":"e_1_3_4_29_2","first-page":"586","volume-title":"Proceedings of the 50th Symposium Foundations of Computer Science (FOCS\u201909)","author":"Raghavendra Prasad","year":"2009","unstructured":"Prasad Raghavendra and David Steurer. 2009. How to round any CSP. In Proceedings of the 50th Symposium Foundations of Computer Science (FOCS\u201909). 586\u2013594."},{"issue":"3","key":"e_1_3_4_30_2","doi-asserted-by":"crossref","first-page":"763","DOI":"10.1137\/S0097539795280895","article-title":"A parallel repetition theorem","volume":"27","author":"Raz Ran","year":"1998","unstructured":"Ran Raz. 1998. A parallel repetition theorem. SIAM J. Comput. 27, 3 (1998), 763\u2013803.","journal-title":"SIAM J. Comput."},{"issue":"2","key":"e_1_3_4_31_2","doi-asserted-by":"crossref","first-page":"409","DOI":"10.1016\/j.geb.2010.05.008","article-title":"Credibility and determinism in a game of persuasion","volume":"71","author":"Sher Itai","year":"2011","unstructured":"Itai Sher. 2011. Credibility and determinism in a game of persuasion. Games Econ. Behav. 71, 2 (2011), 409\u2013419.","journal-title":"Games Econ. Behav."},{"issue":"1","key":"e_1_3_4_32_2","doi-asserted-by":"crossref","first-page":"99","DOI":"10.3982\/TE683","article-title":"Persuasion and dynamic communication","volume":"9","author":"Sher Itai","year":"2014","unstructured":"Itai Sher. 2014. Persuasion and dynamic communication. Theor. Econ. 9, 1 (2014), 99\u2013136.","journal-title":"Theor. Econ."},{"key":"e_1_3_4_33_2","volume-title":"Rigorous Analysis of Approximation Algorithms for MAX 2-CSP","author":"Sj\u00f6gren Henrik","year":"2009","unstructured":"Henrik Sj\u00f6gren. 2009. Rigorous Analysis of Approximation Algorithms for MAX 2-CSP. Skolan f\u00f6r datavetenskap och kommunikation, Kungliga Tekniska h\u00f6gskolan."},{"key":"e_1_3_4_34_2","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1017\/CBO9781139060011.011","article-title":"Giving and receiving advice","volume":"1","author":"Sobel Joel","year":"2013","unstructured":"Joel Sobel. 2013. Giving and receiving advice. Adv. Econ. Econometr. 1 (2013), 305\u2013341.","journal-title":"Adv. Econ. Econometr."},{"issue":"2","key":"e_1_3_4_35_2","doi-asserted-by":"crossref","first-page":"374","DOI":"10.1016\/j.geb.2003.07.003","article-title":"The value of commitment in Stackelberg games with observation costs","volume":"49","author":"V\u00e1rdy Felix","year":"2004","unstructured":"Felix V\u00e1rdy. 2004. The value of commitment in Stackelberg games with observation costs. Games Econ. Behav. 49, 2 (2004), 374\u2013400.","journal-title":"Games Econ. Behav."}],"container-title":["ACM Transactions on Economics and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3696470","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3696470","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:10:14Z","timestamp":1750295414000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3696470"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,11,7]]},"references-count":34,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,12,31]]}},"alternative-id":["10.1145\/3696470"],"URL":"https:\/\/doi.org\/10.1145\/3696470","relation":{},"ISSN":["2167-8375","2167-8383"],"issn-type":[{"value":"2167-8375","type":"print"},{"value":"2167-8383","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,11,7]]},"assertion":[{"value":"2022-11-03","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-08-22","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-11-07","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}