Home  Issues  Aims and Scope  Instructions for Authors 
Special Issue on Selected Papers from the 12th International Conference and Workshops on Algorithms and Computation, WALCOM 2018
DOI: 10.7155/jgaa.00513
Random Popular Matchings with Incomplete Preference Lists
Suthee Ruangwises and
Toshiya Itoh
Vol. 23, no. 5, pp. 815835, 2019. Regular paper.
Abstract 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 $\alpha = m/n > \alpha_*$, where $\alpha_* \approx 1.42$ is the root of equation $x^2 = e^{1/x}$, then a popular matching exists with probability $1o(1)$; and if $\alpha < \alpha_*$, then a popular matching exists with probability $o(1)$, i.e. a phase transition occurs at $\alpha_*$. 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 $\alpha_k$, where $\alpha_k \geq 1$ is the root of equation $x e^{1/2x} = 1(1e^{1/x})^{k1}$.

Submitted: March 2018.
Reviewed: April 2019.
Revised: April 2019.
Accepted: June 2019.
Final: September 2019.
Published: October 2019.
