 On random stable partitionsBoris Pittel ()
International Journal of Game Theory, 2019, vol. 48, issue 2, No 6, 433-480 Abstract: Abstract It is well known that the one-sided stable matching problem (“stable roommates problem”) does not necessarily have a solution. We had found that, for the independent, uniformly random preference lists, the expected number of solutions converges to $$e^{1/2}$$ e 1 / 2 as n, the number of members, grows, and with Rob Irving we proved that the limiting probability of solvability is below $$e^{1/2}/2$$ e 1 / 2 / 2 , at most. Stephan Mertens’s extensive numerics compelled him to conjecture that this probability is of order $$n^{-1/4}$$ n - 1 / 4 . Jimmy Tan introduced a notion of a stable cyclic partition, and proved existence of such a partition for every system of members’ preferences, discovering that presence of odd cycles in a stable partition is equivalent to absence of a stable matching. In this paper we show that the expected number of stable partitions with odd cycles grows as $$n^{1/4}$$ n 1 / 4 . However the standard deviation of that number is of order $$n^{3/8}\gg n^{1/4}$$ n 3 / 8 ≫ n 1 / 4 , i.e. too large to conclude that the odd cycles exist with probability $$1-o(1)$$ 1 - o ( 1 ) . Still, as a byproduct, we show that with probability $$1-o(1)$$ 1 - o ( 1 ) the fraction of members with more than one stable “predecessor” is of order $$n^{-1/2+o(1)}$$ n - 1 / 2 + o ( 1 ) . Furthermore, with probability $$1-o(1)$$ 1 - o ( 1 ) the average rank of a predecessor in every stable partition is of order $$n^{1/2}$$ n 1 / 2 . The likely size of the largest stable matching is $$n/2-O(n^{1/4+o(1)})$$ n / 2 - O ( n 1 / 4 + o ( 1 ) ) , and the likely number of pairs of unmatched members blocking the optimal complete matching is $$O(n^{3/4+o(1)})$$ O ( n 3 / 4 + o ( 1 ) ) . Keywords: Stable matchings; Partitions; Random preferences; Asymptotics; 05C30; 05C80; 05C05; 34E05; 60C05 (search for similar items in EconPapers) Downloads: (external link) Related works: Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text Persistent link: https://EconPapers.repec.org/RePEc:spr:jogath:v:48:y:2019:i:2:d:10.1007_s00182-018-0635-9 Ordering information: This journal article can be ordered from DOI: 10.1007/s00182-018-0635-9 Access Statistics for this article International Journal of Game Theory is currently edited by Shmuel Zamir, Vijay Krishna and Bernhard von Stengel More articles in International Journal of Game Theory from Springer, Game Theory Society |
Is your work missing from RePEc? Here is how to contribute.
Questions or problems? Check the EconPapers FAQ or send mail to .
EconPapers is hosted by the
School of Business at Örebro University.