A Direct Proof of the Short-Side Advantage in Random Matching Markets
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866918119924039680 |
|---|---|
| author | Mauras, Simon Pralat, Pawel Vetta, Adrian |
| author_facet | Mauras, Simon Pralat, Pawel Vetta, Adrian |
| contents | 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-proposal deferred-acceptance algorithm gives doctors an expected rank of order $\log n$ for their partners and hospitals an expected rank of order $\frac{n}{\log n}$ for their partners. This situation is reversed in an unbalanced market with $n+1$ doctors and $n$ hospitals, a phenomenon known as the short-side advantage. The current proofs of this fact are indirect, counter-intuitively being based upon analyzing the hospital-proposal deferred-acceptance algorithm. In this paper we provide a direct proof of the short-side advantage, explicitly analyzing the doctor-proposal deferred-acceptance algorithm. Our proof sheds light on how and why the phenomenon arises. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_05574 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Direct Proof of the Short-Side Advantage in Random Matching Markets Mauras, Simon Pralat, Pawel Vetta, Adrian Computer Science and Game Theory Discrete Mathematics Combinatorics 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-proposal deferred-acceptance algorithm gives doctors an expected rank of order $\log n$ for their partners and hospitals an expected rank of order $\frac{n}{\log n}$ for their partners. This situation is reversed in an unbalanced market with $n+1$ doctors and $n$ hospitals, a phenomenon known as the short-side advantage. The current proofs of this fact are indirect, counter-intuitively being based upon analyzing the hospital-proposal deferred-acceptance algorithm. In this paper we provide a direct proof of the short-side advantage, explicitly analyzing the doctor-proposal deferred-acceptance algorithm. Our proof sheds light on how and why the phenomenon arises. |
| title | A Direct Proof of the Short-Side Advantage in Random Matching Markets |
| topic | Computer Science and Game Theory Discrete Mathematics Combinatorics |
| url | https://arxiv.org/abs/2501.05574 |