Random Popular Matchings with Incomplete Preference Lists

摘要

Given a set $A$ of $n$ people and a set $B$ of $m geq 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 $lpha = m lpha_*$, where $lpha_* pprox 1.42$ is the root of equation $x^2 = e^{1/x}$, then a popular matching exists with probability $1-o(1)$; and if $lpha lpha_*$, then a popular matching exists with probability $o(1)$, i.e. a phase transition occurs at $lpha_*$. 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 geq 4$, a similar phase transition occurs at $lpha_k$, where $lpha_k geq 1$ is the root of equation $x e^{-1/2x} = 1-(1-e^{-1/x})^{k-1}$.