Tiered random matching markets: Rank is proportional to popularity

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations


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 [20], which analyzed markets with uniform preferences. The results quantitatively demonstrate the effect of competition due to the heterogeneous attractiveness of agents in the market.

Original languageEnglish (US)
Title of host publication12th Innovations in Theoretical Computer Science Conference, ITCS 2021
EditorsJames R. Lee
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959771771
StatePublished - Feb 1 2021
Event12th Innovations in Theoretical Computer Science Conference, ITCS 2021 - Virtual, Online
Duration: Jan 6 2021Jan 8 2021

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
ISSN (Print)1868-8969


Conference12th Innovations in Theoretical Computer Science Conference, ITCS 2021
CityVirtual, Online

All Science Journal Classification (ASJC) codes

  • Software


  • Deferred acceptance
  • Stable marriage problem
  • Stable matching
  • Tiered random markets

Cite this