Popular matchings with weighted voters

Titelangaben

Heeger, Klaus ; Cseh, Ágnes:
Popular matchings with weighted voters.
In: Games and Economic Behavior. Bd. 144 (2024) . - S. 300-328.
ISSN 0899-8256
DOI: https://doi.org/10.1016/j.geb.2024.01.015

Volltext

Link zum Volltext (externe URL):

Abstract

We consider a natural generalization of the well-known Popular Matching problem where every vertex has a weight. We call a matching M more popular than matching M′ if the weight of vertices preferring M to M′ is larger than the weight of vertices preferring M′ to M. 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 c for some c>3 and all vertices on the other side have weight 1.