Pairwise preferences in the stable marriage problem
- We study the classical, two-sided stable marriage problem under pairwise preferences. In the most general setting, agents are allowed to express their preferences as comparisons of any two of their edges, and they also have the right to declare a draw or even withdraw from such a comparison. This freedom is then gradually restricted as we specify six stages of orderedness in the preferences, ending with the classical case of strictly ordered lists. We study all cases occurring when combining the three known notions of stability-weak, strong, and super-stability-under the assumption that each side of the bipartite market obtains one of the six degrees of orderedness. By designing three polynomial algorithms and two NP-completeness proofs, we determine the complexity of all cases not yet known and thus give an exact boundary in terms of preference structure between tractable and intractable cases.
Verfasserangaben: | Ágnes CsehORCiDGND, Attila Juhos |
---|---|
DOI: | https://doi.org/10.1145/3434427 |
ISSN: | 2167-8375 |
ISSN: | 2167-8383 |
Titel des übergeordneten Werks (Englisch): | ACM Transactions on Economics and Computation / Association for Computing Machinery |
Verlag: | Association for Computing Machinery |
Verlagsort: | New York |
Publikationstyp: | Wissenschaftlicher Artikel |
Sprache: | Englisch |
Datum der Erstveröffentlichung: | 02.01.2021 |
Erscheinungsjahr: | 2021 |
Datum der Freischaltung: | 23.05.2024 |
Freies Schlagwort / Tag: | Stable marriage; acyclic preferences; intransitivity; poset; stable matching; strongly stable matching; super stable matching; weakly |
Band: | 9 |
Ausgabe: | 1 |
Aufsatznummer: | 7 |
Seitenanzahl: | 28 |
Fördernde Institution: | Hungarian Academy of Sciences under its Momentum Programme [LP2016-3/2020]; OTKAOrszagos Tudomanyos Kutatasi Alapprogramok (OTKA) [K128611]; COST Action European Network for Game Theory [CA16228] |
Organisationseinheiten: | Digital Engineering Fakultät / Hasso-Plattner-Institut für Digital Engineering GmbH |
DDC-Klassifikation: | 0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 004 Datenverarbeitung; Informatik |
Peer Review: | Referiert |