Combinatorial Optimization Reading Group - Lily Wang

Title: Popular Matchings

Abstract:

We introduce a variant of the stable matching problem on a bipartite graph G = (A [ P;E): for any node in A, from its ranking of its neighbours we can dene its ranking of matchings, which compares matchings on whether it's matched and if so, the preference order of the nodes it's matched to. The popular matching problem asks whether there is a matching M such that for every other matching M0, more nodes in A prefer M to M' than M' to M. We'll discuss the earliest known efficient algorithms for finding popular matchings over strict preference lists and in the general case with ties, and compare the complexity of the popular matching problem with the max-cardinality matching problem.