Stable roommates problem with random preferences

DOI10.1088/1742-5468/2015/01/P01020MaRDI QIDQ3302097zbMATH OpenOpenAlexFDO

Authors S. Mertens

Publication date 11 August 2020

Published in Journal of Statistical Mechanics: Theory and Experiment (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1401.5269

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Disordered systems (random Ising models, random Schrödinger operators, etc.) in equilibrium statistical mechanics (82B44) Matching models (91B68)

Abstract: The stable roommates problem with $n$ agents has worst case complexity $O(n^2)$ in time and space. Random instances can be solved faster and with less memory, however. We introduce an algorithm that has average time and space complexity $O(n^{f}rac32)$ for random instances. We use this algorithm to simulate large instances of the stable roommates problem and to measure the probabilty $p_n$ that a random instance of size $n$ admits a stable matching. Our data supports the conjecture that $p_n=Theta(n^{-1/4})$.

Recommendations

• The ``stable roommates problem with random preferences
• On random stable partitions
• On a Random Instance of a ‘Stable Roommates’ Problem: Likely Behavior of the Proposal Algorithm
• The Average Number of Stable Matchings
• An upper bound for the solvability probability of a random stable roommates instance

Cites work

• Algorithmics of matching under preferences. With a foreword by Kurt Mehlhorn
• An efficient algorithm for the “stable roommates” problem
• An upper bound for the solvability probability of a random stable roommates instance
• Beauty and distance in the stable marriage problem
• College Admissions and the Stability of Marriage
• scientific article; zbMATH DE number 45086 (Why is no real title available?)
• scientific article; zbMATH DE number 48303 (Why is no real title available?)
• Random stable matchings
• Small random instances of the stable roommates problem
• The ``stable roommates problem with random preferences
• The nature of computation

Cited in

(12)

• The stable roommates problem with choice functions
• Matching with externalities: the role of prudence and social connectedness in stability
• Exchange-stability in roommate problems
• The Stable Roommates Problem with Short Lists
• On the stable matchings that can be reached when the agents go marching in one by one
• The Stable Roommates Problem with Ties
• Small random instances of the stable roommates problem
• An upper bound for the solvability probability of a random stable roommates instance
• Random stable matchings
• A note on roommate problems with a limited number of rooms
• Coalitional stability in matching problems with externalities and random preferences
• The ``stable roommates problem with random preferences

This page was built for publication: Stable roommates problem with random preferences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3302097)