Random Popular Matchings with Incomplete Preference Lists - Ruangwises, Suthee; Itoh, Toshiya (Journal of Graph Algorithms and Applications, 2019)
Given a set $A$ of $n$ people and a set $B$ of $m ≥ n$ items, with each person having a list that ranks his/her preferred items in order of preference, we want to match every person with a unique item. A matching $M$ is called popular if for any other matching $M'$, the number of people who prefer $M$ to $M'$ is not less than the number of those who prefer $M'$ to $M$. For given $n$ and $m$, consider the probability of existence of a popular matching when each person's preference list is independently and uniformly generated at random. Previously, Mahdian[Mahdian, Conf. El. Comm., 2006] showed that when people's preference lists are strict (containing no ties) and complete (containing all items in $B$), if $α = m/n > α_*$, where $α_* ≈ 1.42$ is the root of equation $x^2 = e^{1/x}$, then a popular matching exists with probability $1-o(1)$; and if $α < α_*$, then a popular matching exists with probability $o(1)$, i.e. a phase transition occurs at $α_*$. In this paper, we investigate phase transitions in the case that people's preference lists are strict but not complete. We show that in the case where every person has a preference list with length of a constant $k ≥ 4$, a similar phase transition occurs at $α_k$, where $α_k ≥ 1$ is the root of equation $x e^{-1/2x} = 1-(1-e^{-1/x})^{k-1}$.