JFLI/Univ. of Tokyo on Popularity and Matchings

Date: Wednesday July 11, 2018

Time: 10:30-12:00

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)  

 

Abstract:
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.

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *