{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:36:17Z","timestamp":1787340977507,"version":"build-2736575974"},"reference-count":45,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"6","funder":[{"DOI":"10.13039\/100010661","name":"Horizon 2020 Framework Programme","doi-asserted-by":"publisher","award":["866132"],"award-info":[{"award-number":["866132"]}],"id":[{"id":"10.13039\/100010661","id-type":"DOI","asserted-by":"publisher"}]},{"name":"European Union\u2019s Horizon Europe Program","award":["101170373"],"award-info":[{"award-number":["101170373"]}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["2020788"],"award-info":[{"award-number":["2020788"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["2600\/24"],"award-info":[{"award-number":["2600\/24"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"name":"TAU Center for AI and Data Science"},{"DOI":"10.13039\/100007229","name":"Harvard University","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100007229","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2025,12,31]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>We introduce a new model of combinatorial contracts in which a principal delegates the execution of a costly task to an agent. To complete the task, the agent can take any subset of a given set of unobservable actions, each of which has an associated cost. The cost of a set of actions is the sum of the costs of the individual actions, and the principal\u2019s reward as a function of the chosen actions satisfies some form of diminishing returns. The principal incentivizes the agents through a contract based on the observed outcome. Our main results are for the case where the task delegated to the agent is a project, which can be successful or not. We show that if the success probability as a function of the set of actions is gross substitutes, then an optimal contract can be computed with polynomially many value queries, whereas if it is submodular, the optimal contract is NP-hard. All our results extend to linear contracts for higher-dimensional outcome spaces, which we show to be robustly optimal given first moment constraints. Our analysis uncovers a new property of gross substitutes functions and reveals many interesting connections between combinatorial contracts and combinatorial auctions, where gross substitutes is known to be the frontier for efficient computation.<\/jats:p>","DOI":"10.1137\/23m1611828","type":"journal-article","created":{"date-parts":[[2025,12,2]],"date-time":"2025-12-02T08:27:56Z","timestamp":1764664076000},"page":"1427-1455","source":"Crossref","is-referenced-by-count":2,"title":["Combinatorial Contracts"],"prefix":"10.1137","volume":"54","author":[{"given":"Paul","family":"D\u00fctting","sequence":"first","affiliation":[{"name":"Google Research, Z\u00fcrich, 8002 Switzerland."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tomer","family":"Ezra","sequence":"additional","affiliation":[{"name":"Harvard University, Boston, USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michal","family":"Feldman","sequence":"additional","affiliation":[{"name":"Computer Science, Tel Aviv University, Tel Aviv, Israel, and Microsoft ILDC, Israel."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9420-9424","authenticated-orcid":true,"given":"Thomas","family":"Kesselheim","sequence":"additional","affiliation":[{"name":"Institute of Computer Science, University of Bonn, Bonn, 53115 Germany."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2025,12,2]]},"reference":[{"key":"ref1","doi-asserted-by":"crossref","unstructured":"T. Alon, P. D\u00fctting, Y. Li, and I. Talgam-Cohen, Bayesian analysis of linear contracts, in Proc. of ACM EC\u201923, 2023, p. 66.","DOI":"10.1145\/3580507.3597795"},{"key":"ref2","doi-asserted-by":"crossref","unstructured":"T. Alon, P. D\u00fctting, and I. Talgam-Cohen, Contracts with private cost per unit-of-effort, in Proc. of ACM EC\u201921, 2021, pp. 52\u201369.","DOI":"10.1145\/3465456.3467651"},{"key":"ref3","doi-asserted-by":"crossref","unstructured":"M. Babaioff, M. Feldman, and N. Nisan, Free-riding and free-labor in combinatorial agency, in Proc. of SAGT\u201909, 2009, pp. 109\u2013121.","DOI":"10.1007\/978-3-642-04645-2_11"},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1613\/jair.2961"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1016\/j.jet.2012.01.010"},{"key":"ref6","doi-asserted-by":"crossref","unstructured":"E. Balkanski and R. P. Leme, On the construction of substitutes, in Proc. of ACM EC\u201918, 2018, p. 643.","DOI":"10.1145\/3219166.3219184"},{"key":"ref7","unstructured":"C. Bechtel and S. Dughmi, Delegated stochastic probing, in Proc. of ITCS\u201921, 2021, 37, pp. 37:1\u201337:19."},{"key":"ref8","doi-asserted-by":"crossref","unstructured":"C. Bechtel, S. Dughmi, and N. Patel, Delegated pandora\u2019s box, in Proc. of ACM EC\u201922, 2022, pp. 666\u2013693.","DOI":"10.1145\/3490486.3538267"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1257\/aer.20131159"},{"key":"ref10","doi-asserted-by":"crossref","unstructured":"M. Castiglioni, A. Marchesi, and N. Gatti, Bayesian agency: Linear versus tractable contracts, in Proc. of ACM EC\u201921, 2021, pp. 285\u2013286.","DOI":"10.1145\/3465456.3467602"},{"key":"ref11","doi-asserted-by":"crossref","unstructured":"R. Deo-Campo Vuong, S. Dughmi, N. Patel, and A. Prasad, On supermodular contracts and dense subgraphs, in Proc. of ACM-SIAM SODA\u201924, 2024, pp. 109\u2013132.","DOI":"10.1137\/1.9781611977912.6"},{"key":"ref12","doi-asserted-by":"crossref","unstructured":"S. Dobzinski, U. Feige, and M. Feldman, Are gross substitutes a substitute for submodular valuations? in Proc. of ACM EC\u201921, 2021, pp. 390\u2013408.","DOI":"10.1145\/3465456.3467615"},{"key":"ref13","doi-asserted-by":"crossref","unstructured":"P. D\u00fctting, T. Ezra, M. Feldman, and T. Kesselheim, Multi-agent contracts, in Proc. of ACM STOC\u201923, 2023, pp. 1311\u20131324.","DOI":"10.1145\/3564246.3585193"},{"key":"ref14","doi-asserted-by":"crossref","unstructured":"P. D\u00fctting, T. Ezra, M. Feldman, and T. Kesselheim, Multi-agent combinatorial contracts, in Proc. of ACM-SIAM SODA\u201925, 2025, pp. 1857\u20131891.","DOI":"10.1137\/1.9781611978322.58"},{"key":"ref15","doi-asserted-by":"crossref","unstructured":"P. D\u00fctting, M. Feldman, and Y. Gal Tzur, Combinatorial contracts beyond gross substitutes, in Proc. of ACM-SIAM SODA\u201924, 2024, pp. 92\u2013108.","DOI":"10.1137\/1.9781611977912.5"},{"key":"ref16","doi-asserted-by":"crossref","unstructured":"P. D\u00fctting, M. Feldman, T. Ponitka, and E. Soumalias, The pseudo-dimension of contracts, in Proc. of ACM EC\u201925, 2025, pp. 514\u2013539.","DOI":"10.1145\/3736252.3742585"},{"key":"ref17","unstructured":"P. D\u00fctting, M. Feldman, Y. G. Tzur, and A. Rubinstein, The Query Complexity of Contracts, CoRR, https:\/\/arxiv.org\/abs\/2403.09794, 2024."},{"key":"ref18","unstructured":"P. D\u00fctting, G. Guruganesh, J. Schneider, and J. R. Wang, Optimal no-regret learning for one-sided lipschitz functions, in Proc. of ICML\u201923, 2023, pp. 8836\u20138850."},{"key":"ref19","doi-asserted-by":"crossref","unstructured":"P. D\u00fctting, T. Roughgarden, and I. Talgam-Cohen, Simple versus optimal contracts, in Proc. of ACM EC\u201919, 2019, pp. 369\u2013387.","DOI":"10.1145\/3328526.3329591"},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1137\/20M132153X"},{"key":"ref21","unstructured":"T. Ezra, M. Feldman, and M. Schlesinger, On the (in)approximability of combinatorial contracts, in Proc. of ITCS\u201924, 2024, 44, pp. 44:1\u201344:22."},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1109\/JSAC.2007.070810"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.2307\/1912246"},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1006\/jeth.1999.2531"},{"key":"ref25","doi-asserted-by":"crossref","unstructured":"G. Guruganesh, J. Schneider, and J. Wang, Contracts under moral hazard and adverse selection, in Proc. of ACM EC\u201921, 2021, pp. 563\u2013582.","DOI":"10.1145\/3465456.3467637"},{"key":"ref26","unstructured":"J. D. Hartline, L. Shan, Y. Li, and Y. Wu, Optimal scoring rules for multi-dimensional effort, in Proc. of COLT\u201923, 2023, pp. 2624\u20132650."},{"key":"ref27","doi-asserted-by":"publisher","DOI":"10.1613\/jair.4940"},{"key":"ref28","doi-asserted-by":"publisher","DOI":"10.2307\/3003320"},{"key":"ref29","doi-asserted-by":"publisher","DOI":"10.2307\/1913238"},{"key":"ref30","doi-asserted-by":"publisher","DOI":"10.1093\/jleo\/7.special_issue.24"},{"key":"ref31","doi-asserted-by":"publisher","DOI":"10.1145\/3434415"},{"key":"ref32","doi-asserted-by":"publisher","DOI":"10.2307\/1913392"},{"key":"ref33","doi-asserted-by":"crossref","unstructured":"J. M. Kleinberg and R. Kleinberg, Delegated search approximates efficient search, in Proc. of ACM EC\u201918, 2018, pp. 287\u2013302.","DOI":"10.1145\/3219166.3219205"},{"key":"ref34","doi-asserted-by":"crossref","unstructured":"J. M. Kleinberg and M. Raghavan, How do classifiers induce agents to invest effort strategically? in Proc. of ACM EC\u201919, 2019, pp. 825\u2013844.","DOI":"10.1145\/3328526.3329584"},{"key":"ref35","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(02)00455-6"},{"key":"ref36","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2005.02.006"},{"key":"ref37","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2017.10.016"},{"key":"ref38","doi-asserted-by":"crossref","unstructured":"Y. Li, J. D. Hartline, L. Shan, and Y. Wu, Optimization of scoring rules, in Proc. of ACM EC\u201922, 2022, pp. 988\u2013989.","DOI":"10.1145\/3490486.3538338"},{"key":"ref39","doi-asserted-by":"crossref","unstructured":"K. Murota, Convexity and steinitz\u2019s exchange property, in Proc. of IPCO\u201996, 1996, pp. 260\u2013274.","DOI":"10.1007\/3-540-61310-2_20"},{"key":"ref40","first-page":"151","volume":"1","author":"Murota K.","year":"2016","journal-title":"J. Mech. Inst. Des."},{"key":"ref41","doi-asserted-by":"publisher","DOI":"10.1287\/moor.24.1.95"},{"key":"ref42","doi-asserted-by":"publisher","DOI":"10.1016\/j.jet.2004.10.007"},{"key":"ref43","volume-title":"Scientific background on the 2016 Nobel Prize in Economic Sciences","author":"Royal Swedish Academy of Sciences","year":"2016"},{"key":"ref44","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.1030.0147"},{"key":"ref45","doi-asserted-by":"crossref","unstructured":"B. Zhu, S. Bates, Z. Yang, Y. Wang, J. Jiao, and M. I. Jordan, The sample complexity of online contract design, in Proc. of ACM EC\u201923, 2023, 1188.","DOI":"10.1145\/3580507.3597673"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/23M1611828","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:59:14Z","timestamp":1787338754000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/23M1611828"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,12,2]]},"references-count":45,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2025,12,31]]}},"alternative-id":["10.1137\/23M1611828"],"URL":"https:\/\/doi.org\/10.1137\/23m1611828","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,12,2]]}}}