{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:10:27Z","timestamp":1750219827412,"version":"3.41.0"},"reference-count":44,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2023,5,24]],"date-time":"2023-05-24T00:00:00Z","timestamp":1684886400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc\/4.0\/"}],"funder":[{"name":"NSF Graduate Research Fellowship","award":["1752814"],"award-info":[{"award-number":["1752814"]}]},{"name":"Vannevar Bush Faculty Fellowship","award":["N00014-21-1-2941"],"award-info":[{"award-number":["N00014-21-1-2941"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2023,6,30]]},"abstract":"<jats:p>Large-scale, two-sided matching platforms must find market outcomes that align with user preferences while simultaneously learning these preferences from data. Classical notions of stability (Gale and Shapley, 1962; Shapley and Shubik, 1971) are, unfortunately, of limited value in the learning setting, given that preferences are inherently uncertain and destabilizing while they are being learned. To bridge this gap, we develop a framework and algorithms for learning stable market outcomes under uncertainty. Our primary setting is matching with transferable utilities, where the platform both matches agents and sets monetary transfers between them. We design an incentive-aware learning objective that captures the distance of a market outcome from equilibrium. Using this objective, we analyze the complexity of learning as a function of preference structure, casting learning as a stochastic multi-armed bandit problem. Algorithmically, we show that \u201coptimism in the face of uncertainty,\u201d the principle underlying many bandit algorithms, applies to a primal-dual formulation of matching with transfers and leads to near-optimal regret bounds. Our work takes a first step toward elucidating when and how stable matchings arise in large, data-driven marketplaces.<\/jats:p>","DOI":"10.1145\/3583681","type":"journal-article","created":{"date-parts":[[2023,2,16]],"date-time":"2023-02-16T11:34:03Z","timestamp":1676547243000},"page":"1-46","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Learning Equilibria in Matching Markets with Bandit Feedback"],"prefix":"10.1145","volume":"70","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3521-440X","authenticated-orcid":false,"given":"Meena","family":"Jagadeesan","sequence":"first","affiliation":[{"name":"UC Berkeley EECS, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4295-5361","authenticated-orcid":false,"given":"Alexander","family":"Wei","sequence":"additional","affiliation":[{"name":"UC Berkeley EECS, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6617-4842","authenticated-orcid":false,"given":"Yixin","family":"Wang","sequence":"additional","affiliation":[{"name":"UC Berkeley EECS, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8935-817X","authenticated-orcid":false,"given":"Michael I.","family":"Jordan","sequence":"additional","affiliation":[{"name":"UC Berkeley EECS and Statistics, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0257-3860","authenticated-orcid":false,"given":"Jacob","family":"Steinhardt","sequence":"additional","affiliation":[{"name":"UC Berkeley Statistics, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,5,24]]},"reference":[{"key":"e_1_3_3_2_2","first-page":"263","volume-title":"21st Annual Conference on Learning Theory (COLT\u201908)","author":"Abernethy Jacob D.","year":"2008","unstructured":"Jacob D. Abernethy, Elad Hazan, and Alexander Rakhlin. 2008. Competing in the dark: An efficient algorithm for bandit linear optimization. In 21st Annual Conference on Learning Theory (COLT\u201908). Omnipress, 263\u2013274."},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2020.01.008"},{"key":"e_1_3_3_4_2","article-title":"Competing bandits: The perils of exploration under competition","volume":"2007","author":"Aridor Guy","year":"2020","unstructured":"Guy Aridor, Yishay Mansour, Aleksandrs Slivkins, and Zhiwei Steven Wu. 2020. Competing bandits: The perils of exploration under competition. CoRR abs\/2007.10144 (2020).","journal-title":"CoRR"},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.2018.3265"},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1023\/A:1013689704352"},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701398375"},{"key":"e_1_3_3_8_2","article-title":"Existence of equilibrium in large matching markets with complementarities","author":"Azevedo Eduardo M.","year":"2018","unstructured":"Eduardo M. Azevedo and John William Hatfield. 2018. Existence of equilibrium in large matching markets with complementarities. Available at SSRN (2018). https:\/\/papers.ssrn.com\/sol3\/papers.cfm?abstract_id=3268884.","journal-title":"Available at SSRN"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/3164539"},{"key":"e_1_3_3_10_2","article-title":"Beyond  \\(\\log ^2(T)\\)  regret for decentralized bandits in matching markets","volume":"2103","author":"Basu Soumya","year":"2021","unstructured":"Soumya Basu, Karthik Abinav Sankararaman, and Abishek Sankararaman. 2021. Beyond \\(\\log ^2(T)\\) regret for decentralized bandits in matching markets. CoRR abs\/2103.07501 (2021).","journal-title":"CoRR"},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.1002\/nav.21963"},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jet.2017.01.004"},{"key":"e_1_3_3_13_2","article-title":"Regret, stability, and fairness in matching markets with bandit learners","volume":"2102","author":"Cen Sarah H.","year":"2021","unstructured":"Sarah H. Cen and Devavrat Shah. 2021. Regret, stability, and fairness in matching markets with bandit learners. CoRR abs\/2102.06246 (2021).","journal-title":"CoRR"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2012.01.001"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(87)90017-5"},{"key":"e_1_3_3_16_2","series-title":"30th International Conference on Machine Learning","first-page":"151","volume":"28","author":"Chen Wei","year":"2013","unstructured":"Wei Chen, Yajun Wang, and Yang Yuan. 2013. Combinatorial multi-armed bandit: General framework and applications. In 30th International Conference on Machine Learning(JMLR Workshop and Conference Proceedings, Vol. 28). JMLR.org, 151\u2013159."},{"key":"e_1_3_3_17_2","first-page":"2116","volume-title":"Annual Conference on Neural Information Processing Systems","author":"Combes Richard","year":"2015","unstructured":"Richard Combes, Mohammad Sadegh Talebi, Alexandre Prouti\u00e8re, and Marc Lelarge. 2015. Combinatorial bandits revisited. In Annual Conference on Neural Information Processing Systems. 2116\u20132124."},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.5555\/1642293.1642445"},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.2307\/2525306"},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.3982\/ECTA10011"},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/3391403.3399508"},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/2600057.2602897"},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2011.2181864"},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1962.11989827"},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2018.10.013"},{"key":"e_1_3_3_26_2","first-page":"202","volume-title":"60th IEEE Annual Symposium on Foundations of Computer Science (FOCS\u201919)","author":"Immorlica Nicole","year":"2019","unstructured":"Nicole Immorlica, Karthik Abinav Sankararaman, Robert E. Schapire, and Aleksandrs Slivkins. 2019. Adversarial bandits with knapsacks. In 60th IEEE Annual Symposium on Foundations of Computer Science (FOCS\u201919). IEEE Computer Society, 202\u2013219."},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2020.2013"},{"key":"e_1_3_3_28_2","first-page":"594","volume-title":"44th Symposium on Foundations of Computer Science (FOCS\u201903)","author":"Kleinberg Robert D.","year":"2003","unstructured":"Robert D. Kleinberg and Frank Thomson Leighton. 2003. The value of knowing a demand curve: Bounds on regret for online posted-price auctions. In 44th Symposium on Foundations of Computer Science (FOCS\u201903). IEEE Computer Society, 594\u2013605."},{"key":"e_1_3_3_29_2","doi-asserted-by":"publisher","DOI":"10.1002\/nav.3800020109"},{"key":"e_1_3_3_30_2","unstructured":"JMLR Workshop and Conference Proceedings 18th International Conference on Artificial Intelligence and Statistics 38 Branislav Kveton Zheng Wen Azin Ashkan Csaba Szepesv\u00e1ri Tight regret bounds for stochastic combinatorial semi-bandits 2015"},{"key":"e_1_3_3_31_2","doi-asserted-by":"publisher","DOI":"10.1017\/9781108571401"},{"key":"e_1_3_3_32_2","article-title":"The symmetry between arms and knapsacks: A primal-dual approach for bandits with knapsacks","volume":"2102","author":"Li Xiaocheng","year":"2021","unstructured":"Xiaocheng Li, Chunlin Sun, and Yinyu Ye. 2021. The symmetry between arms and knapsacks: A primal-dual approach for bandits with knapsacks. CoRR abs\/2102.06385 (2021).","journal-title":"CoRR"},{"key":"e_1_3_3_33_2","series-title":"23rd International Conference on Artificial Intelligence and Statistics","first-page":"1618","volume":"108","author":"Liu Lydia T.","year":"2020","unstructured":"Lydia T. Liu, Horia Mania, and Michael I. Jordan. 2020. Competing bandits in matching markets. In 23rd International Conference on Artificial Intelligence and Statistics(Proceedings of Machine Learning Research, Vol. 108). PMLR, 1618\u20131628."},{"key":"e_1_3_3_34_2","article-title":"Bandit learning in decentralized matching markets","volume":"2012","author":"Liu Lydia T.","year":"2020","unstructured":"Lydia T. Liu, Feng Ruan, Horia Mania, and Michael I. Jordan. 2020. Bandit learning in decentralized matching markets. CoRR abs\/2012.07348 (2020).","journal-title":"CoRR"},{"key":"e_1_3_3_35_2","doi-asserted-by":"publisher","DOI":"10.1257\/aer.20181186"},{"key":"e_1_3_3_36_2","doi-asserted-by":"publisher","DOI":"10.3982\/ECTA11183"},{"key":"e_1_3_3_37_2","doi-asserted-by":"publisher","DOI":"10.1145\/2764468.2764508"},{"key":"e_1_3_3_38_2","doi-asserted-by":"publisher","DOI":"10.1080\/02331939608844186"},{"key":"e_1_3_3_39_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0531(74)90066-0"},{"key":"e_1_3_3_40_2","first-page":"2256","volume-title":"27th Annual Conference on Neural Information Processing Systems","author":"Russo Daniel","year":"2013","unstructured":"Daniel Russo and Benjamin Van Roy. 2013. Eluder dimension and the sample complexity of optimistic exploration. In 27th Annual Conference on Neural Information Processing Systems. 2256\u20132264."},{"key":"e_1_3_3_41_2","series-title":"24th International Conference on Artificial Intelligence and Statistics","first-page":"1252","volume":"130","author":"Sankararaman Abishek","year":"2021","unstructured":"Abishek Sankararaman, Soumya Basu, and Karthik Abinav Sankararaman. 2021. Dominate or delete: Decentralized competing bandits in serial dictatorship. In 24th International Conference on Artificial Intelligence and Statistics(Proceedings of Machine Learning Research, Vol. 130). PMLR, 1252\u20131260."},{"key":"e_1_3_3_42_2","doi-asserted-by":"publisher","DOI":"10.2307\/1910101"},{"key":"e_1_3_3_43_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01753437"},{"key":"e_1_3_3_44_2","doi-asserted-by":"publisher","DOI":"10.1145\/3391403.3399449"},{"key":"e_1_3_3_45_2","volume-title":"Annual Conference on Neural Information Processing Systems","author":"Tirinzoni Andrea","year":"2020","unstructured":"Andrea Tirinzoni, Matteo Pirotta, Marcello Restelli, and Alessandro Lazaric. 2020. An asymptotically optimal primal-dual incremental algorithm for contextual linear bandits. In Annual Conference on Neural Information Processing Systems."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3583681","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3583681","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:46:27Z","timestamp":1750178787000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3583681"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5,24]]},"references-count":44,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,6,30]]}},"alternative-id":["10.1145\/3583681"],"URL":"https:\/\/doi.org\/10.1145\/3583681","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2023,5,24]]},"assertion":[{"value":"2021-12-31","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-11-11","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-05-24","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}