A direct proof of the short-side advantage in random matching markets
成果类型：
Article
署名作者：
Mauras, Simon; Pralat, Pawel; Vetta, Adrian
署名单位：
Inria; Warsaw School of Economics; McGill University; McGill University
刊物名称：
GAMES AND ECONOMIC BEHAVIOR
ISSN/ISSBN：
0899-8256
DOI：
10.1016/j.geb.2025.08.013
发表日期：
2025
页码：
53-61
关键词：
摘要：
We study the stable matching problem under the random matching model where the preferences of the doctors and hospitals are sampled uniformly and independently at random. In a balanced market with n doctors and n hospitals, the doctor-proposing deferred-acceptance algorithm gives doctors an expected rank of order logn for their partners and hospitals an expected rank of order n logn for their partners (Pittel, 1989; Wilson, 1972). This situation is reversed in an unbalanced market with n + 1 doctors and n hospitals (Ashlagi et al., 2017), a phenomenon known as the short-side advantage. The current proofs (Ashlagi et al., 2017; Cai and Thomas, 2022) of this fact are indirect, counter-intuitively being based upon analyzing the hospital-proposing deferred-acceptance algorithm. In this paper we provide a direct proof of the short-side advantage, explicitly analyzing the doctor-proposing deferred-acceptance algorithm. Our proof sheds light on how and why the phenomenon arises.