{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,28]],"date-time":"2026-02-28T17:30:56Z","timestamp":1772299856384,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":55,"publisher":"ACM","funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["866132"],"award-info":[{"award-number":["866132"]}],"id":[{"id":"10.13039\/501100000781","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":"NSF-BSF","award":["2020788"],"award-info":[{"award-number":["2020788"]}]},{"name":"TAU Center for AI and Data Science"},{"name":"Amazon"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,7,7]]},"DOI":"10.1145\/3736252.3742585","type":"proceedings-article","created":{"date-parts":[[2025,7,2]],"date-time":"2025-07-02T18:48:05Z","timestamp":1751482085000},"page":"514-539","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["The Pseudo-Dimension of Contracts"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0635-6812","authenticated-orcid":false,"given":"Paul","family":"D\u00fctting","sequence":"first","affiliation":[{"name":"Google Research, Zurich, Zurich, Switzerland"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2915-8405","authenticated-orcid":false,"given":"Michal","family":"Feldman","sequence":"additional","affiliation":[{"name":"Tel Aviv University, Tel Aviv, Tel Aviv, Israel"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9240-7398","authenticated-orcid":false,"given":"Tomasz","family":"Ponitka","sequence":"additional","affiliation":[{"name":"Tel Aviv University, Tel Aviv, Tel Aviv, Israel"}]},{"ORCID":"https:\/\/orcid.org\/0009-0002-5701-1977","authenticated-orcid":false,"given":"Ermis","family":"Soumalias","sequence":"additional","affiliation":[{"name":"University of Zurich, ETH AI Center, Zurich, Zurich, Switzerland"}]}],"member":"320","published-online":{"date-parts":[[2025,7,2]]},"reference":[{"key":"e_1_3_2_2_1_1","volume-title":"Welfare and Beyond in Multi-Agent Contracts. CoRR abs\/2504.18876","author":"Aharoni Gil","year":"2025","unstructured":"Gil Aharoni, Martin Hoefer, and Inbal Talgam-Cohen. 2025. Welfare and Beyond in Multi-Agent Contracts. CoRR abs\/2504.18876 (2025)."},{"key":"e_1_3_2_2_2_1","volume-title":"Bayesian Analysis of Linear Contracts. In EC","author":"Alon Tal","year":"2023","unstructured":"Tal Alon, Paul D\u00fctting, Yingkai Li, and Inbal Talgam-Cohen. 2023. Bayesian Analysis of Linear Contracts. In EC 2023. 66."},{"key":"e_1_3_2_2_3_1","volume-title":"EC 2021. 52\u201369","author":"Alon Tal","year":"2021","unstructured":"Tal Alon, Paul D\u00fctting, and Inbal Talgam-Cohen. 2021. Contracts with private cost per unit-of-effort. In EC 2021. 52\u201369."},{"key":"e_1_3_2_2_4_1","volume-title":"EC 2006. 18\u201328","author":"Babaioff Moshe","year":"2006","unstructured":"Moshe Babaioff, Michal Feldman, and Noam Nisan. 2006. Combinatorial agency. In EC 2006. 18\u201328."},{"key":"e_1_3_2_2_5_1","volume-title":"ICLR","author":"Bacchiocchi Francesco","year":"2024","unstructured":"Francesco Bacchiocchi, Matteo Castiglioni, Alberto Marchesi, and Nicola Gatti. 2024. Learning Optimal Contracts: How to Exploit Small Action Spaces. In ICLR 2024."},{"key":"e_1_3_2_2_6_1","volume-title":"Beyond the Worst-Case Analysis of Algorithms","author":"Balcan Maria-Florina","unstructured":"Maria-Florina Balcan. 2020. Data-Driven Algorithm Design. In Beyond the Worst-Case Analysis of Algorithms. Cambridge University Press, Cambridge, UK, 626\u2013645."},{"key":"e_1_3_2_2_7_1","volume-title":"STOC","author":"Balcan Maria-Florina","year":"2021","unstructured":"Maria-Florina Balcan, Dan F. DeBlasio, Travis Dick, Carl Kingsford, Tuomas Sandholm, and Ellen Vitercik. 2021. How much data is sufficient to learn high-performing algorithms? generalization guarantees for data-driven algorithm design. In STOC 2021. 919\u2013932."},{"key":"e_1_3_2_2_8_1","volume-title":"EC 2018. 173\u2013174","author":"Balcan Maria-Florina","year":"2018","unstructured":"Maria-Florina Balcan, Tuomas Sandholm, and Ellen Vitercik. 2018. A General Theory of Sample Complexity for Multi-Item Profit Maximization. In EC 2018. 173\u2013174."},{"key":"e_1_3_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.50"},{"key":"e_1_3_2_2_10_1","volume-title":"NIPS 2016. 2091","author":"Balcan Maria-Florina","year":"2016","unstructured":"Maria-Florina Balcan, Tuomas Sandholm, and Ellen Vitercik. 2016. Sample complexity of automated mechanism design. In NIPS 2016. 2091\u20132099."},{"key":"e_1_3_2_2_11_1","volume-title":"Soloff","author":"Bates Stephen","year":"2024","unstructured":"Stephen Bates, Michael I. Jordan, Michael Sklar, and Jake A. Soloff. 2024. Principal-Agent Hypothesis Testing. arXiv:2205.06812 [cs.GT] https:\/\/arxiv.org\/abs\/2205.06812"},{"key":"e_1_3_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2018\/18"},{"key":"e_1_3_2_2_13_1","doi-asserted-by":"crossref","first-page":"105900","DOI":"10.1016\/j.jet.2024.105900","article-title":"Data-driven contract design","volume":"221","author":"Burkett Justin","year":"2024","unstructured":"Justin Burkett and Maxwell Rosenthal. 2024. Data-driven contract design. J. Econ. Theory 221 (2024), 105900.","journal-title":"J. Econ. Theory"},{"key":"e_1_3_2_2_14_1","volume-title":"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 EC 2024."},{"key":"e_1_3_2_2_15_1","doi-asserted-by":"crossref","first-page":"536","DOI":"10.1257\/aer.20131159","article-title":"Robustness and Linear","volume":"105","author":"Carroll Gabriel","year":"2015","unstructured":"Gabriel Carroll. 2015. Robustness and Linear Contracts. Am. Econ. Rev. 105, 2 (2015), 536\u2013563.","journal-title":"Contracts. Am. Econ. Rev."},{"key":"e_1_3_2_2_16_1","volume-title":"A Reduction from Multi-Parameter to Single-Parameter Bayesian Contract Design","author":"Castiglioni Matteo","year":"1836","unstructured":"Matteo Castiglioni, Junjie Chen, Minming Li, Haifeng Xu, and Song Zuo. 2025. A Reduction from Multi-Parameter to Single-Parameter Bayesian Contract Design. In SODA. SIAM, 1795\u20131836."},{"key":"e_1_3_2_2_17_1","volume-title":"EC 2021. 285\u2013286","author":"Castiglioni Matteo","year":"2021","unstructured":"Matteo Castiglioni, Alberto Marchesi, and Nicola Gatti. 2021. Bayesian Agency: Linear versus Tractable Contracts. In EC 2021. 285\u2013286."},{"key":"e_1_3_2_2_18_1","volume-title":"EC 2022. 705\u2013735","author":"Castiglioni Matteo","year":"2022","unstructured":"Matteo Castiglioni, Alberto Marchesi, and Nicola Gatti. 2022. Designing menus of contracts efficiently: the power of randomization. In EC 2022. 705\u2013735."},{"key":"e_1_3_2_2_19_1","volume-title":"EC 2023. 412\u2013448","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 EC 2023. 412\u2013448."},{"key":"e_1_3_2_2_20_1","volume-title":"EC 2024. 315\u2013344","author":"Chen Yurong","year":"2024","unstructured":"Yurong Chen, Zhaohua Chen, Xiaotie Deng, and Zhiyi Huang. 2024. Are Bounded Contracts Learnable and Approximately Optimal?. In EC 2024. 315\u2013344."},{"key":"e_1_3_2_2_21_1","volume-title":"Learning Approximately Optimal Contracts. In SAGT","author":"Cohen Alon","year":"2022","unstructured":"Alon Cohen, Argyrios Deligkas, and Moran Koren. 2022. Learning Approximately Optimal Contracts. In SAGT 2022. 331\u2013346."},{"key":"e_1_3_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591867"},{"key":"e_1_3_2_2_23_1","volume-title":"Automated Design of Affine Maximizer Mechanisms in Dynamic Settings. In AAAI","author":"Curry Michael","year":"2024","unstructured":"Michael Curry, Vinzenz Thoma, Darshan Chakrabarti, Stephen McAleer, Christian Kroer, Tuomas Sandholm, Niao He, and Sven Seuken. 2024. Automated Design of Affine Maximizer Mechanisms in Dynamic Settings. In AAAI 2024. 9626\u20139635."},{"key":"e_1_3_2_2_24_1","volume-title":"On Supermodular Contracts and Dense Subgraphs. In SODA","author":"Deo-Campo Vuong Ramiro","year":"2024","unstructured":"Ramiro Deo-Campo Vuong, Shaddin Dughmi, Neel Patel, and Aditya Prasad. 2024. On Supermodular Contracts and Dense Subgraphs. In SODA 2024. 109\u2013132."},{"key":"e_1_3_2_2_25_1","unstructured":"Ilias Diakonikolas. 2019. Lecture 4: Concentration Inequalities. http:\/\/www.iliasdiakonikolas.org\/teaching\/Fall19\/scribes\/lec4.pdf"},{"key":"e_1_3_2_2_26_1","volume-title":"Combinatorial Contracts. In FOCS","author":"D\u00fctting Paul","year":"2021","unstructured":"Paul D\u00fctting, Tomer Ezra, Michal Feldman, and Thomas Kesselheim. 2021a. Combinatorial Contracts. In FOCS 2021. 815\u2013826."},{"key":"e_1_3_2_2_27_1","volume-title":"Multi-Agent Contracts. In STOC","author":"D\u00fctting Paul","year":"2023","unstructured":"Paul D\u00fctting, Tomer Ezra, Michal Feldman, and Thomas Kesselheim. 2023. Multi-Agent Contracts. In STOC 2023. 1311\u20131324."},{"key":"e_1_3_2_2_28_1","volume-title":"Multi-Agent Combinatorial Contracts. In SODA 2025. 1857","author":"D\u00fctting Paul","year":"2025","unstructured":"Paul D\u00fctting, Tomer Ezra, Michal Feldman, and Thomas Kesselheim. 2025. Multi-Agent Combinatorial Contracts. In SODA 2025. 1857\u20131891."},{"key":"e_1_3_2_2_29_1","volume-title":"Combinatorial Contracts Beyond Gross Substitutes. In SODA","author":"D\u00fctting Paul","year":"2024","unstructured":"Paul D\u00fctting, Michal Feldman, and Yoav Gal-Tzur. 2024. Combinatorial Contracts Beyond Gross Substitutes. In SODA 2024. 92\u2013108."},{"key":"e_1_3_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.2403.09794"},{"key":"e_1_3_2_2_31_1","volume-title":"Optimal No-Regret Learning for One-Side Lipschitz Functions. In ICML","author":"D\u00fctting Paul","year":"2023","unstructured":"Paul D\u00fctting, Guru Guruganesh, Jon Schneider, and Joshua Wang. 2023. Optimal No-Regret Learning for One-Side Lipschitz Functions. In ICML 2023. 8836\u20138850."},{"key":"e_1_3_2_2_32_1","volume-title":"EC 2019. 369\u2013387","author":"D\u00fctting Paul","year":"2019","unstructured":"Paul D\u00fctting, Tim Roughgarden, and Inbal Talgam-Cohen. 2019. Simple versus optimal contracts. In EC 2019. 369\u2013387."},{"key":"e_1_3_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/20M132153X"},{"key":"e_1_3_2_2_34_1","first-page":"3","article-title":"Algorithmic Contract Theory: A Survey","volume":"16","author":"D\u00fctting Paul","year":"2024","unstructured":"Paul D\u00fctting, Michal Feldman, and Inbal Talgam-Cohen. 2024. Algorithmic Contract Theory: A Survey. Found. Trends Theor. Comput. Sci. 16, 3\u20134 (2024), 211\u2013412.","journal-title":"Found. Trends Theor. Comput. Sci."},{"key":"e_1_3_2_2_35_1","volume-title":"ITCS","author":"Ezra Tomer","year":"2024","unstructured":"Tomer Ezra, Michal Feldman, and Maya Schlesinger. 2024a. On the (In)approximability of Combinatorial Contracts. In ITCS 2024. 44:1\u201344:22."},{"key":"e_1_3_2_2_36_1","volume-title":"CoRR abs\/2403.09545","author":"Ezra Tomer","year":"2024","unstructured":"Tomer Ezra, Michal Feldman, and Maya Schlesinger. 2024b. Sequential Contracts. CoRR abs\/2403.09545 (2024)."},{"key":"e_1_3_2_2_37_1","volume-title":"Tomasz Ponitka, and Maya Schlesinger.","author":"Feldman Michal","year":"2025","unstructured":"Michal Feldman, Yoav Gal Tzur, Tomasz Ponitka, and Maya Schlesinger. 2025. Budget-Feasible Contracts. CoRR abs\/2504.01773 (2025)."},{"key":"e_1_3_2_2_38_1","volume-title":"EC 2014. 5\u201322","author":"Frazier Peter","year":"2014","unstructured":"Peter Frazier, David Kempe, Jon Kleinberg, and Robert Kleinberg. 2014. Incentivizing exploration. In EC 2014. 5\u201322."},{"key":"e_1_3_2_2_39_1","volume-title":"The Creator Economy Could Approach Half a Trillion Dollars by","author":"Sachs Goldman","year":"2027","unstructured":"Goldman Sachs. 2022. The Creator Economy Could Approach Half a Trillion Dollars by 2027. https:\/\/www.goldmansachs.com\/insights\/articles\/the-creator-economy-could-approach-half-a-trillion-dollars-by-2027"},{"key":"e_1_3_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.2307\/1912246"},{"key":"e_1_3_2_2_41_1","volume-title":"EC 2021. 563\u2013582","author":"Guruganesh Guru","unstructured":"Guru Guruganesh, Jon Schneider, and Joshua R. Wang. 2021. Contracts under Moral Hazard and Adverse Selection. In EC 2021. 563\u2013582."},{"key":"e_1_3_2_2_42_1","volume-title":"The Power of Menus in Contract Design. In EC","author":"Guruganesh Guru","year":"2023","unstructured":"Guru Guruganesh, Jon Schneider, Joshua R. Wang, and Junyao Zhao. 2023. The Power of Menus in Contract Design. In EC 2023. 818\u2013848."},{"key":"e_1_3_2_2_43_1","volume-title":"EC 2014. 359\u2013376","author":"Ho Chien-Ju","year":"2014","unstructured":"Chien-Ju Ho, Aleksandrs Slivkins, and Jennifer Wortman Vaughan. 2014. Adaptive contract design for crowdsourcing markets: Bandit algorithms for repeated principal-agent problems. In EC 2014. 359\u2013376."},{"key":"e_1_3_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.2307\/3003320"},{"key":"e_1_3_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1741"},{"key":"e_1_3_2_2_46_1","volume-title":"NIPS","author":"Morgenstern Jamie","year":"2015","unstructured":"Jamie Morgenstern and Tim Roughgarden. 2015. The pseudo-dimension of near-optimal auctions. In NIPS 2015. 136\u2013144."},{"key":"e_1_3_2_2_47_1","unstructured":"Royal Swedish Academy of Sciences. 2016. Scientific background on the 2016 Nobel Prize in Economic. https:\/\/www.nobelprize.org\/prizes\/economic-sciences\/2016\/press-release\/"},{"key":"e_1_3_2_2_48_1","volume-title":"Incentivized Learning in Principal-Agent Bandit Games. In ICML","author":"Scheid Antoine","year":"2024","unstructured":"Antoine Scheid, Daniil Tiapkin, Etienne Boursier, Aymeric Capitaine, Eric Moulines, Michael Jordan, El-Mahdi El-Mhamdi, and Alain Oliviero Durmus. 2024. Incentivized Learning in Principal-Agent Bandit Games. In ICML 2024. 43608\u201343631."},{"key":"e_1_3_2_2_49_1","doi-asserted-by":"crossref","first-page":"477","DOI":"10.1257\/aer.102.3.477","article-title":"On the Use of Holdout Samples for Model","volume":"102","author":"Schorfheide Frank","year":"2012","unstructured":"Frank Schorfheide and Kenneth I. Wolpin. 2012. On the Use of Holdout Samples for Model Selection. Am. Econ. Rev. 102, 3 (2012), 477\u201381.","journal-title":"Selection. Am. Econ. Rev."},{"key":"e_1_3_2_2_50_1","doi-asserted-by":"crossref","first-page":"332","DOI":"10.1016\/j.rie.2016.02.001","article-title":"To hold out or not to hold out","volume":"70","author":"Schorfheide Frank","year":"2016","unstructured":"Frank Schorfheide and Kenneth I. Wolpin. 2016. To hold out or not to hold out. Res. Econ. 70, 2 (2016), 332\u2013345.","journal-title":"Res. Econ."},{"key":"e_1_3_2_2_51_1","volume-title":"Prices","author":"Soumalias Ermis","year":"2025","unstructured":"Ermis Soumalias, Jakob Heiss, Jakob Weissteiner, and Sven Seuken. 2025. Prices, Bids, Values: One ML-Powered Combinatorial Auction to Rule Them All. arXiv:2411.09355 [cs.GT] https:\/\/arxiv.org\/abs\/2411.09355 Forthcoming at ICML 2025."},{"key":"e_1_3_2_2_52_1","volume-title":"Machine Learning-Powered Course Allocation. In EC","author":"Soumalias Ermis","year":"2024","unstructured":"Ermis Soumalias, Behnoosh Zamanlooy, Jakob Weissteiner, and Sven Seuken. 2024b. Machine Learning-Powered Course Allocation. In EC 2024. 1099."},{"key":"e_1_3_2_2_53_1","volume-title":"Machine Learning-Powered Combinatorial Clock Auction. In AAAI","author":"Soumalias Ermis Nikiforos","year":"2024","unstructured":"Ermis Nikiforos Soumalias, Jakob Weissteiner, Jakob Heiss, and Sven Seuken. 2024a. Machine Learning-Powered Combinatorial Clock Auction. In AAAI 2024. 9891\u20139900."},{"key":"e_1_3_2_2_54_1","volume-title":"Introduction to Nonparametric Estimation","author":"Tsybakov Alexandre B.","unstructured":"Alexandre B. Tsybakov. 2009. Introduction to Nonparametric Estimation. Springer, New York, NY, USA."},{"key":"e_1_3_2_2_55_1","volume-title":"The Sample Complexity of Online Contract Design. In EC","author":"Zhu Banghua","year":"2023","unstructured":"Banghua Zhu, Stephen Bates, Zhuoran Yang, Yixin Wang, Jiantao Jiao, and Michael I. Jordan. 2023. The Sample Complexity of Online Contract Design. In EC 2023. 1188."}],"event":{"name":"EC '25: 26th ACM Conference on Economics and Computation","location":"Stanford University Stanford CA USA","acronym":"EC '25","sponsor":["SIGecom ACM Special Interest Group on Economics and Computation"]},"container-title":["Proceedings of the 26th ACM Conference on Economics and Computation"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3736252.3742585","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,2]],"date-time":"2025-07-02T18:49:38Z","timestamp":1751482178000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3736252.3742585"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7,2]]},"references-count":55,"alternative-id":["10.1145\/3736252.3742585","10.1145\/3736252"],"URL":"https:\/\/doi.org\/10.1145\/3736252.3742585","relation":{},"subject":[],"published":{"date-parts":[[2025,7,2]]},"assertion":[{"value":"2025-07-02","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}