Min-Cost Popular Matchings in a Hospitals/Residents Instance with Complete Preferences

We consider a matching problem in a hospitals/residents instance G, that is, a many-to-one matching instance, in which every vertex has a strict ranking of its neighbors and hospitals have capacities. A matching M is said to be popular if M does not lose an election against any matching in which vertices cast votes for one matching versus another. There are efficient algorithms to find popular matchings in G, but it is NP-hard to find a min-cost popular matching when edges have costs. When preferences are complete, there is a polynomial-time algorithm for this problem in the one-to-one setting. Interestingly, the set of popular matchings in a many-to-one instance can be richer than the set of popular matchings in the corresponding one-to-one instance obtained by cloning vertices. No polynomial-time algorithm is currently known for the min-cost popular matching problem with complete preferences in the many-to-one setting. We show a polynomial-time algorithm for this problem. Our algorithm includes a subroutine for computing a min-cost popular perfect matching; this subroutine also works for instances with incomplete preferences.

History: This manuscript was accepted for the Special Issue on Market Design.

Funding: T. Kavitha was supported by the Department of Atomic Energy, Government of India [Grant RTI4001]. K. Makino was partially supported by JSPS KAKENHI [Grant JP20H05967] and the joint project of Kyoto University and Toyota Motor Corporation titled “Advanced Mathematical Science for Mobility Society.”