TY - GEN
T1 - Tiered random matching markets
T2 - 12th Innovations in Theoretical Computer Science Conference, ITCS 2021
AU - Ashlagi, Itai
AU - Braverman, Mark
AU - Saberi, Amin
AU - Thomas, Clayton
AU - Zhao, Geng
N1 - Funding Information:
Funding Mark Braverman: 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.
Publisher Copyright:
© Itai Ashlagi, Mark Braverman, Amin Saberi, Clayton Thomas, and Geng Zhao.
PY - 2021/2/1
Y1 - 2021/2/1
N2 - 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.
AB - 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.
KW - Deferred acceptance
KW - Stable marriage problem
KW - Stable matching
KW - Tiered random markets
UR - http://www.scopus.com/inward/record.url?scp=85104908603&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85104908603&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.ITCS.2021.46
DO - 10.4230/LIPIcs.ITCS.2021.46
M3 - Conference contribution
AN - SCOPUS:85104908603
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 12th Innovations in Theoretical Computer Science Conference, ITCS 2021
A2 - Lee, James R.
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Y2 - 6 January 2021 through 8 January 2021
ER -