hu / en

Popular matchings with weighted voters – new research article by Ágnes Cseh and Klaus Heeger

 

 

Popular matchings with weighted voters

 

Klaus Heeger – Ágnes Cseh

Games and Economic Behavior, Volume 144, March 2024, Pages 300-328

 

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