Popularity, Mixed Matchings, and Self-Duality

Chien-Chung Huang () and Telikepalli Kavitha ()
Additional contact information
Chien-Chung Huang: École Normale Supérieure, Université PSL, 75005 Paris, France
Telikepalli Kavitha: Tata Institute of Fundamental Research, Mumbai, Maharashtra 400005, India

Mathematics of Operations Research, 2021, vol. 46, issue 2, 405-427

Abstract: Our input instance is a bipartite graph G where each vertex has a preference list ranking its neighbors in a strict order of preference. A matching M is popular if there is no matching N such that the number of vertices that prefer N to M outnumber those that prefer M to N . Each edge is associated with a utility and we consider the problem of matching vertices in a popular and utility-optimal manner. It is known that it is NP-hard to compute a max-utility popular matching. So we consider mixed matchings : a mixed matching is a probability distribution or a lottery over matchings. Our main result is that the popular fractional matching polytope P G is half-integral and in the special case where a stable matching in G is a perfect matching, this polytope is integral. This implies that there is always a max-utility popular mixed matching which is the average of two integral matchings. So in order to implement a max-utility popular mixed matching in G , we need just a single random bit. We analyze the popular fractional matching polytope whose description may have exponentially many constraints via an extended formulation with a linear number of constraints. The linear program that gives rise to this formulation has an unusual property: self-duality . The self-duality of this LP plays a crucial role in our proof. Our result implies that a max-utility popular half-integral matching in G and also in the roommates problem (where the input graph need not be bipartite) can be computed in polynomial time.

Keywords: Primary: analysis of algorithms; bipartite graphs; matchings; LP duality; polytopes (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2020.1063 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:46:y:2021:i:2:p:405-427

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().