Can I read Unbalanced Random Matching Markets with Partial Preferences on EtoBox?

Unbalanced Random Matching Markets with Partial Preferences by Potukuchi, Aditya; Singh, Shikha is a scholarly article available to read on EtoBox.

What is Unbalanced Random Matching Markets with Partial Preferences about?

Properties of stable matchings in the popular random-matching-market model have been studied for over 50 years. In a random matching market, each agent has complete preferences drawn uniformly and independently at random. Wilson (1972), Knuth (1976) and Pittel (1989) proved that in balanced random matching markets, the proposers are matched to their $\ln n$th choice on average. In this paper, we consider markets where agents have partial (truncated) preferences, that is, the proposers only rank their top $d$ partners. Despite the long history of the problem, the following fundamental question remained unanswered: \emph{what is the smallest value of $d$ that results in a perfect stable matching with high probability?} In this paper, we answer this question exactly -- we prove that a degree of $\ln^2 n$ is necessary and sufficient. That is, we show that if $d < (1-\epsilon) \ln^2 n$ then no stable matching is perfect and if $d > (1+ \epsilon) \ln^2 n$, then every stable matching is perfect with high probability. This settles a recent conjecture by Kanoria, Min and Qian (2021). We generalize this threshold for unbalanced markets: we consider a matching market with $n$ agents on the sh

Author

Potukuchi, Aditya; Singh, Shikha

Published

2024

Language

EN