{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:08:35Z","timestamp":1750219715184,"version":"3.41.0"},"reference-count":35,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2024,3,11]],"date-time":"2024-03-11T00:00:00Z","timestamp":1710115200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nd\/4.0\/"}],"funder":[{"name":"National Center for Artificial Intelligence CENIA","award":["FB210017"],"award-info":[{"award-number":["FB210017"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Econ. Comput."],"published-print":{"date-parts":[[2024,3,31]]},"abstract":"<jats:p>Algorithmic matching is a pervasive mechanism in our social lives and is becoming a major medium through which people find romantic partners and potential spouses. However, romantic matching markets pose a principal-agent problem with the potential for moral hazard. The agent\u2019s (or system\u2019s) interest is to maximize the use of the matching website, while the principal\u2019s (or user\u2019s) interest is to find the best possible match. This creates a conflict of interest: the optimal matching of users may not be aligned with the platform\u2019s goal of maximizing engagement, as it could lead to long-term relationships and fewer users using the site over time. Here, we borrow the notion of price of anarchy from game theory to quantify the decrease in social efficiency of online algorithmic matching sites where engagement is in tension with user utility. We derive theoretical bounds on the price of anarchy and show that it can be bounded by a constant that does not depend on the number of users in the system. This suggests that as online matching sites grow, their potential benefits scale up without sacrificing social efficiency. Further, we conducted experiments with human subjects in a matching market and compared the social welfare achieved by an optimal matching service against a self-interested matching algorithm. We show that introducing competition among matching sites aligns the self-interested behavior of platform designers with their users and increases social efficiency.<\/jats:p>","DOI":"10.1145\/3627985","type":"journal-article","created":{"date-parts":[[2023,11,3]],"date-time":"2023-11-03T18:32:17Z","timestamp":1699036337000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Price of Anarchy in Algorithmic Matching of Romantic Partners"],"prefix":"10.1145","volume":"12","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8158-4647","authenticated-orcid":false,"given":"Andr\u00e9s","family":"Abeliuk","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Chile, and National Center for Artificial Intelligence (CENIA), Santiago, Chile"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7652-7202","authenticated-orcid":false,"given":"Khaled","family":"Elbassioni","sequence":"additional","affiliation":[{"name":"Khalifa University of Science &amp; Technology, Abu Dhabi, UAE"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0070-0667","authenticated-orcid":false,"given":"Talal","family":"Rahwan","sequence":"additional","affiliation":[{"name":"Computer Science, New York University, Abu Dhabi, UAE"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3681-7982","authenticated-orcid":false,"given":"Manuel","family":"Cebrian","sequence":"additional","affiliation":[{"name":"Department of Statistics, Universidad Carlos III de Madrid, Madrid, Spain"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1796-4303","authenticated-orcid":false,"given":"Iyad","family":"Rahwan","sequence":"additional","affiliation":[{"name":"Center for Humans &amp; Machines, Max-Planck Institute for Human Development, Berlin, Germany"}]}],"member":"320","published-online":{"date-parts":[[2024,3,11]]},"reference":[{"key":"e_1_3_4_2_2","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1007\/978-3-642-17572-5_6","volume-title":"International Workshop on Internet and Network Economics","author":"Balmaceda Felipe","year":"2010","unstructured":"Felipe Balmaceda, Santiago R. Balseiro, Jose R. Correa, and Nicolas E. Stier-Moses. 2010. The cost of moral hazard and limited liability in the principal-agent problem. In International Workshop on Internet and Network Economics. Springer, 63\u201374."},{"key":"e_1_3_4_3_2","article-title":"Combinatorial Optimization: Theory and Algorithms","author":"Bernhard Korte","year":"2008","unstructured":"Korte Bernhard and Jens Vygen. 2008. Combinatorial Optimization: Theory and Algorithms. Springer.","journal-title":"Springer."},{"issue":"8","key":"e_1_3_4_4_2","doi-asserted-by":"crossref","first-page":"eaap9815","DOI":"10.1126\/sciadv.aap9815","article-title":"Aspirational pursuit of mates in online dating markets","volume":"4","author":"Bruch Elizabeth E.","year":"2018","unstructured":"Elizabeth E. Bruch and M. E. J. Newman. 2018. Aspirational pursuit of mates in online dating markets. Science Advances 4, 8 (2018), eaap9815.","journal-title":"Science Advances"},{"key":"e_1_3_4_5_2","doi-asserted-by":"publisher","DOI":"10.2307\/1884176"},{"key":"e_1_3_4_6_2","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1222447110"},{"key":"e_1_3_4_7_2","first-page":"1583","volume-title":"Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems","author":"Esmaeili Seyed A.","year":"2022","unstructured":"Seyed A. Esmaeili, Sharmila Duppala, Vedant Nanda, Aravind Srinivasan, and John P. Dickerson. 2022. Rawlsian fairness in online bipartite matching: Two-sided, group, and individual. In Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems. 1583\u20131585."},{"key":"e_1_3_4_8_2","first-page":"412","volume-title":"2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS \u201920)","author":"Fahrbach Matthew","year":"2020","unstructured":"Matthew Fahrbach, Zhiyi Huang, Runzhou Tao, and Morteza Zadimoghaddam. 2020. Edge-weighted online bipartite matching. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS \u201920). IEEE, 412\u2013423."},{"key":"e_1_3_4_9_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jet.2005.12.001"},{"key":"e_1_3_4_10_2","doi-asserted-by":"publisher","DOI":"10.1177\/1529100612436522"},{"key":"e_1_3_4_11_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2020.103261"},{"issue":"4","key":"e_1_3_4_12_2","article-title":"The attention economy and the net","volume":"2","author":"Goldhaber Michael H.","year":"1997","unstructured":"Michael H. Goldhaber. 1997. The attention economy and the net. First Monday 2, 4 (1997).","journal-title":"First Monday"},{"issue":"2","key":"e_1_3_4_13_2","first-page":"79","article-title":"Which features increase customer retention","volume":"58","author":"Hamilton Rebecca W.","year":"2017","unstructured":"Rebecca W. Hamilton, Roland T. Rust, and Chekitan S. Dev. 2017. Which features increase customer retention. MIT Sloan Management Review 58, 2 (2017), 79\u201384.","journal-title":"MIT Sloan Management Review"},{"key":"e_1_3_4_14_2","doi-asserted-by":"publisher","DOI":"10.1257\/aer.100.1.130"},{"key":"e_1_3_4_15_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11129-010-9088-6"},{"key":"e_1_3_4_16_2","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1007\/978-3-540-68279-0_3","volume-title":"50 Years of Integer Programming 1958-2008","author":"Hoffman Alan J.","year":"2010","unstructured":"Alan J. Hoffman and Joseph B. Kruskal. 2010. Integral boundary points of convex polyhedra. In 50 Years of Integer Programming 1958-2008. Springer, 49\u201376."},{"key":"e_1_3_4_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188858"},{"issue":"1","key":"e_1_3_4_18_2","first-page":"191","article-title":"An empirical analysis of planned obsolescence","volume":"16","author":"Iizuka Toshiaki","year":"2007","unstructured":"Toshiaki Iizuka. 2007. An empirical analysis of planned obsolescence. Journal of Economics & Management Strategy 16, 1 (2007), 191\u2013226.","journal-title":"Journal of Economics & Management Strategy"},{"key":"e_1_3_4_19_2","volume-title":"Facilitating the Search for Partners on Matching Platforms: Restricting Agent Actions","author":"Kanoria Yash","year":"2017","unstructured":"Yash Kanoria and Daniela Saban. 2017. Facilitating the Search for Partners on Matching Platforms: Restricting Agent Actions. Technical Report."},{"key":"e_1_3_4_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/3490486.3538365"},{"key":"e_1_3_4_21_2","first-page":"404","volume-title":"Annual Symposium on Theoretical Aspects of Computer Science","author":"Koutsoupias Elias","year":"1999","unstructured":"Elias Koutsoupias and Christos Papadimitriou. 1999. Worst-case equilibria. In Annual Symposium on Theoretical Aspects of Computer Science. Springer, 404\u2013413."},{"key":"e_1_3_4_22_2","first-page":"6987","volume-title":"Proceedings of the 37th International Conference on Machine Learning","author":"Mladenov Martin","year":"2020","unstructured":"Martin Mladenov, Elliot Creager, Omer Ben-Porat, Kevin Swersky, Richard Zemel, and Craig Boutilier. 2020. Optimizing long-term social welfare in recommender systems: A constrained matching approach. In Proceedings of the 37th International Conference on Machine Learning. 6987\u20136998."},{"key":"e_1_3_4_23_2","doi-asserted-by":"publisher","DOI":"10.5555\/31027"},{"issue":"10","key":"e_1_3_4_24_2","doi-asserted-by":"crossref","first-page":"664","DOI":"10.1089\/cyber.2014.0302","article-title":"Is online better than offline for meeting partners? Depends: Are you looking to marry or to date?","volume":"17","author":"Paul Aditi","year":"2014","unstructured":"Aditi Paul. 2014. Is online better than offline for meeting partners? Depends: Are you looking to marry or to date? Cyberpsychology, Behavior, and Social Networking 17, 10 (2014), 664\u2013667.","journal-title":"Cyberpsychology, Behavior, and Social Networking"},{"key":"e_1_3_4_25_2","doi-asserted-by":"publisher","DOI":"10.1002\/9780470316887"},{"key":"e_1_3_4_26_2","doi-asserted-by":"publisher","DOI":"10.1038\/s41586-019-1138-y"},{"key":"e_1_3_4_27_2","doi-asserted-by":"publisher","DOI":"10.1111\/j.1756-2171.2006.tb00036.x"},{"key":"e_1_3_4_28_2","doi-asserted-by":"publisher","DOI":"10.1177\/0003122412448050"},{"key":"e_1_3_4_29_2","first-page":"187","article-title":"Designing organizations for an information-rich world","volume":"70","author":"Simon Herbert A.","year":"1996","unstructured":"Herbert A. Simon. 1996. Designing organizations for an information-rich world. International Library of Critical Writings in Economics 70 (1996), 187\u2013202.","journal-title":"International Library of Critical Writings in Economics"},{"key":"e_1_3_4_30_2","first-page":"149","article-title":"Loyalty and e-marketing issues: Customer retention on the web","volume":"3","author":"Smith Alan D.","year":"2002","unstructured":"Alan D. Smith. 2002. Loyalty and e-marketing issues: Customer retention on the web. Quarterly Journal of Electronic Commerce 3 (2002), 149\u2013162.","journal-title":"Quarterly Journal of Electronic Commerce"},{"key":"e_1_3_4_31_2","volume-title":"Online Dating & Relationship","author":"Smith Aaron Whitman","year":"2013","unstructured":"Aaron Whitman Smith and Maeve Duggan. 2013. Online Dating & Relationship. Pew Research Center, Washington, DC."},{"key":"e_1_3_4_32_2","volume-title":"Reinforcement Learning: An Introduction","author":"Sutton Richard S.","year":"2018","unstructured":"Richard S. Sutton and Andrew G. Barto. 2018. Reinforcement Learning: An Introduction. MIT Press."},{"key":"e_1_3_4_33_2","doi-asserted-by":"publisher","DOI":"10.5555\/3192424.3192510"},{"key":"e_1_3_4_34_2","volume-title":"Convex Optimization","author":"Vandenberghe Lieven","year":"2004","unstructured":"Lieven Vandenberghe and Stephen Boyd. 2004. Convex Optimization. Vol. 1. Cambridge University Press, Cambridge."},{"key":"e_1_3_4_35_2","doi-asserted-by":"crossref","first-page":"1070","DOI":"10.1007\/978-3-662-47672-7_87","volume-title":"Automata, Languages, and Programming: 42nd International Colloquium (ICALP \u201915), Proceedings, Part I 42","author":"Wang Yajun","year":"2015","unstructured":"Yajun Wang and Sam Chiu-wai Wong. 2015. Two-sided online bipartite matching and vertex cover: Beating the greedy algorithm. In Automata, Languages, and Programming: 42nd International Colloquium (ICALP \u201915), Proceedings, Part I 42. Springer, 1070\u20131081."},{"key":"e_1_3_4_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/3442381.3449889"}],"container-title":["ACM Transactions on Economics and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3627985","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3627985","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:36:10Z","timestamp":1750178170000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3627985"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3,11]]},"references-count":35,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,3,31]]}},"alternative-id":["10.1145\/3627985"],"URL":"https:\/\/doi.org\/10.1145\/3627985","relation":{},"ISSN":["2167-8375","2167-8383"],"issn-type":[{"type":"print","value":"2167-8375"},{"type":"electronic","value":"2167-8383"}],"subject":[],"published":{"date-parts":[[2024,3,11]]},"assertion":[{"value":"2020-08-19","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-10-13","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-03-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}