at Google ScholarTitle data
Heeger, Klaus ; Cseh, Ágnes:
Popular matchings with weighted voters.
In: Games and Economic Behavior.
Vol. 144
(2024)
.
- pp. 300-328.
ISSN 0899-8256
DOI: https://doi.org/10.1016/j.geb.2024.01.015
Abstract in another language
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.
Further data
| Item Type: | Article in a journal |
|---|---|
| Refereed: | Yes |
| Keywords: | Popular matching; Stable matching; Complexity; Algorithm |
| Institutions of the University: | Faculties > Faculty of Mathematics, Physics und Computer Science > Department of Mathematics > Chair Mathematical Economics Faculties > Faculty of Mathematics, Physics und Computer Science > Department of Mathematics > Chair Dynamical Systems and Data |
| Result of work at the UBT: | Yes |
| DDC Subjects: | 000 Computer Science, information, general works > 004 Computer science 500 Science > 510 Mathematics |
| Date Deposited: | 14 Feb 2024 06:11 |
| Last Modified: | 14 Feb 2024 06:11 |
| URI: | https://eref.uni-bayreuth.de/id/eprint/88552 |