Popular Matchings in the Stable Marriage Problem

The stable marriage problem consists of a bipartite graph $G = (A \cup B,E)$ where every vertex has a ranking of its neighbours in a strict order of preference. Every stable matching matches the same subset of vertices. In this talk we consider a relaxation of stability called {\em popularity} -- this notion was introduced by G\"ardenfors in 1975 and  it is based on ``global stability''. A matching is popular if it never loses a head-to-head election against any matching where each vertex casts a vote.

A stable matching is a min-size popular matching and there is a simple and efficient algorithm to compute a max-size popular matching in $G$. However it is NP-hard to compute a max-utility popular matching when there is a utility function on the edge set.  A max-utility popular {\em mixed matching},  i.e., a probability distribution over matchings, could have a much higher utility than all popular matchings in $G$ and it can be computed in polynomial time. This mixed matching has a simple structure: it is of the form $\{(M, \frac{1}{2}), (M',\frac{1}{2})\}$ where $M$ and $M'$ are matchings in G. This structure is due to the self-duality of the linear program that gives rise to the polytope of popular fractional matchings in $G$.