[Back]

R. Bredereck, J. Chen, U. Finnendahl, R. Niedermeier:
"Stable roommates with narcissistic, single-peaked, andsingle-crossing preferences";
Autonomous Agents and Multi-Agent Systems, 34 (2020), 1 - 29.

The classicalStable Roommatesproblem is to decide whether there exists a matchingof an even number of agents such that no two agents which are not matched to each otherwould prefer to be with each other rather than with their respectively assigned partners. WeinvestigateStable Roommateswith complete (i.e., every agent can be matched with anyother agent) or incomplete preferences, with ties (i.e., two agents are considered of equal valueto some agent) or without ties. It is known that in general allowing ties makes the problem NP-complete. We provide algorithms forStable Roommatesthat are, compared to those in theliterature, more efficient when the input preferences are complete and have some structuralproperty, such as being narcissistic, single-peaked, and single-crossing. However, when thepreferences are incomplete and have ties, we show that being single-peaked and single-crossing does not reduce the computational complexity-Stable RoommatesremainsNP-complete.

http://dx.doi.org/10.1007/s10458-020-09470-x

https://publik.tuwien.ac.at/files/publik_293434.pdf