Document Open Access Logo

Tiered Random Matching Markets: Rank Is Proportional to Popularity

Authors Itai Ashlagi, Mark Braverman, Amin Saberi, Clayton Thomas, Geng Zhao

PDF

File

Thumbnail PDF
PDF
LIPIcs.ITCS.2021.46.pdf
  • Filesize: 0.5 MB
  • 16 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Algorithmic game theory and mechanism design
Keywords
  • Stable matching
  • stable marriage problem
  • tiered random markets
  • deferred acceptance

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Abstract

We study the stable marriage problem in two-sided markets with randomly generated preferences. Agents on each side of the market are divided into a constant number of "soft" tiers, which capture agents' qualities. Specifically, every agent within a tier has the same public score, and agents on each side have preferences independently generated proportionally to the public scores of the other side. 
We compute the expected average rank which agents in each tier have for their partners in the man-optimal stable matching, and prove concentration results for the average rank in asymptotically large markets. Furthermore, despite having a significant effect on ranks, public scores do not strongly influence the probability of an agent matching to a given tier of the other side. This generalizes the results by Pittel [Pittel, 1989], which analyzed markets with uniform preferences. The results quantitatively demonstrate the effect of competition due to the heterogeneous attractiveness of agents in the market.

Cite As Get BibTex

Itai Ashlagi, Mark Braverman, Amin Saberi, Clayton Thomas, and Geng Zhao. Tiered Random Matching Markets: Rank Is Proportional to Popularity. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 46:1-46:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.ITCS.2021.46

Author Details

Itai Ashlagi
  • Department of Management Science and Engineering, Stanford University, CA, USA
Mark Braverman
  • Department of Computer Science, Princeton University, NJ, USA
Amin Saberi
  • Department of Management Science and Engineering, Stanford University, CA, USA
Clayton Thomas
  • Department of Computer Science, Princeton University, NJ, USA
Geng Zhao
  • Department of Computer Science, Stanford University, CA, USA

Funding

  • Braverman, Mark: Research supported in part by the NSF Alan T. Waterman Award, Grant No. 1933331, a Packard Fellowship in Science and Engineering, and the Simons Collaboration on Algorithms and Geometry. Any opinions, findings, and conclusions or recommendations expressed in this publication are those of the author and do not necessarily reflect the views of the National Science Foundation.

References

  1. Itai Ashlagi, Mark Braverman, and Avinatan Hassidim. Stability in large matching markets with complementarities. Operations Research, 62(4):713-732, 2014. Google Scholar
  2. Itai Ashlagi, Mark Braverman, Yash Kanoria, and Peng Shi. Communication requirements and informative signaling in matching markets. In Proceedings of the 2017 ACM Conference on Economics and Computation, EC '17, page 263, New York, NY, USA, 2017. Association for Computing Machinery. URL: https://doi.org/10.1145/3033274.3084093.
  3. Itai Ashlagi, Yash Kanoria, and Jacob D Leshno. Unbalanced random matching markets: The stark effect of competition. Journal of Political Economy, 125(1):69-98, 2017. Google Scholar
  4. Hedyeh Beyhaghi, Daniela Sabán, and Éva Tardos. Effect of selfish choices in deferred acceptance with short lists. CoRR, abs/1701.00849, 2017. URL: http://arxiv.org/abs/1701.00849.
  5. Robert King Brayton. On the asymptotic behavior of the number of trials necessary to complete a set with random selection. Journal of Mathematical Analysis and Applications, 7(1):31-61, 1963. Google Scholar
  6. Linda Cai and Clayton Thomas. The short-side advantage in random matching markets. arXiv preprint, 2019. URL: http://arxiv.org/abs/1910.04406.
  7. Peter Coles and Ran Shorrer. Optimal truncation in matching markets. Games and Economic Behavior, 87:591-615, 2014. Google Scholar
  8. Aristides Doumas and Vassilis Papanicolaou. The coupon collector’s problem revisited: Asymptotics of the variance. Advances in Applied Probability - ADVAN APPL PROBAB, 44, March 2012. URL: https://doi.org/10.1239/aap/1331216649.
  9. David Gale and Lloyd S Shapley. College admissions and the stability of marriage. The American Mathematical Monthly, 69(1):9-15, 1962. Google Scholar
  10. Hugo Gimbert, Claire Mathieu, and Simon Mauras. Two-sided matching markets with correlated random preferences have few stable pairs. arXiv preprint, 2019. URL: http://arxiv.org/abs/1904.03890.
  11. Yannai A. Gonczarowski. Manipulation of stable matchings using minimal blacklists. In Proceedings of the Fifteenth ACM Conference on Economics and Computation, EC '14, page 449, New York, NY, USA, 2014. Association for Computing Machinery. URL: https://doi.org/10.1145/2600057.2602840.
  12. Gunter J Hitsch, Ali Hortaçsu, and Dan Ariely. Matching and sorting in online dating. American Economic Review, 100(1):130-63, 2010. Google Scholar
  13. Nicole Immorlica and Mohammad Mahdian. Incentives in large random two-sided markets. ACM Transactions on Economics and Computation (TEAC), 3(3):1-25, 2015. Google Scholar
  14. Yash Kanoria, Seungki Min, and Pengyu Qian. Which random matching markets exhibit a stark effect of competition? arXiv preprint, 2020. URL: http://arxiv.org/abs/2006.14653.
  15. D. E. Knuth. Mariages Stable. Université de Montréal Press, 1976. Translated as “Stable Marriage and Its Relation to Other Combinatorial Problems, CRM Proceedings and Lecture Notes, 1997. Google Scholar
  16. Donald E Knuth, Rajeev Motwani, and Boris Pittel. Stable husbands. Random Structures & Algorithms, 1(1):1-14, 1990. Google Scholar
  17. Fuhito Kojima and Parag A Pathak. Incentives and stability in large two-sided matching markets. American Economic Review, 99(3):608-27, 2009. Google Scholar
  18. SangMok Lee. Incentive Compatibility of Large Centralized Matching Markets. The Review of Economic Studies, 84(1):444-463, September 2016. URL: https://doi.org/10.1093/restud/rdw041.
  19. David G McVitie and Leslie B Wilson. Stable marriage assignment for unequal sets. BIT Numerical Mathematics, 10(3):295-309, 1970. Google Scholar
  20. Boris Pittel. The average number of stable matchings. SIAM Journal on Discrete Mathematics, 2(4):530-549, 1989. Google Scholar
  21. Boris Pittel. On likely solutions of a stable marriage problem. The Annals of Applied Probability, pages 358-401, 1992. Google Scholar
  22. Boris Pittel. On likely solutions of the stable matching problem with unequal numbers of men and women. Mathematics of Operations Research, 44(1):122-146, 2019. Google Scholar
  23. LB Wilson. An analysis of the stable marriage assignment algorithm. BIT Numerical Mathematics, 12(4):569-575, 1972. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact