Tata Institute of Fundamental Research

Popular Matchings in the Stable Marriage Problem

STCS Colloquium
Speaker: Kavitha Telikepalli
Organiser: Piyush Srivastava
Date: Tuesday, 5 Sep 2017, 16:00 to 17:00
Venue: A-201 (STCS Seminar Room)

(Scan to add to calendar)
Abstract:  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 Gardenfors 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$.