文章基本信息

标题：Tiered Random Matching Markets: Rank Is Proportional to Popularity
本地全文：下载
作者：Itai Ashlagi ; Mark Braverman ; Amin Saberi 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2021
卷号：185
页码：46:1-46:16
DOI：10.4230/LIPIcs.ITCS.2021.46
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Stable matching; stable marriage problem; tiered random markets; deferred acceptance