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.
Author details: | Ágnes CsehORCiDGND, Attila Juhos |
---|---|
DOI: | https://doi.org/10.1145/3434427 |
ISSN: | 2167-8375 |
ISSN: | 2167-8383 |
Title of parent work (English): | ACM Transactions on Economics and Computation / Association for Computing Machinery |
Publisher: | Association for Computing Machinery |
Place of publishing: | New York |
Publication type: | Article |
Language: | English |
Date of first publication: | 2021/01/02 |
Publication year: | 2021 |
Release date: | 2024/05/23 |
Tag: | Stable marriage; acyclic preferences; intransitivity; poset; stable matching; strongly stable matching; super stable matching; weakly |
Volume: | 9 |
Issue: | 1 |
Article number: | 7 |
Number of pages: | 28 |
Funding 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] |
Organizational units: | Digital Engineering Fakultät / Hasso-Plattner-Institut für Digital Engineering GmbH |
DDC classification: | 0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 004 Datenverarbeitung; Informatik |
Peer review: | Referiert |