{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T16:10:04Z","timestamp":1750695004139,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":42,"publisher":"ACM","funder":[{"name":"NSF","award":["FAI-2147212, CCF-2217062"],"award-info":[{"award-number":["FAI-2147212, CCF-2217062"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,6,15]]},"DOI":"10.1145\/3717823.3718222","type":"proceedings-article","created":{"date-parts":[[2025,6,15]],"date-time":"2025-06-15T22:21:27Z","timestamp":1750026087000},"page":"1532-1543","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Tractable Agreement Protocols"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0009-0006-2584-7728","authenticated-orcid":false,"given":"Natalie","family":"Collina","sequence":"first","affiliation":[{"name":"University of Pennsylvania, Philadelphia, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0385-9043","authenticated-orcid":false,"given":"Surbhi","family":"Goel","sequence":"additional","affiliation":[{"name":"University of Pennsylvania, Philadelphia, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6973-3876","authenticated-orcid":false,"given":"Varun","family":"Gupta","sequence":"additional","affiliation":[{"name":"University of Pennsylvania, Philadelphia, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0586-0515","authenticated-orcid":false,"given":"Aaron","family":"Roth","sequence":"additional","affiliation":[{"name":"University of Pennsylvania, Philadelphia, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060686"},{"key":"e_1_3_2_1_2_1","unstructured":"Rohan Alur Manish Raghavan and Devavrat Shah. 2024. Human Expertise in Algorithmic Prediction. arXiv preprint arXiv:2402.00793."},{"key":"e_1_3_2_1_3_1","volume-title":"IEEE Symposium on Discrete Algorithms (SODA), arxiv:2402","author":"Arunachaleswaran Eshwar Ram","year":"2025","unstructured":"Eshwar Ram Arunachaleswaran, Natalie Collina, Aaron Roth, and Mirah Shi. 2025. An Elementary Predictor Obtaining 2\u221a T+1 Distance to Calibration. IEEE Symposium on Discrete Algorithms (SODA), arxiv:2402.11410"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1214\/aos"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.2307\/2118364"},{"key":"e_1_3_2_1_6_1","volume-title":"Proceedings of the 55th Annual ACM Symposium on Theory of Computing. 1727\u20131740","author":"Jaros\u0142","year":"2023","unstructured":"Jaros\u0142 aw B\u0142 asiok, Parikshit Gopalan, Lunjia Hu, and Preetum Nakkiran. 2023. A unifying theory of distance from calibration. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing. 1727\u20131740."},{"volume-title":"Mechanisms for a no-regret agent: Beyond the common prior. In 2020 ieee 61st annual symposium on foundations of computer science (focs). 259\u2013270","author":"Camara Modibo K","key":"e_1_3_2_1_7_1","unstructured":"Modibo K Camara, Jason D Hartline, and Aleck Johnsen. 2020. Mechanisms for a no-regret agent: Beyond the common prior. In 2020 ieee 61st annual symposium on foundations of computer science (focs). 259\u2013270."},{"key":"e_1_3_2_1_8_1","volume-title":"The Twelfth International Conference on Learning Representations.","author":"Chan Chi-Min","year":"2024","unstructured":"Chi-Min Chan, Weize Chen, Yusheng Su, Jianxuan Yu, Wei Xue, Shanghang Zhang, Jie Fu, and Zhiyuan Liu. 2024. ChatEval: Towards Better LLM-based Evaluators through Multi-Agent Debate. In The Twelfth International Conference on Learning Representations."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3670865.3673460"},{"key":"e_1_3_2_1_10_1","unstructured":"Yuval Dagan Constantinos Daskalakis Maxwell Fishelson Noah Golowich Robert Kleinberg and Princewill Okoroafor. 2024. Improved bounds for calibration via stronger sign preservation games. arXiv preprint."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1982.10477856"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1214\/aos"},{"key":"e_1_3_2_1_13_1","unstructured":"Yash Deshpande Elchanan Mossel and Youngtak Sohn. 2022. Agreement and Statistical Efficiency in Bayesian Perception Models. arXiv preprint."},{"key":"e_1_3_2_1_14_1","volume-title":"Dung Daniel Ngo, and Zhiwei Steven Wu","author":"Du Ally Yalei","year":"2024","unstructured":"Ally Yalei Du, Dung Daniel Ngo, and Zhiwei Steven Wu. 2024. Reconciling Model Multiplicity for Downstream Decision Making. arXiv preprint."},{"key":"e_1_3_2_1_15_1","volume-title":"Forty-first International Conference on Machine Learning.","author":"Du Yilun","year":"2024","unstructured":"Yilun Du, Shuang Li, Antonio Torralba, Joshua B Tenenbaum, and Igor Mordatch. 2024. Improving Factuality and Reasoning in Language Models through Multiagent Debate. In Forty-first International Conference on Machine Learning."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/ITW.2006.1633786"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1006\/game.1999.0740"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1093\/biomet\/85.2.379"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3580507.3597679"},{"key":"e_1_3_2_1_20_1","volume-title":"Bayesian learning in social networks. Games and economic behavior, 45, 2","author":"Gale Douglas","year":"2003","unstructured":"Douglas Gale and Shachar Kariv. 2003. Bayesian learning in social networks. Games and economic behavior, 45, 2 (2003), 329\u2013346."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3328526.3329624"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0531(82)90099-0"},{"key":"e_1_3_2_1_23_1","unstructured":"Ira Globus-Harris Varun Gupta Michael Kearns and Aaron Roth. 2024. Model Ensembling for Constrained Optimization. arxiv:2405.16752. arxiv:2405.16752"},{"key":"e_1_3_2_1_24_1","volume-title":"Loss Minimization Through the Lens Of Outcome Indistinguishability. In 14th Innovations in Theoretical Computer Science Conference (ITCS","author":"Gopalan Parikshit","year":"2023","unstructured":"Parikshit Gopalan, Lunjia Hu, Michael P Kim, Omer Reingold, and Udi Wieder. 2023. Loss Minimization Through the Lens Of Outcome Indistinguishability. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)."},{"key":"e_1_3_2_1_25_1","unstructured":"Varun Gupta Christopher Jung Georgy Noarov Mallesh M Pai and Aaron Roth. 2022. Online Multivalid Learning: Means Moments and Prediction Intervals. Innovations in Theoretical Computer Science (ITCS)."},{"key":"e_1_3_2_1_26_1","volume-title":"International Conference on Machine Learning. 1939\u20131948","author":"H\u00e9bert-Johnson Ursula","year":"2018","unstructured":"Ursula H\u00e9bert-Johnson, Michael Kim, Omer Reingold, and Guy Rothblum. 2018. Multicalibration: Calibration for the (computationally-identifiable) masses. In International Conference on Machine Learning. 1939\u20131948."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS61266.2024.00024"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1257\/aer.101.6.2590"},{"key":"e_1_3_2_1_29_1","volume-title":"The Thirty Sixth Annual Conference on Learning Theory. 5143\u20135145","author":"Kleinberg Bobby","year":"2023","unstructured":"Bobby Kleinberg, Renato Paes Leme, Jon Schneider, and Yifeng Teng. 2023. U-calibration: Forecasting for an unknown agent. In The Thirty Sixth Annual Conference on Learning Theory. 5143\u20135145."},{"key":"e_1_3_2_1_30_1","volume-title":"14th Innovations in Theoretical Computer Science Conference (ITCS","author":"Kong Yuqing","year":"2023","unstructured":"Yuqing Kong and Grant Schoenebeck. 2023. False Consensus, Information Theory, and Prediction Markets. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). 251, 81."},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"crossref","unstructured":"Tian Liang Zhiwei He Wenxiang Jiao Xing Wang Yan Wang Rui Wang Yujiu Yang Zhaopeng Tu and Shuming Shi. 2023. Encouraging divergent thinking in large language models through multi-agent debate. arXiv preprint arXiv:2305.19118.","DOI":"10.18653\/v1\/2024.emnlp-main.992"},{"volume-title":"Repeated Games and Reputations: Long-Run Relationships","author":"Mailath George J","key":"e_1_3_2_1_32_1","unstructured":"George J Mailath and Larry Samuelson. 2006. Repeated Games and Reputations: Long-Run Relationships. Oxford University Press."},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-013-0479-y"},{"key":"e_1_3_2_1_34_1","unstructured":"Georgy Noarov Ramya Ramalingam Aaron Roth and Stephan Xie. 2023. High-Dimensional Prediction for Sequential Decision Making. arxiv:2310.17651. arxiv:2310.17651"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451050"},{"key":"e_1_3_2_1_36_1","unstructured":"Mingda Qiao and Letian Zheng. 2024. On the Distance from Calibration in Sequential Prediction. arXiv preprint arXiv:2402.07458."},{"key":"e_1_3_2_1_37_1","volume-title":"Forecasting for Swap Regret for All Downstream Agents. ACM Conference on Economics and Computation (EC).","author":"Roth Aaron","year":"2024","unstructured":"Aaron Roth and Mirah Shi. 2024. Forecasting for Swap Regret for All Downstream Agents. ACM Conference on Economics and Computation (EC)."},{"key":"e_1_3_2_1_38_1","unstructured":"Aaron Roth Alexander Tolbert and Scott Weinstein. 2023. Reconciling Individual Probability Forecasts. arxiv:2209.01687. arxiv:2209.01687"},{"key":"e_1_3_2_1_39_1","volume-title":"Calibration with many checking rules. Mathematics of operations Research, 28, 1","author":"Sandroni Alvaro","year":"2003","unstructured":"Alvaro Sandroni, Rann Smorodinsky, and Rakesh V Vohra. 2003. Calibration with many checking rules. Mathematics of operations Research, 28, 1 (2003), 141\u2013153."},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"crossref","unstructured":"Herbert A Simon. 1955. A behavioral model of rational choice. The quarterly journal of economics 99\u2013118.","DOI":"10.2307\/1884852"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00122574"},{"key":"e_1_3_2_1_42_1","first-page":"22313","article-title":"Calibrating predictions to decisions: A novel approach to multi-class calibration","volume":"34","author":"Zhao Shengjia","year":"2021","unstructured":"Shengjia Zhao, Michael Kim, Roshni Sahoo, Tengyu Ma, and Stefano Ermon. 2021. Calibrating predictions to decisions: A novel approach to multi-class calibration. Advances in Neural Information Processing Systems, 34 (2021), 22313\u201322324.","journal-title":"Advances in Neural Information Processing Systems"}],"event":{"name":"STOC '25: 57th Annual ACM Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Prague Czechia","acronym":"STOC '25"},"container-title":["Proceedings of the 57th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3717823.3718222","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T15:44:31Z","timestamp":1750693471000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3717823.3718222"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,15]]},"references-count":42,"alternative-id":["10.1145\/3717823.3718222","10.1145\/3717823"],"URL":"https:\/\/doi.org\/10.1145\/3717823.3718222","relation":{},"subject":[],"published":{"date-parts":[[2025,6,15]]},"assertion":[{"value":"2025-06-15","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}