1 Search Results for "Zhao, Geng"


Document
Tiered Random Matching Markets: Rank Is Proportional to Popularity

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

Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)


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

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)


Copy BibTex To Clipboard

@InProceedings{ashlagi_et_al:LIPIcs.ITCS.2021.46,
  author =	{Ashlagi, Itai and Braverman, Mark and Saberi, Amin and Thomas, Clayton and Zhao, Geng},
  title =	{{Tiered Random Matching Markets: Rank Is Proportional to Popularity}},
  booktitle =	{12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
  pages =	{46:1--46:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-177-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{185},
  editor =	{Lee, James R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.46},
  URN =		{urn:nbn:de:0030-drops-135851},
  doi =		{10.4230/LIPIcs.ITCS.2021.46},
  annote =	{Keywords: Stable matching, stable marriage problem, tiered random markets, deferred acceptance}
}
  • Refine by Author
  • 1 Ashlagi, Itai
  • 1 Braverman, Mark
  • 1 Saberi, Amin
  • 1 Thomas, Clayton
  • 1 Zhao, Geng

  • Refine by Classification
  • 1 Theory of computation → Algorithmic game theory and mechanism design

  • Refine by Keyword
  • 1 Stable matching
  • 1 deferred acceptance
  • 1 stable marriage problem
  • 1 tiered random markets

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2021

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