Robust Popular Matchings
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866917030845743104 |
|---|---|
| author | Bullinger, Martin Csáji, Gergely Gangam, Rohith Reddy Shahkar, Parnian |
| author_facet | Bullinger, Martin Csáji, Gergely Gangam, Rohith Reddy Shahkar, Parnian |
| contents | We study popularity for matchings under preferences. This solution concept captures matchings that do not lose against any other matching in a majority vote by the agents. A popular matching is said to be robust if it is popular among multiple instances. We present a polynomial-time algorithm for deciding whether there exists a robust popular matching if instances only differ with respect to the preferences of a single agent. The same method applies also to dominant matchings, a subclass of maximum-size popular matchings. By contrast, we obtain NP-completeness if two instances differ only by two agents of the same side or by a swap of two adjacent alternatives by two agents. The first hardness result applies to dominant matchings as well. Moreover, we find another complexity dichotomy based on preference completeness for the case where instances differ by making some options unavailable. We conclude by discussing related models, such as strong and mixed popularity. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_12653 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Robust Popular Matchings Bullinger, Martin Csáji, Gergely Gangam, Rohith Reddy Shahkar, Parnian Data Structures and Algorithms Computer Science and Game Theory We study popularity for matchings under preferences. This solution concept captures matchings that do not lose against any other matching in a majority vote by the agents. A popular matching is said to be robust if it is popular among multiple instances. We present a polynomial-time algorithm for deciding whether there exists a robust popular matching if instances only differ with respect to the preferences of a single agent. The same method applies also to dominant matchings, a subclass of maximum-size popular matchings. By contrast, we obtain NP-completeness if two instances differ only by two agents of the same side or by a swap of two adjacent alternatives by two agents. The first hardness result applies to dominant matchings as well. Moreover, we find another complexity dichotomy based on preference completeness for the case where instances differ by making some options unavailable. We conclude by discussing related models, such as strong and mixed popularity. |
| title | Robust Popular Matchings |
| topic | Data Structures and Algorithms Computer Science and Game Theory |
| url | https://arxiv.org/abs/2401.12653 |