Popular matchings with weighted voters

• 成果类型: Article
• 署名作者: Heeger, Klaus; Cseh, Agnes
• 署名单位: Technical University of Berlin; Ben-Gurion University of the Negev; University of Bayreuth
• 刊物名称: GAMES AND ECONOMIC BEHAVIOR
• ISSN/ISSBN: 0899-8256
• DOI: 10.1016/j.geb.2024.01.015
• 发表日期: 2024
• 页码: 300-328
• 关键词: Popular matching; stable matching; complexity; algorithm

摘要

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.