Random Popular Matchings with Incomplete Preference Lists

Abstract

Given a set $A$ of $n$ people and a set $B$ of $m\ge 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^{\prime }$, the number of people who prefer $M$ to $M^{\prime }$ is not less than the number of those who prefer $M^{\prime }$ 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 $\alpha =m/n>{\alpha }_{\ast }$, where ${\alpha }_{\ast }\approx 1.42$ is the root of equation $x^2=e^{1/x}$, then a popular matching exists with probability $1-o(1)$; and if $\alpha <{\alpha }_{\ast }$, then a popular matching exists with probability $o(1)$, i.e. a phase transition occurs at ${\alpha }_{\ast }$. 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\ge 4$, a similar phase transition occurs at ${\alpha }_k$, where ${\alpha }_k\ge 1$ is the root of equation $x{e}^{-1/2x}=1-(1-e^{-1/x}{)}^{k-1}$