Date: Wednesday July 11, 2018
Place: University of Tokyo, Seminar AD, 3rd Floor, Eng. 6 Building
Title: Popularity, Mixed Matchings, and Self-duality
Speaker: Dr. Chien-Chung Huang (CNRS and ENS, France)
We consider the problem of matching applicants to jobs under two-sided preferences in a popular and utility-optimal manner. Our input instance is a bipartite graph G with a utility function where each vertex has a preference list ranking its neighbors in a strict order of preference. A matching M is popular if
the number of vertices that prefer M to T is higher than the number of vertices that prefer T to M for all matchings T in G. A mixed matching is a probability distribution over (finitely many) matchings.
Motivated by the fact that a popular mixed matching could have a much higher utility than all popular matchings, we study the popular fractional matching polytope. Our main result is that this polytope is half-integral (and in the special case where a stable matching is a perfect matching, this polytope is integral), implying that there is always a max-utility popular mixed matching
over only two matchings, which can be computed in polynomial time.
An immediate consequence is that in order to implement a max-utility popular mixed matching in G, we need just one single random bit.
We analyze the popular fractional matching polytope whose description may have exponentially many constraints . The linear program that gives rise to this formulation has an unusual property: self-duality. In other words, this linear program is exactly identical to its dual program. This is a rare case where an LP of a natural problem has such a property. The self- duality of the LP plays a crucial role in our proof of the half-integrality of the polytope. To complement this result, we also show that the problem of computing a max-utility popular (integral) matching is NP- hard.