{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,6,25]],"date-time":"2023-06-25T04:24:02Z","timestamp":1687667042817},"reference-count":42,"publisher":"Association for Computing Machinery (ACM)","issue":"1-2","funder":[{"name":"Singapore MOE","award":["R-252-000-625-133"]},{"name":"Singapore NRF Fellowship","award":["R-252-000-750-733"]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Econ. Comput."],"published-print":{"date-parts":[[2023,3,31]]},"abstract":"The past few years have seen several works exploring learning economic solutions from data, including optimal auction design, function optimization, stable payoffs in cooperative games, and more. In this work, we provide a unified learning-theoretic methodology for modeling such problems and establish tools for determining whether a given solution concept can be efficiently learned from data. Our learning-theoretic framework generalizes a notion of function space dimension\u2014the graph dimension\u2014adapting it to the solution concept learning domain. We identify sufficient conditions for efficient solution learnability and show that results in existing works can be immediately derived using our methodology. Finally, we apply our methods in other economic domains, yielding learning variants of competitive equilibria and Condorcet winners.<\/jats:p>\n ","DOI":"10.1145\/3580374","type":"journal-article","created":{"date-parts":[[2023,4,22]],"date-time":"2023-04-22T11:01:36Z","timestamp":1682161296000},"page":"1-23","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["A Learning Framework for Distribution-Based Game-Theoretic Solution Concepts"],"prefix":"10.1145","volume":"11","author":[{"ORCID":"http:\/\/orcid.org\/0000-0002-7662-5117","authenticated-orcid":false,"given":"Tushant","family":"Jha","sequence":"first","affiliation":[{"name":"University of Oxford"}]},{"ORCID":"http:\/\/orcid.org\/0000-0002-0635-6230","authenticated-orcid":false,"given":"Yair","family":"Zick","sequence":"additional","affiliation":[{"name":"University of Massachusetts, Amherst"}]}],"member":"320","published-online":{"date-parts":[[2023,6,24]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511624216"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1613\/jair.1.11270"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.5555\/2832249.2832315"},{"key":"e_1_3_3_5_2","first-page":"2083","volume-title":"Proceedings of the 30th International Conference on Neural Information Processing Systems (NIPS\u201916)","author":"Balcan M. F.","year":"2016","unstructured":"M. F. Balcan, T. Sandholm, and E. Vitercik. 2016. Sample complexity of automated mechanism design. In Proceedings of the 30th International Conference on Neural Information Processing Systems (NIPS\u201916). 2083\u20132091."},{"key":"e_1_3_3_6_2","article-title":"Envy-free classification","volume":"1809","author":"Balcan M. F.","year":"2018","unstructured":"M. F. Balcan, T. Dick, R. Noothigattu, and A. D. Procaccia. 2018. Envy-free classification. CoRR abs\/1809.08700 (2018).","journal-title":"CoRR"},{"key":"e_1_3_3_7_2","first-page":"793","volume-title":"Proceedings of the 43rd Annual ACM Symposium on Theory of Computing (STOC\u201911)","author":"Balcan M. F.","year":"2011","unstructured":"M. F. Balcan and N. Harvey. 2011. Learning submodular functions. In Proceedings of the 43rd Annual ACM Symposium on Theory of Computing (STOC\u201911). 793\u2013802."},{"key":"e_1_3_3_8_2","article-title":"Learning cooperative games","volume":"1505","author":"Balcan M. F.","year":"2015","unstructured":"M. F. Balcan, A. D. Procaccia, and Y. Zick. 2015. Learning cooperative games. CoRR abs\/1505.00039 (2015).","journal-title":"CoRR"},{"key":"e_1_3_3_9_2","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1145\/3219166.3219217","volume-title":"Proceedings of the 2018 ACM Conference on Economics and Computation (EC\u201918)","author":"Balcan M. F.","year":"2018","unstructured":"M. F. Balcan, T. Sandholm, and E. Vitercik. 2018. A general theory of sample complexity for multi-item profit maximization. In Proceedings of the 2018 ACM Conference on Economics and Computation (EC\u201918). 173\u2013174."},{"key":"e_1_3_3_10_2","first-page":"4017","volume-title":"Proceedings of the 29th International Conference on Neural Information Processing Systems (NIPS\u201916)","author":"Balkanski E.","year":"2016","unstructured":"E. Balkanski, A. Rubinstein, and Y. Singer. 2016. The power of optimization from samples. In Proceedings of the 29th International Conference on Neural Information Processing Systems (NIPS\u201916). 4017\u20134025."},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055406"},{"key":"e_1_3_3_12_2","unstructured":"E. Balkanski and Y. Singer. 2017. The sample complexity of optimizing a convex function. Proceedings of Machine Learning Research 65 (2017) 1\u201327."},{"key":"e_1_3_3_13_2","first-page":"6222","volume-title":"Proceedings of the 30th International Conference on Neural Information Processing Systems (NIPS\u201917)","author":"Balkanski E.","year":"2017","unstructured":"E. Balkanski, U. Syed, and S. Vassilvitskii. 2017. Statistical cost sharing. In Proceedings of the 30th International Conference on Neural Information Processing Systems (NIPS\u201917). 6222\u20136231."},{"key":"e_1_3_3_14_2","first-page":"1421","volume-title":"Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems (AAMAS\u201915)","author":"Bhattacharyya A.","year":"2015","unstructured":"A. Bhattacharyya and P. Dey. 2015. Sample complexity for winner prediction in elections. In Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems (AAMAS\u201915). 1421\u20131431."},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781107446984"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.5555\/3304415.3304435"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1086\/664613"},{"key":"e_1_3_3_18_2","first-page":"243","volume-title":"Proceedings of the 46th Annual ACM Symposium on Theory of Computing (STOC\u201914)","author":"Cole R.","year":"2014","unstructured":"R. Cole and T. Roughgarden. 2014. The sample complexity of revenue maximization. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing (STOC\u201914). 243\u2013252."},{"key":"e_1_3_3_19_2","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1007\/BF01586937","article-title":"Fixed point theorems for discontinuous mappings","volume":"51","author":"Cromme L. J.","year":"1991","unstructured":"L. J. Cromme and I. Diener. 1991. Fixed point theorems for discontinuous mappings. Mathematical Programming 51, 1-3 (1991), 257\u2013267.","journal-title":"Mathematical Programming"},{"key":"e_1_3_3_20_2","first-page":"2377","article-title":"Multiclass learnability and the ERM principle","volume":"16","author":"Daniely A.","year":"2011","unstructured":"A. Daniely, S. Sabato, S. Ben-David, and S. Shalev-Shwartz. 2011. Multiclass learnability and the ERM principle. Journal of Machine Learning Research 16 (2011), 2377\u20132404.","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_3_3_21_2","first-page":"426","volume-title":"Proceedings of the 48th Annual ACM Symposium on Theory of Computing (STOC\u201916)","author":"Devanur N.","year":"2016","unstructured":"N. Devanur, Z. Huang, and C. Psomas. 2016. The sample complexity of auctions with side information. In Proceedings of the 48th Annual ACM Symposium on Theory of Computing (STOC\u201916). 426\u2013439."},{"key":"e_1_3_3_22_2","volume-title":"Trends in Computational Social Choice","author":"Elkind E.","year":"2017","unstructured":"E. Elkind, M. Lackner, and D. Peters. 2017. Structured preferences. In Trends in Computational Social Choice, U. Endriss (Ed.). AI Access, 187\u2013208."},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.1006\/jeth.1999.2531"},{"key":"e_1_3_3_24_2","unstructured":"Jason S. Hartford James R. Wright and Kevin Leyton-Brown. 2016. Deep learning for predicting human strategic behavior. In Proceedings of the 29th International Conference on Neural Information Processing Systems (NIPS\u201916) . 2424\u20132432."},{"key":"e_1_3_3_25_2","unstructured":"A. Hassidim and Y. Singer. 2017. Submodular optimization under noise. Proceedings of Machine Learning Research 65 (2017) 1069\u20131122."},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.5555\/2936924.2936962"},{"key":"e_1_3_3_27_2","doi-asserted-by":"crossref","unstructured":"A. Igarashi J. Sliwinski and Y. Zick. 2019. Forming probably stable communities with limited interactions. In Proceedings of the 33rd AAAI Conference on Artificial Intelligence (AAAI\u201919) . 2053\u20132060.","DOI":"10.1609\/aaai.v33i01.33012053"},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.5555\/200548"},{"key":"e_1_3_3_29_2","doi-asserted-by":"publisher","DOI":"10.5555\/3463952.3464163"},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.5555\/3463952.3464043"},{"key":"e_1_3_3_31_2","doi-asserted-by":"crossref","unstructured":"Nicholas Mattei and Toby Walsh. 2013. PrefLib: A library of preference data http:\/\/preflib.org . In Algorithmic Decision Theory . Lecture Notes in Computer Science Vol. 8176. Springer 259\u2013270.","DOI":"10.1007\/978-3-642-41575-3_20"},{"key":"e_1_3_3_32_2","first-page":"136","volume-title":"Proceedings of the 28th International Conference on Neural Information Processing Systems (NIPS\u201915)","author":"Morgenstern J.","year":"2015","unstructured":"J. Morgenstern and T. Roughgarden. 2015. On the pseudo-dimension of nearly optimal auctions. In Proceedings of the 28th International Conference on Neural Information Processing Systems (NIPS\u201915). 136\u2013144."},{"key":"e_1_3_3_33_2","unstructured":"J. Morgenstern and T. Roughgarden. 2016. Learning simple auctions. Proceedings of Machine Learning Research 49 (2016) 1298\u20131318."},{"key":"e_1_3_3_34_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF00114804"},{"key":"e_1_3_3_35_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511800481"},{"key":"e_1_3_3_36_2","first-page":"209","volume-title":"Proceedings of the 15th ACM Conference on Economics and Computation (EC\u201914)","author":"Othman A.","year":"2014","unstructured":"A. Othman, C. Papadimitriou, and A. Rubinstein. 2014. The complexity of fairness through equilibrium. In Proceedings of the 15th ACM Conference on Economics and Computation (EC\u201914). 209\u2013226."},{"key":"e_1_3_3_37_2","unstructured":"N. Rosenfeld E. Balkanski A. Globerson and Y. Singer. 2018. Learning to optimize combinatorial functions. Proceedings of Machine Learning Research 80 (2018) 4374\u20134383."},{"key":"e_1_3_3_38_2","doi-asserted-by":"publisher","DOI":"10.5555\/2621980"},{"key":"e_1_3_3_39_2","doi-asserted-by":"publisher","DOI":"10.5555\/1756006.1953019"},{"key":"e_1_3_3_40_2","first-page":"2730","volume-title":"Proceedings of the 26th International Conference on Artificial Intelligence (IJCAI\u201917)","author":"Sliwinski J.","year":"2017","unstructured":"J. Sliwinski and Y. Zick. 2017. Learning hedonic games. In Proceedings of the 26th International Conference on Artificial Intelligence (IJCAI\u201917). 2730\u20132736."},{"key":"e_1_3_3_41_2","first-page":"5352","volume-title":"Proceedings of the 30th International Conference on Neural Information Processing Systems (NIPS\u201917)","author":"Syrgkanis V.","year":"2017","unstructured":"V. Syrgkanis. 2017. A sample complexity measure with applications to learning optimal auctions. In Proceedings of the 30th International Conference on Neural Information Processing Systems (NIPS\u201917). 5352\u20135359."},{"key":"e_1_3_3_42_2","doi-asserted-by":"publisher","DOI":"10.1137\/1116025"},{"key":"e_1_3_3_43_2","first-page":"2237","volume-title":"Proceedings of the 33rd AAAI Conference on Artificial Intelligence, the 31st Innovative Applications of Artificial Intelligence Conference, and the 9th AAAI Symposium on Educational Advances in Artificial Intelligence (AAAI\u201919\/IAAI\u201919\/EAAI\u201919)","author":"Zhang H.","year":"2019","unstructured":"H. Zhang and V. Conitzer. 2019. A PAC framework for aggregating agents\u2019 judgments. In Proceedings of the 33rd AAAI Conference on Artificial Intelligence, the 31st Innovative Applications of Artificial Intelligence Conference, and the 9th AAAI Symposium on Educational Advances in Artificial Intelligence (AAAI\u201919\/IAAI\u201919\/EAAI\u201919). 2237\u20132244."}],"container-title":["ACM Transactions on Economics and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3580374","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,24]],"date-time":"2023-06-24T13:14:49Z","timestamp":1687612489000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3580374"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,3,31]]},"references-count":42,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2023,3,31]]}},"alternative-id":["10.1145\/3580374"],"URL":"http:\/\/dx.doi.org\/10.1145\/3580374","relation":{},"ISSN":["2167-8375","2167-8383"],"issn-type":[{"value":"2167-8375","type":"print"},{"value":"2167-8383","type":"electronic"}],"subject":["Computational Mathematics","Marketing","Economics and Econometrics","Statistics and Probability","Computer Science (miscellaneous)"],"published":{"date-parts":[[2023,3,31]]},"assertion":[{"value":"2020-09-15","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-01-12","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-06-24","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}