{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,13]],"date-time":"2026-07-13T23:22:25Z","timestamp":1783984945301,"version":"3.55.0"},"reference-count":54,"publisher":"Association for Computing Machinery (ACM)","issue":"2","funder":[{"DOI":"10.13039\/100019180","name":"HORIZON EUROPE European Research Council","doi-asserted-by":"publisher","award":["101170373"],"award-info":[{"award-number":["101170373"]}],"id":[{"id":"10.13039\/100019180","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Israeli Science Foundation Breakthrough Program","award":["2600\/24"],"award-info":[{"award-number":["2600\/24"]}]},{"name":"NSF-BSF","award":["2020788"],"award-info":[{"award-number":["2020788"]}]},{"DOI":"10.13039\/100021154","name":"Amazon Research Awards","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100021154","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2026,4,30]]},"abstract":"<jats:p>\n                    We study a natural combinatorial single-principal multi-agent contract design problem, in which a principal motivates a team of agents to exert effort toward a given task. At the heart of our model is a\n                    <jats:italic toggle=\"yes\">reward function<\/jats:italic>\n                    , which maps the agent efforts to an expected reward of the principal. We seek to design computationally efficient algorithms for finding optimal (or near-optimal) linear contracts for reward functions that belong to the complement-free hierarchy.\n                  <\/jats:p>\n                  <jats:p>Our first main result gives constant-factor approximation algorithms for submodular and XOS reward functions, with value oracles for submodular reward functions and value and demand oracles for XOS reward functions. It relies on an unconventional use of \u201cprices\u201d and (approximate) demand queries for selecting the set of agents that the principal should contract with, and exploits a novel scaling property of XOS functions and their marginals, which may be of independent interest.<\/jats:p>\n                  <jats:p>\n                    As our second main result, we show that constant approximation is the best we can get for submodular reward functions, even with both value and demand oracles. For the larger class of subadditive reward functions, we establish an\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\Omega (\\sqrt {n})\\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    impossibility for settings with\n                    <jats:italic toggle=\"yes\">n<\/jats:italic>\n                    agents. A striking feature of this impossibility is that it applies to subadditive functions that are constant-factor close to submodular. This rapid degradation presents a surprising departure from previous literature, e.g., on combinatorial auctions, where approximation guarantees tend to deteriorate more gracefully.\n                  <\/jats:p>","DOI":"10.1145\/3801154","type":"journal-article","created":{"date-parts":[[2026,3,11]],"date-time":"2026-03-11T21:10:08Z","timestamp":1773263408000},"page":"1-37","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Multi-Agent Contracts"],"prefix":"10.1145","volume":"73","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0635-6812","authenticated-orcid":false,"given":"Paul","family":"D\u00fctting","sequence":"first","affiliation":[{"name":"Google Research","place":["Zurich, Switzerland"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0626-4851","authenticated-orcid":false,"given":"Tomer","family":"Ezra","sequence":"additional","affiliation":[{"name":"School of Mathematical Sciences, Tel Aviv University","place":["Tel Aviv-Yafo, Israel"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2915-8405","authenticated-orcid":false,"given":"Michal","family":"Feldman","sequence":"additional","affiliation":[{"name":"Blavatnik School of Computer Science, Tel Aviv University","place":["Tel Aviv-Yafo, Israel"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9420-9424","authenticated-orcid":false,"given":"Thomas","family":"Kesselheim","sequence":"additional","affiliation":[{"name":"Institute of Computer Science, University of Bonn","place":["Bonn, Germany"]}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,4,22]]},"reference":[{"key":"e_1_3_3_2_1","first-page":"895","volume-title":"Proc. EC 2025","author":"Aharoni Gil","year":"2025","unstructured":"Gil Aharoni, Martin Hoefer, and Inbal Talgam-Cohen. 2025. Welfare and beyond in multi-agent contracts. In Proc. EC 2025. ACM, New York, USA, 895."},{"key":"e_1_3_3_3_1","first-page":"580","volume-title":"Proc. EC 2025","author":"Alon Tal","year":"2025","unstructured":"Tal Alon, Matteo Castiglioni, Junjie Chen, Tomer Ezra, Yingkai Li, and Inbal Talgam-Cohen. 2025. Multi-project contracts. In Proc. EC 2025. ACM, New York, USA, 580\u2013598."},{"key":"e_1_3_3_4_1","first-page":"653","volume-title":"Proc. SODA 2021","author":"Assadi Sepehr","year":"2021","unstructured":"Sepehr Assadi, Thomas Kesselheim, and Sahil Singla. 2021. Improved truthful mechanisms for subadditive combinatorial auctions: Breaking the logarithmic barrier. In Proc. SODA 2021. ACM-SIAM, New York & Philadelphia, USA, 653\u2013661."},{"key":"e_1_3_3_5_1","first-page":"18","volume-title":"Proc. EC 2006","author":"Babaioff Moshe","year":"2006","unstructured":"Moshe Babaioff, Michal Feldman, and Noam Nisan. 2006. Combinatorial agency. In Proc. EC 2006. ACM, New York, USA, 18\u201328."},{"key":"e_1_3_3_6_1","first-page":"109","volume-title":"Proc. SAGT 2009","author":"Babaioff Moshe","year":"2009","unstructured":"Moshe Babaioff, Michal Feldman, and Noam Nisan. 2009. Free-riding and free-labor in combinatorial agency. In Proc. SAGT 2009. Springer, Berlin, Germany, 109\u2013121."},{"issue":"1","key":"e_1_3_3_7_1","first-page":"339","article-title":"Mixed strategies in combinatorial agency","volume":"38","author":"Babaioff Moshe","year":"2010","unstructured":"Moshe Babaioff, Michal Feldman, and Noam Nisan. 2010. Mixed strategies in combinatorial agency. J. Artif. Intell. 38, 1 (2010), 339\u2013369.","journal-title":"J. Artif. Intell."},{"key":"e_1_3_3_8_1","first-page":"1691","volume-title":"Proc. ICML 2022","author":"Bechavod Yahav","year":"2022","unstructured":"Yahav Bechavod, Chara Podimata, Zhiwei Steven Wu, and Juba Ziani. 2022. Information discrepancy in strategic learning. In Proc. ICML 2022. PMLR, New York, USA, 1691\u20131715."},{"key":"e_1_3_3_9_1","first-page":"666","volume-title":"Proc. EC 2022","author":"Bechtel Curtis","year":"2022","unstructured":"Curtis Bechtel, Shaddin Dughmi, and Neel Patel. 2022. Delegated pandora\u2019s box. In Proc. EC 2022. ACM, New York, USA, 666\u2013693."},{"key":"e_1_3_3_10_1","first-page":"700","volume-title":"Proc. SODA 2011","author":"Bhawalkar Kshipra","year":"2011","unstructured":"Kshipra Bhawalkar and Tim Roughgarden. 2011. Welfare guarantees for combinatorial auctions with item bidding. In Proc. SODA 2011. ACM-SIAM, New York & Philadelphia, USA, 700\u2013709."},{"key":"e_1_3_3_11_1","first-page":"1293","volume-title":"Proc. EC 2024","author":"Cacciamani Federico","year":"2024","unstructured":"Federico Cacciamani, Martino Bernasconi, Matteo Castiglioni, and Nicola Gatti. 2024. Multi-agent contract design beyond binary actions. In Proc. EC 2024. ACM, New York, USA, 1293."},{"key":"e_1_3_3_12_1","first-page":"704","volume-title":"Proc. STOC 2022","author":"Cai Yang","year":"2022","unstructured":"Yang Cai, Argyris Oikonomou, and Mingfei Zhao. 2022. Computing simple mechanisms: Lift-and-round over marginal reduced forms. In Proc. STOC 2022. ACM, New York, USA, 704\u2013717."},{"key":"e_1_3_3_13_1","first-page":"412","volume-title":"Proc. EC 2023","author":"Castiglioni Matteo","year":"2023","unstructured":"Matteo Castiglioni, Alberto Marchesi, and Nicola Gatti. 2023. Multi-agent contract design: How to commission multiple agents with individual outcomes. In Proc. EC 2023. ACM, New York, USA, 412\u2013448."},{"key":"e_1_3_3_14_1","first-page":"311","volume-title":"Proc. STOC 2010","author":"Chawla Shuchi","year":"2010","unstructured":"Shuchi Chawla, Jason D. Hartline, David L. Malec, and Balasubramanian Sivan. 2010. Multi-parameter mechanism design and sequential posted pricing. In Proc. STOC 2010. ACM, New York, USA, 311\u2013320."},{"key":"e_1_3_3_15_1","first-page":"383","volume-title":"Proc. WINE 2024","author":"Chen Yiling","year":"2024","unstructured":"Yiling Chen and Fang-Yi Yu. 2024. Optimal scoring rule design under partial knowledge. In Proc. WINE 2024. Springer, Berlin, Germany, 383\u2013400."},{"issue":"2","key":"e_1_3_3_16_1","first-page":"11:1\u201311:19","article-title":"Bayesian combinatorial auctions","volume":"63","author":"Christodoulou George","year":"2016","unstructured":"George Christodoulou, Annam\u00e1ria Kov\u00e1cs, and Michael Schapira. 2016. Bayesian combinatorial auctions. J. ACM 63, 2 (2016), 11:1\u201311:19.","journal-title":"J. ACM"},{"key":"e_1_3_3_17_1","first-page":"686","volume-title":"Proc. STOC 2023","author":"Correa Jos\u00e9","year":"2023","unstructured":"Jos\u00e9 Correa and Andr\u00e9s Cristi. 2023. A constant factor prophet inequality for online combinatorial auctions. In Proc. STOC 2023. ACM, New York, USA, 686\u2013697."},{"key":"e_1_3_3_18_1","first-page":"505","volume-title":"Proc. EC 2025","author":"Dasaratha Krishna","year":"2025","unstructured":"Krishna Dasaratha, Benjamin Golub, and Anant Shah. 2025. Incentive design with spillovers. In Proc. EC 2025. ACM, New York, USA, 505."},{"key":"e_1_3_3_19_1","first-page":"109","volume-title":"Proc. SODA 2024","author":"Vuong Ramiro Deo-Campo","year":"2024","unstructured":"Ramiro Deo-Campo Vuong, Shaddin Dughmi, Neel Patel, and Aditya Prasad. 2024. On supermodular contracts and dense subgraphs. In Proc. SODA 2024. ACM-SIAM, New York & Philadelphia, USA, 109\u2013132."},{"issue":"3","key":"e_1_3_3_20_1","first-page":"STOC16\u20131\u2013STOC16","article-title":"Breaking the logarithmic barrier for truthful combinatorial auctions with submodular bidders","volume":"50","author":"Dobzinski Shahar","year":"2021","unstructured":"Shahar Dobzinski. 2021. Breaking the logarithmic barrier for truthful combinatorial auctions with submodular bidders. SIAM J. Comput. 50, 3 (2021), STOC16\u20131\u2013STOC16\u201317.","journal-title":"SIAM J. Comput."},{"key":"e_1_3_3_21_1","first-page":"1311","volume-title":"Proc. STOC 2023","author":"D\u00fctting Paul","year":"2023","unstructured":"Paul D\u00fctting, Tomer Ezra, Michal Feldman, and Thomas Kesselheim. 2023. Multi-agent contracts. In Proc. STOC 2023. ACM, New York, USA, 1311\u20131324."},{"key":"e_1_3_3_22_1","article-title":"Black-box lifting and robustness theorems for multi-agent contracts","author":"D\u00fctting Paul","year":"2025","unstructured":"Paul D\u00fctting, Tomer Ezra, Michal Feldman, and Thomas Kesselheim. 2025a. Black-box lifting and robustness theorems for multi-agent contracts. arXiv:2511.19358. Retrieved from https:\/\/arxiv.org\/abs\/2511.19358 (2025).","journal-title":"arXiv:2511.19358"},{"key":"e_1_3_3_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/23M1611828"},{"key":"e_1_3_3_24_1","first-page":"1857","volume-title":"Proc. SODA 2025","author":"D\u00fctting Paul","year":"2025","unstructured":"Paul D\u00fctting, Tomer Ezra, Michal Feldman, and Thomas Kesselheim. 2025c. Multi-agent combinatorial contracts. In Proc. SODA 2025. ACM-SIAM, New York & Philadelphia, USA, 1857\u20131891."},{"key":"e_1_3_3_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/20M1323850"},{"key":"e_1_3_3_26_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000113"},{"key":"e_1_3_3_27_1","first-page":"369","volume-title":"Proc. EC 2019","author":"D\u00fctting Paul","year":"2019","unstructured":"Paul D\u00fctting, Tim Roughgarden, and Inbal Talgam-Cohen. 2019. Simple versus optimal contracts. In Proc. EC 2019. ACM, New York, USA, 369\u2013387."},{"key":"e_1_3_3_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/20M132153X"},{"key":"e_1_3_3_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.05.018"},{"key":"e_1_3_3_30_1","first-page":"44:1\u201344:22","volume-title":"Proc. ITCS 2024","author":"Ezra Tomer","year":"2024","unstructured":"Tomer Ezra, Michal Feldman, and Maya Schlesinger. 2024. On the (In)approximability of combinatorial contracts. In Proc. ITCS 2024. Schloss Dagstuhl - Leibniz Center for Informatics, Wadern, Germany, 44:1\u201344:22."},{"key":"e_1_3_3_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/070680977"},{"key":"e_1_3_3_32_1","article-title":"Combinatorial contract design: Recent progress and emerging frontiers","author":"Feldman Michal","year":"2025","unstructured":"Michal Feldman. 2025. Combinatorial contract design: Recent progress and emerging frontiers. arXiv:2510.15065. Retrieved from https:\/\/arxiv.org\/abs\/2510.15065 (2025).","journal-title":"arXiv:2510.15065"},{"key":"e_1_3_3_33_1","first-page":"201","volume-title":"Proc. STOC 2013","author":"Feldman Michal","year":"2013","unstructured":"Michal Feldman, Hu Fu, Nick Gravin, and Brendan Lucier. 2013. Simultaneous auctions are (almost) efficient. In Proc. STOC 2013. ACM, New York, USA, 201\u2013210."},{"key":"e_1_3_3_34_1","first-page":"58:1\u201358:24","volume-title":"Proc. ITCS 2026","author":"Feldman Michal","year":"2026","unstructured":"Michal Feldman, Yoav Gal-Tzur, Tomasz Ponitka, and Maya Schlesinger. 2026. One action too many: Inapproximability of budgeted combinatorial contracts. In Proc. ITCS 2026. Schloss Dagstuhl - Leibniz Center for Informatics, Wadern, Germany, 58:1\u201358:24."},{"key":"e_1_3_3_35_1","first-page":"123","volume-title":"Proc. SODA 2015","author":"Feldman Michal","year":"2015","unstructured":"Michal Feldman, Nick Gravin, and Brendan Lucier. 2015. Combinatorial auctions via posted prices. In Proc. SODA 2015. ACM-SIAM, New York & Philadelphia, USA, 123\u2013135."},{"key":"e_1_3_3_36_1","first-page":"353","volume-title":"Proc. EC 2025","author":"Feldman Michal","year":"2025","unstructured":"Michal Feldman, Yoav Gal Tzur, Tomasz Ponitka, and Maya Schlesinger. 2025. Budget-feasible contracts. In Proc. EC 2025. ACM, New York, USA, 353."},{"key":"e_1_3_3_37_1","first-page":"586","volume-title":"Proc. EC 2012","author":"Fu Hu","year":"2012","unstructured":"Hu Fu, Robert Kleinberg, and Ron Lavi. 2012. Conditional equilibrium outcomes via ascending price processes with applications to combinatorial auctions with item bidding. In Proc. EC 2012. ACM, New York, USA, 586."},{"key":"e_1_3_3_38_1","article-title":"Multi-agent contract design with a budget","author":"Goel Sumit","year":"2024","unstructured":"Sumit Goel and Hann Caruthers-Wade. 2024. Multi-agent contract design with a budget. arXiv:2402.15890. Retrieved from https:\/\/arxiv.org\/abs\/2402.15890 (2024).","journal-title":"arXiv:2402.15890"},{"key":"e_1_3_3_39_1","article-title":"Principal-agent meets a cardinality","author":"Gong Qinqin","year":"2024","unstructured":"Qinqin Gong, Ling Gai, Yang Lv, and Ruiqi Yang. 2024. Principal-agent meets a cardinality. Preprint SSRN:4581020. Retrieved from https:\/\/ssrn.com\/abstract=4581020","journal-title":"Preprint SSRN:4581020"},{"key":"e_1_3_3_40_1","doi-asserted-by":"publisher","DOI":"10.2307\/1912246"},{"key":"e_1_3_3_41_1","doi-asserted-by":"publisher","DOI":"10.1006\/jeth.1999.2531"},{"key":"e_1_3_3_42_1","first-page":"2634","volume-title":"Proc. ICML 2019","author":"Harshaw Chris","year":"2019","unstructured":"Chris Harshaw, Moran Feldman, Justin Ward, and Amin Karbasi. 2019. Submodular maximization beyond non-negativity: Guarantees, fast algorithms, and applications. In Proc. ICML 2019. PMLR, New York, USA, 2634\u20132643."},{"key":"e_1_3_3_43_1","doi-asserted-by":"publisher","DOI":"10.2307\/3003320"},{"key":"e_1_3_3_44_1","doi-asserted-by":"publisher","DOI":"10.2307\/3003457"},{"key":"e_1_3_3_45_1","first-page":"287","volume-title":"Proc. EC 2018","author":"Kleinberg Jon M.","year":"2018","unstructured":"Jon M. Kleinberg and Robert Kleinberg. 2018. Delegated search approximates efficient search. In Proc. EC 2018. ACM, New York, USA, 287\u2013302."},{"key":"e_1_3_3_46_1","first-page":"825","volume-title":"Proc. EC 2019","author":"Kleinberg Jon M.","year":"2019","unstructured":"Jon M. Kleinberg and Manish Raghavan. 2019. How do classifiers induce agents to invest effort strategically?. In Proc. EC 2019. ACM, New York, USA, 825\u2013844."},{"key":"e_1_3_3_47_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2005.02.006"},{"key":"e_1_3_3_48_1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.2021.4273"},{"key":"e_1_3_3_49_1","first-page":"113","volume-title":"Proc. WINE 2021","author":"Li Wanyi Dai","year":"2021","unstructured":"Wanyi Dai Li, Nicole Immorlica, and Brendan Lucier. 2021. Contract design for afforestation programs. In Proc. WINE 2021. Springer, Berlin, Germany, 113\u2013130."},{"key":"e_1_3_3_50_1","first-page":"988","volume-title":"Proc. EC 2022","author":"Li Yingkai","year":"2022","unstructured":"Yingkai Li, Jason D. Hartline, Liren Shan, and Yifan Wu. 2022. Optimization of scoring rules. In Proc. EC 2022. ACM, New York, USA, 988\u2013989."},{"issue":"4","key":"e_1_3_3_51_1","doi-asserted-by":"crossref","first-page":"767","DOI":"10.1007\/s00199-001-0248-5","article-title":"Verifying gross substitutability","volume":"20","author":"Reijnierse H.","year":"2002","unstructured":"H. Reijnierse, J. Potters, and A. Gellekom. 2002. Verifying gross substitutability. Econ. Theory 20, 4 (2002), 767\u2013776.","journal-title":"Econ. Theory"},{"key":"e_1_3_3_52_1","unstructured":"Statista. 2021. Instagram Influencer Marketing Spending Worldwide From 2013 to 2020. Retrieved from https:\/\/www.statista.com\/statistics\/950920\/global-instagram-influencer-marketing-spending\/"},{"key":"e_1_3_3_53_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2016.0842"},{"key":"e_1_3_3_54_1","first-page":"211","volume-title":"Proc. STOC 2013","author":"Syrgkanis Vasilis","year":"2013","unstructured":"Vasilis Syrgkanis and \u00c9va Tardos. 2013. Composable and efficient mechanisms. In Proc. STOC 2013. ACM, New York, USA, 211\u2013220."},{"key":"e_1_3_3_55_1","first-page":"92","volume-title":"Proc. SODA 2015","author":"Yao Andrew Chi-Chih","year":"2015","unstructured":"Andrew Chi-Chih Yao. 2015. An n-to-1 bidder reduction for multi-item auctions and its applications. In Proc. SODA 2015. ACM-SIAM, New York & Philadelphia, USA, 92\u2013109."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3801154","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T16:34:41Z","timestamp":1776875681000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3801154"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,4,22]]},"references-count":54,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,4,30]]}},"alternative-id":["10.1145\/3801154"],"URL":"https:\/\/doi.org\/10.1145\/3801154","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,4,22]]},"assertion":[{"value":"2025-03-10","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-02-21","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-04-22","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}