Random Popular Matchings with Incomplete Preference Lists

摘要

Given n people and m items, with each person having a preference list that ranks some or all items, we consider the probability of existence of a popular matching when each person's preference list is independently and uniformly generated at random. We say that a preference list is complete if it includes m items and is k-incomplete if it includes 1 ≤ k < m items. Mahdian showed that if m > 1.42, then popular matching exists with high probability and if m < 1.42, then popular matching does not exist with high probability when a complete preference lists is chosen independently and uniformly for each person. In this paper, we analyze the probability of existence of a popular matching when a k-incomplete preference lists is chosen independently and uniformly for each person.