Popular matchings with weighted voters
Klaus Heeger, Ágnes Cseh
Abstract
We consider a natural generalization of the well-known POPULAR MATCHING problem where every vertex has a weight. We call a matching 𝑀 more popular than matching 𝑀′ if the weight of vertices preferring 𝑀 to 𝑀′ is larger than the weight of vertices preferring 𝑀′ to 𝑀. For this case, we show that it is NP-hard to find a popular matching. Our main result is a polynomial-time algorithm that delivers a popular matching or a proof for its non-existence in instances where all vertices on one side have weight 𝑐 for some 𝑐 > 3 and all vertices on the other side have weight 1.
Keywords: Popular matching, Stable matching, Complexity, Algorithm
