Hostname: page-component-586b7cd67f-2brh9 Total loading time: 0 Render date: 2024-11-22T06:58:43.220Z Has data issue: false hasContentIssue false
  • English
  • Français

On a Random Instance of a ‘Stable Roommates’ Problem: Likely Behavior of the Proposal Algorithm

Published online by Cambridge University Press:  12 September 2008

Boris Pittel
Boris Pittel
Affiliation:
Department of Mathematics, The Ohio State University
Get access Rights & Permissions [Opens in a new window]

Abstract

In a set of even cardinality n, each member ranks all the others in order of preference. A stable matching is a partition of the set into n/2 pairs, with the property that no two unpaired members both prefer each other to their partners under matching. It is known that for some problem instances no stable matching exists. In 1985, Irving found an O(n2) two-phase algorithm that would determine, for any instance, whether a stable matching exists, and if so, would find such a matching. Recently, Tan proved that Irving's algorithm, with a modified second phase, always finds a stable cyclic partition of the members set, which is a stable matching when each cycle has length two. In this paper we study a likely behavior of the algorithm under the assumption that an instance of the ranking system is chosen uniformly at random. We prove that the likely number of basic steps, i.e. the individual proposals in the first phase and the rotation eliminations, involving subsets of members in the second phase, is O(n log n), and that the likely size of a rotation is O((n log n)1/2). We establish a ‘hyperbola law’ analogous to our past result on stable marriages. It states that at every step of the second phase, the product of the rank of proposers and the rank of proposal holders is asymptotic, in probability, to n3. We show that every stable cyclic partition is likely to be almost a stable matching, in the sense that at most O((n log n)1/2) members can be involved in the cycles of length three or more.

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 2 , Issue 1 , March 1993 , pp. 53 - 92
Copyright
Copyright © Cambridge University Press 1993

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Bollobáas, B. (1985) Random Graphs, Academic Press.Google Scholar
[2]Breiman, L. (1968) Probability, Addison-Wesley, Reading, MA.Google Scholar
[3]Chernoff, H. (1952) A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. Ann. Math. Statist. 23 493–509.CrossRefGoogle Scholar
[4]Darling, D. A. (1953) On a class of problems related to the random division of an interval. Arm. Math. Statist. 24 239–253.CrossRefGoogle Scholar
[5]Devroye, L. (1981) Laws of the iterated logarithm for order statistics of uniform spacings. Ann. Probab. 9 860–867.CrossRefGoogle Scholar
[6]Devroye, L. (1982) A loglog law for maximal uniform spacings. Ann. Probab. 10 863–868.CrossRefGoogle Scholar
[7]Durrett, R. (1991) Probability: Theory and Examples, Wadsworth & Brooks, California.Google Scholar
[8]Erdős, P. and Rényi, A. (1966) On the existence of a factor of degree one of a connected random graph. Acta Math. Inst. Acad. Sci. Hungar. 17 359–368.CrossRefGoogle Scholar
[9]Gusfield, D. and Irving, R. W. (1989) The Stable Marriage Problem, (Structure and Algorithms), The MIT Press, Cambridge.Google Scholar
[10]Gale, D. and Shapley, L. S. (1962) College admissions and the stability of marriage. Amer. Math. Monthly 69 9–15.CrossRefGoogle Scholar
[11]Hoeffding, W. (1963) Probability inequalities for sums of bounded random variables. J. Amer. Stat. Assoc. 58 13–30.CrossRefGoogle Scholar
[12]Irving, R. W. (1985) An efficient algorithm for the stable room-mates problem. J. Algorithms 6 577–595.CrossRefGoogle Scholar
[13]Irving, R. W. (1986) On the stable room-mates problem, University of Glasgow, Department of Computing Science, Research Report CSC/86/R5 1–20.Google Scholar
[14]Irving, R. W. (1991) Personal communication.Google Scholar
[15]Karlin, S. (1981) Some natural viability systems for a multiallelic locus: a theoretical study. Genetics 97 457–473.Google Scholar
[16]Kingman, J. F. C. (1988) Typical polymorphisms maintained by selection at a single locus. J. Appl. Prob. 25A 113–125.CrossRefGoogle Scholar
[17]Kingman, J. F. C. (1989) Maxima of random quadratic forms on a simplex. Probability, Statistics and mathematics, Papers in Honor of Samuel Karlin 123–140.CrossRefGoogle Scholar
[18]Knuth, D. E. (1976) Marriages Stables et leurs relations avec d'autres problémes combinatoires, Les Presses de l'Université de Montréal, Montreal.Google Scholar
[19]Knuth, D. E., Motwani, R. and Pittel, B. (1990) Stable Husbands. Random Structures and Algorithms 1 1–14.CrossRefGoogle Scholar
[20]Levy, P. (1939) Sur la division d'un segment par des points choisis au hasard. Comptes Rendus Acad. Sci. Paris 208 147–149.Google Scholar
[21]McVitie, D. G. and Wilson, L. B. (1971) The stable marriage problem. Commun. ACM 14 486–492.CrossRefGoogle Scholar
[22]Pittel, B. (1993) On a stable roommates problem with random preferences. Ann. Probab. (forthcoming)Google Scholar
[23]Pittel, B. (1989) The average number of stable matchings. SIAM J. Disc. Math. 2 530–549.CrossRefGoogle Scholar
[24]Pittel, B. (1992) On likely solutions of a stable marriage problem. Ann. Appl. Probab. 2 358–401.Google Scholar
[25]Roth, A. E. and Sotomayor, M. (1990) Two Sided Matching: A Study in Game-Theoretic Modelling and Analysis, Cambridge University Press, Econometrics Series.Google Scholar
[26]Shubik, M. (1982) Game Theory in the Social Sciences: Concepts and Solutions, MIT Press, Cambridge, MA.Google Scholar
[27]Tan, Jimmy J. M. (1991) A necessary and sufficient condition for the existence of a complete stable matching. J. Algorithms 12 1–25.Google Scholar
[28]Wilson, L. B. (1972) An analysis of the stable assignment problem. BIT 12 569–575.Google Scholar