Random Paths to Popularity in Two-Sided Matching

We study practically relevant aspects of popularity in two-sided matching where only one side has preferences. A matching is called popular if there does not exist another matching that is preferred by a simple majority. We show that for a matching to be popular it is necessary and sufficient that no coalition of size up to 3 decides to exchange their houses by simple majority. We then constructively show that a market where such coalitions meet at random converges to a popular matching whenever it exists