Structural Complexities of Matching Mechanisms
Pages 455 - 466
Abstract
We study various novel complexity measures for two-sided matching mechanisms, applied to the two canonical strategyproof matching mechanisms, Deferred Acceptance (DA) and Top Trading Cycles (TTC). Our metrics are designed to capture the complexity of various structural (rather than computational) concerns, in particular ones of recent interest within economics. We consider a unified, flexible approach to formalizing our questions: Define a protocol or data structure performing some task, and bound the number of bits that it requires. Our main results apply this approach to four questions of general interest; for mechanisms matching applicants to institutions, our questions are: (1) How can one applicant affect the outcome matching? (2) How can one applicant affect another applicant's set of options? (3) How can the outcome matching be represented / communicated? (4) How can the outcome matching be verified? Holistically, our results show that TTC is more complex than DA, formalizing previous intuitions that DA has a simpler structure than TTC. For question (2), our result gives a new combinatorial characterization of which institutions are removed from each applicant's set of options when a new applicant is added in DA; this characterization may be of independent interest. For question (3), our result gives new tight lower bounds proving that the relationship between the matching and the priorities is more complex in TTC than in DA. We nonetheless showcase that this higher complexity of TTC is nuanced: By constructing new tight lower-bound instances and new verification protocols, we prove that DA and TTC are comparable in complexity under questions (1) and (4). This more precisely delineates the ways in which TTC is more complex than DA, and emphasizes that diverse considerations must factor into gauging the complexity of matching mechanisms.
References
[1]
Atila Abdulkadiroğlu and Tayfun Sönmez. 2003. School choice: A mechanism design approach. American Economic Review, 93, 3 (2003), 729–747.
[2]
Mohammad Akbarpour and Shengwu Li. 2020. Credible auctions: A trilemma. Econometrica, 88, 2 (2020), 425–467.
[3]
Nick Arnosti. 2020. Deferred Acceptance is Unpredictable. Blog Post. https://nickarnosti.com/blog/da-predictability/ Accessed April 2023
[4]
Itai Ashlagi and Yannai A. Gonczarowski. 2018. Stable matching mechanisms are not obviously strategy-proof. Journal of Economic Theory, 177 (2018), 405–425.
[5]
Itai Ashlagi, Yash Kanoria, and Jacob D. Leshno. 2017. Unbalanced Random Matching Markets: The Stark Effect of Competition. Journal of Political Economy, 125, 1 (2017), 69 – 98.
[6]
Eduardo M. Azevedo and Jacob D. Leshno. 2016. A supply and demand framework for two-sided matching markets. Journal of Political Economy, 124, 5 (2016), 1235–1268.
[7]
Moshe Babaioff, Kira Goldner, and Yannai A. Gonczarowski. 2020. Bulow-Klemperer-Style Results for Welfare Maximization in Two-Sided Markets. In Proceedings of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 2452–2471.
[8]
Moshe Babaioff, Yannai A. Gonczarowski, and Noam Nisan. 2022. The menu-size complexity of revenue approximation. Games and Economic Behavior, 134 (2022), 281–307. Originally appeared in Proceedings of STOC’17
[9]
Moshe Babaioff, Nicole Immorlica, Brendan Lucier, and S. Matthew Weinberg. 2020. A Simple and Approximately Optimal Mechanism for an Additive Buyer. Journal of the ACM, 67, 4 (2020), 24:1–24:40. https://doi.org/10.1145/3398745
[10]
Sophie Bade and Yannai A. Gonczarowski. 2017. Gibbard-Satterthwaite success stories and obvious strategyproofness. In Proceedings of the 18th ACM Conference on Economics and Computation (EC). 565.
[11]
BPS (Boston Public Schools) Strategic Planning Team. 2005. Recommendation to Implement A New BPS Assignment Algorithm.
[12]
Jeremy Bulow and Paul Klemperer. 1996. Auctions Versus Negotiations. The American Economic Review, 180–194.
[13]
Linda Cai and Clayton Thomas. 2019. Representing All Stable Matchings by Walking a Maximal Chain. arxiv:1910.04401 Mimeo
[14]
Linda Cai and Clayton Thomas. 2022. The short-side advantage in random matching markets. In Proceedings of the 5th Symposium on Simplicity in Algorithms (SOSA). 257–267.
[15]
Stephen A. Cook, Yuval Filmus, and Dai Tri Man Lê. 2014. The complexity of the comparator circuit value problem. ACM Transactions on Computation Theory (TOCT), 6, 4 (2014), 1–44.
[16]
Constantinos Daskalakis, Alan Deckelbaum, and Christos Tzamos. 2017. Strong Duality for a Multiple-Good Monopolist. Econometrica, 85, 3 (2017), 735–767.
[17]
Shahar Dobzinski. 2016. Computational Efficiency Requires Simple Taxation. In Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS). 209–218.
[18]
Shahar Dobzinski and Shiri Ron. 2021. The communication complexity of payment computation. In Proceedings of the 53rd Annual ACM Symposium on Theory of Computing (STOC). 933–946.
[19]
Shahar Dobzinski, Shiri Ron, and Jan Vondrák. 2022. On the hardness of dominant strategy mechanism design. In Proceedings of the 54th Annual ACM Symposium on Theory of Computing (STOC). 690–703.
[20]
Alon Eden, Michal Feldman, Ophir Friedler, Inbal Talgam-Cohen, and S. Matthew Weinberg. 2017. The Competition Complexity of Auctions: A Bulow-Klemperer Result for Multi-Dimensional Bidders. In Proceedings of the 18th ACM Conference on Economics and Computation (EC). 343.
[21]
Alon Eden, Michal Feldman, Ophir Friedler, Inbal Talgam-Cohen, and S. Matthew Weinberg. 2017. A Simple and Approximately Optimal Mechanism for a Buyer with Complements. In Proceedings of the 18th ACM Conference on Economics and Computation (EC). 323.
[22]
David Gale and Lloyd S. Shapley. 1962. College Admissions and the Stability of Marriage. Amer. Math. Monthly, 69 (1962), 9–14.
[23]
David Gale and Marilda Sotomayor. 1985. Some remarks on the stable matching problem. Discrete Applied Mathematics, 11, 3 (1985), 223–232.
[24]
Rohith R. Gangam, Tung Mai, Nitya Raju, and Vijay V. Vazirani. 2018. A Structural and Algorithmic Study of Stable Matching Lattices of “Nearby” Instances, with Applications. Mimeo
[25]
Louis Golowich and Shengwu Li. 2021. On the Computational Properties of Obviously Strategy-Proof Mechanisms. Mimeo
[26]
Yannai A. Gonczarowski. 2018. Bounding the menu-size of approximately optimal auctions via optimal-transport duality. In Proceedings of the 50th Annual ACM Symposium on Theory of Computing (STOC). 123–131.
[27]
Yannai A. Gonczarowski, Ori Heffetz, and Clayton Thomas. 2023. Strategyproofness-Exposing Mechanism Descriptions. In Proceedings of the 24th ACM Conference on Economics and Computation (EC).
[28]
Yannai A. Gonczarowski, Noam Nisan, Rafail Ostrovsky, and Will Rosenbaum. 2019. A stable marriage requires communication. Games and Economic Behavior, 118 (2019), 626–647. Originally appeared in Proceedings of SODA’15
[29]
Aram Grigoryan and Markus Möller. 2023. A Theory of Auditability for Allocation and Social Choice Mechanisms. Working Paper
[30]
Dan Gusfield and Robert Irving. 1989. The Stable Marriage Problem: Structure and Algorithms. MIT Press. isbn:9780262071185
[31]
Rustamdjan Hakimov and Madhav Raghavan. 2023. Improving Transparency and Verifiability in School Admissions: Theory and Experiment. Available at SSRN 3572020.
[32]
Peter J. Hammond. 1979. Straightforward individual incentive compatibility in large economies. The Review of Economic Studies, 46, 2 (1979), 263–282.
[33]
Sergiu Hart and Noam Nisan. 2017. Approximate revenue maximization with multiple items. Journal of Economic Theory, 172 (2017), 313–347. Originally appeared in Proceedings of EC’12
[34]
Sergiu Hart and Noam Nisan. 2019. Selling multiple correlated goods: Revenue maximization and menu-size complexity. Journal of Economic Theory, 183 (2019), 991–1029. Originally appeared in Proceedings of EC’13
[35]
Jason D. Hartline and Tim Roughgarden. 2009. Simple versus optimal mechanisms. In Proceedings of the 10th ACM Conference on Electronic Commerce (EC). 225–234.
[36]
Nicole Immorlica and Mohammad Mahdian. 2005. Marriage, honesty, and stability. In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 53–62.
[37]
Robert W. Irving and Paul Leather. 1986. The Complexity of Counting Stable Marriages. SIAM J. Comput., 15, 3 (1986), 655–667.
[38]
Yash Kanoria, Seungki Min, and Pengyu Qian. 2021. In which matching markets does the short side enjoy an advantage? In Proceedings of the 32nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 1374–1386.
[39]
Anna R. Karlin, Shayan O. Gharan, and Robbie Weber. 2018. A Simply Exponential Upper Bound on the Maximum Number of Stable Matchings. In Proceedings of the 50th Annual ACM Symposium on Theory of Computing (STOC). 920–925.
[40]
Matt Kasman and Jon Valant. 2019. The opportunities and risks of K-12 student placement algorithms. The Brookings Institute, https://www.brookings.edu/research/the-opportunities-and-risks-of-k-12-student-placement-algorithms/ Accessed April 2023
[41]
Ron Kupfer. 2020. The Influence of One Strategic Agent on the Core of Stable Matchings. In Proceedings of the 16th International Conference on Web and Internet Economics (WINE).
[42]
Jacob D. Leshno and Irene Lo. 2021. The cutoff structure of top trading cycles in school choice. The Review of Economic Studies, 88, 4 (2021), 1582–1623.
[43]
Shengwu Li. 2017. Obviously strategy-proof mechanisms. American Economic Review, 107, 11 (2017), 3257–87.
[44]
Jinpeng Ma. 1994. Strategy-proofness and the strict core in a market with indivisibilities. International Journal of Game Theory, 23, 1 (1994), 75–83.
[45]
Tung Mai and Vijay V. Vazirani. 2018. Finding Stable Matchings That Are Robust to Errors in the Input. In Proceedings of the 26th Annual European Symposium on Algorithms (ESA). 112, 60:1–60:11.
[46]
Pinaki Mandal and Souvik Roy. 2021. Obviously Strategy-Proof Implementation Of Assignment Rules: A New Characterization. International Economic Review, 63, 1 (2021), 261–290.
[47]
Markus Möller. 2022. Transparent Matching Mechanisms. Available at SSRN 4073464.
[48]
Cory Palmer and Dömotör Pálvölgyi. 2022. At most 3.55^n stable matchings. In Proceedings of the 62nd Annual IEEE Symposium on Foundations of Computer Science (FOCS). 217–227.
[49]
Boris Pittel. 1989. The Average Number of Stable Matchings. SIAM Journal on Discrete Mathematics, 2, 4 (1989), 530–549.
[50]
Marek Pycia and Peter Troyan. 2021. A theory of simplicity in games and mechanism design. Mimeo (Originally appeared as “Obvious Dominance and Random Priority” in Proceedings of EC’19)
[51]
Samantha Robertson, Tonya Nguyen, and Niloufar Salehi. 2021. Modeling Assumptions Clash with the Real World: Transparency, Equity, and Community Challenges for Student Assignment Algorithms. In Proceedings of the ACM Conference on Human Factors in Computing Systems (CHI). Article 589, 14 pages.
[52]
Alvin E. Roth. 1982. The economics of matching: stability and incentives. Mathematics of Operations Research, 7, 4 (1982), 617–628.
[53]
Aviad Rubinstein, Raghuvansh R. Saxena, Clayton Thomas, S. Matthew Weinberg, and Junyao Zhao. 2021. Exponential communication separations between notions of selfishness. In Proceedings of the 53rd Annual ACM Symposium on Theory of Computing (STOC). 947–960.
[54]
Daniela Saban and Jay Sethuraman. 2015. The complexity of computing the random priority allocation matrix. Mathematics of Operations Research, 40, 4 (2015), 1005–1014.
[55]
Raghuvansh R. Saxena, Ariel Schvartzman, and S. Matthew Weinberg. 2018. The menu complexity of “one-and-a-half-dimensional” mechanism design. In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 2026–2035.
[56]
Ilya Segal. 2007. The communication requirements of social choice rules and supporting budget sets. Journal of Economic Theory, 136, 1 (2007), 341–378.
[57]
Jay Sethuraman. 2016. An alternative proof of a characterization of the TTC mechanism. Operations Research Letters, 44, 1 (2016), 107–108.
[58]
Lloyd Shapley and Herbert Scarf. 1974. On cores and indivisibility. Journal of Mathematical Economics, 1, 1 (1974), 23–37.
[59]
Ashok Subramanian. 1994. A new approach to stable matching problems. SIAM J. Comput., 23, 4 (1994), 671–700.
[60]
Clayton Thomas. 2021. Classification of Priorities Such That Deferred Acceptance is OSP Implementable. In Proceedings of the 22nd ACM Conference on Economics and Computation (EC). 860–860.
[61]
Peter Troyan. 2019. Obviously Strategy-Proof Implementation Of Top Trading Cycles. International Economic Review, 60, 3 (2019), 1249–1261.
Index Terms
- Structural Complexities of Matching Mechanisms
Recommendations
Stability in Large Matching Markets with Complementarities
<P>Labor markets can often be viewed as many-to-one matching markets. It is well known that if complementarities are present in such markets, a stable matching may not exist. We study large random matching markets with couples. We introduce a new ...
Matching with couples revisited
EC '11: Proceedings of the 12th ACM conference on Electronic commerceIt is well known that a stable matching in a many-to-one matching market with couples need not exist. We introduce a new matching algorithm for such markets and show that for large random markets the algorithm will find a stable matching with high ...
Stability in Large Matching Markets with Complementarities
Labor markets can often be viewed as many-to-one matching markets. It is well known that if complementarities are present in such markets, a stable matching may not exist. We study large random matching markets with couples. We introduce a new matching ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
June 2024
2049 pages
ISBN:9798400703836
DOI:10.1145/3618260
- General Chairs:
- Bojan Mohar,
- Igor Shinkar,
- Program Chair:
- Ryan O'Donnell
Copyright © 2024 Copyright is held by the owner/author(s). Publication rights licensed to ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 11 June 2024
Check for updates
Author Tags
Qualifiers
- Research-article
Conference
STOC '24
Sponsor:
Acceptance Rates
Overall Acceptance Rate 1,469 of 4,586 submissions, 32%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 61Total Downloads
- Downloads (Last 12 months)61
- Downloads (Last 6 weeks)15
Reflects downloads up to 29 Nov 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in