at Google ScholarTitle data
Aziz, Haris ; Csáji, Gergely ; Cseh, Ágnes:
Computational Complexity of k-stable Matchings.
In: ACM Transactions on Economics and Computation.
Vol. 13
(2025)
Issue 1
.
- 5.
ISSN 2167-8383
DOI: https://doi.org/10.1145/3708507
Abstract in another language
We study deviations by a group of agents in the three main types of matching markets: the house allocation, the marriage, and the roommates models. For a given instance, we call a matching k-stable if no other matching exists that is more beneficial to at least k out of the n agents. The concept generalizes the recently studied majority stability. We prove that whereas the verification of k-stability for a given matching is polynomial-time solvable in all three models, the complexity of deciding whether a k-stable matching exists depends on (frac{k}{n}) and is characteristic of each model.
Further data
| Item Type: | Article in a journal |
|---|---|
| Refereed: | Yes |
| Keywords: | Stable matching; popular matching; majority stability; algorithm; complexity |
| Institutions of the University: | Faculties > Faculty of Mathematics, Physics und Computer Science > Department of Mathematics > Chair Mathematical Economics > Chair Mathematical Economics - Univ.-Prof. Dr. Jörg Rambau Faculties > Faculty of Mathematics, Physics und Computer Science > Department of Mathematics > Chair Dynamical Systems and Data > Chair Dynamical Systems and Data - Univ.-Prof. Dr. Peter Koltai |
| 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 2025 08:53 |
| Last Modified: | 14 Feb 2025 08:53 |
| URI: | https://eref.uni-bayreuth.de/id/eprint/92361 |