Random popular matchings

We consider matching markets where a centralized authority must find a matching between the agents on one side of the market, and the items on the other side. Such settings occur, for example, in mail-based DVD rental services such as NetFlix or in some job markets. The objective is to find a popular matching, or a matching that is preferred by a majority of the agents to any other matching. This concept was first defined and studied by Abraham et al. The main drawback of this concept is that popular matchings sometimes do not exist. We partially address this issue in this paper, by proving that in a probabilistic setting where preference lists are drawn at random and the number of items is more than the number of agents by a small multiplicative factor, popular matchings almost surely exist. More precisely, we prove that there is a threshold α ≈ 1.42 such that if the number of items divided by the number of agents exceeds this threshold, then a solution almost always exists. Our proof uses a characterization result by Abraham et al., and a number of tools from the theory of random graphs and phase transitions.