Stable roommates with narcissistic, single-peaked, and single-crossing preferences

Stable matching problems have long been studied in algorithmic game theory and computer science. The Stable Roommates problem is a well-known variant where agents are matched in pairs, avoiding mutual preferences for alternative partners. Prior research has shown that when preferences are complete and strict, efficient algorithms exist. However, when preferences include ties or are incomplete, the problem becomes computationally harder. No prior work had resolved how structural properties like narcissism, single-peakedness, or single-crossing affect computational complexity in the presence of ties. This gap motivated the current investigation into how these properties influence the problem's tractability.

The authors aimed to analyze the computational complexity of the Stable Roommates problem under various preference structures. They focused on whether structural properties like narcissistic, single-peaked, and single-crossing preferences could simplify the problem when preferences are complete. Additionally, they sought to determine if these properties could reduce complexity when preferences are incomplete and include ties. The study's motivation was to clarify the boundary between tractable and intractable cases of the problem.

The researchers used theoretical analysis and algorithm design to study the Stable Roommates problem. They considered complete and incomplete preferences with and without ties. For complete preferences, they examined structural properties such as narcissism, single-peakedness, and single-crossing. They designed algorithms for these cases and analyzed their efficiency. For incomplete preferences with ties, they performed complexity analysis to determine whether structural properties could reduce computational hardness. The methods combined algorithm design with reductions from known NP-complete problems.

The study found that when preferences are complete and have structural properties like narcissism, single-peakedness, and single-crossing, the Stable Roommates problem can be solved more efficiently than in general cases. The authors developed algorithms that outperform existing ones for these structured inputs. However, when preferences are incomplete and include ties, even with single-peaked and single-crossing properties, the problem remains NP-complete. These findings highlight that structural properties can reduce computational complexity in some cases but not in others.

The authors concluded that structural properties such as narcissism, single-peakedness, and single-crossing can simplify the Stable Roommates problem when preferences are complete. However, these properties do not help when preferences are incomplete and include ties. The results clarify the boundary between tractable and intractable cases of the problem. The study contributes to understanding how preference structures affect computational complexity in stable matching problems.