We consider popular matching problems in a stable marriage instance G. A matching M is popular if it does not lose a head-to-head election against any matching, where each vertex casts a vote for the matching where it gets a better assignment. Popular matchings always exist in G since every stable matching is popular. Algorithmic questions for several popular matching problems have been studied in the last few years: these include finding a max-size popular matching, finding a popular matching with our favorite edge(s) in it, finding a max-weight popular (mixed) matching when there are edge weights. We will see efficient algorithms for some of these problems.

Interestingly, all tractability results in popular matchings seem to reduce the popular matching problem to an appropriate question in either stable matchings or dominant matchings. Dominant matchings always exist in G and form a subclass of max-size popular matchings while stable matchings form a subclass of min-size popular matchings. We recently showed that deciding if G admits a popular matching that is neither stable nor dominant is NP-hard. This implies a tight 1/2-factor approximation for the max-weight popular matching problem in G and the hardness of finding a popular matching in a non-bipartite graph.

[Joint work with Agnes Cseh, Yuri Faenza, Chien-Chung Huang, Vladlena Powers, and Xingyu Zhang.]