Stable roommates with narcissistic, single-peaked, and single-crossing preferences
- PDF / 920,531 Bytes
- 29 Pages / 439.37 x 666.142 pts Page_size
- 81 Downloads / 172 Views
(2020) 34:53
Stable roommates with narcissistic, single-peaked, and single-crossing preferences Robert Bredereck1 · Jiehua Chen2 · Ugo Paavo Finnendahl1 · Rolf Niedermeier1
© The Author(s) 2020
Abstract The classical Stable Roommates problem is to decide whether there exists a matching of an even number of agents such that no two agents which are not matched to each other would prefer to be with each other rather than with their respectively assigned partners. We investigate Stable Roommates with complete (i.e., every agent can be matched with any other agent) or incomplete preferences, with ties (i.e., two agents are considered of equal value to some agent) or without ties. It is known that in general allowing ties makes the problem NPcomplete. We provide algorithms for Stable Roommates that are, compared to those in the literature, more efficient when the input preferences are complete and have some structural property, such as being narcissistic, single-peaked, and single-crossing. However, when the preferences are incomplete and have ties, we show that being single-peaked and singlecrossing does not reduce the computational complexity—Stable Roommates remains NP-complete. Keywords Stable matching · Incomplete preferences · Preferences with ties · Restricted preference domains · NP-completeness · Polynomial-time algorithms
A preliminary version of this work appeared in the Proceedings of the 5th International Conference on Algorithmic Decision Theory (ADT ’17) [10], volume 10576 of LNCS, pages 315–330, Springer, 2017. This full version contains (more) proof details for Propositions 1, 2, Theorems 1, 2, and Proposition 8. Furthermore, the reduction used for our main result (Theorem 2) was replaced by a completely new reduction showing NP-hardness for the case of narcissistic, single-peaked, and single-crossing preferences (the preferences in the previous reduction were not narcissistic). Most of the work was done while all authors were with TU Berlin, with some additional work done while Jiehua Chen was with Ben-Gurion University, Israel, and with University of Warsaw, Poland.
B
Jiehua Chen [email protected] Robert Bredereck [email protected] Ugo Paavo Finnendahl [email protected] Rolf Niedermeier [email protected]
1
TU Berlin, Berlin, Germany
2
TU Wien, Vienna, Austria 0123456789().: V,-vol
123
53
Page 2 of 29
Autonomous Agents and Multi-Agent Systems
(2020) 34:53
1 Introduction Given 2n agents, each having preferences with regard to how suitable the other agents are as potential partners, the Stable Roommates problem is to decide whether there exists a matching, i.e., a set of disjoint pairs of the agents, without inducing a blocking pair. A blocking pair consists of two agents that are not matched to each other but prefer to be with each other rather than with their assigned partners. A matching without blocking pairs is called a stable matching. Stable Roommates was introduced by Gale and Shapley [26] in the 1960’s and has been studied extensively since th
Data Loading...
