Abstract
We study the dynamics of stable marriage and stable roommates markets. Our main tool is the incremental algorithm of Roth and Vande Vate and its generalization by Tan and Hsueh. Beyond proposing alternative proofs for known results, we also generalize some of them to the nonbipartite case. In particular, we show that the lastcomer gets his best stable partner in both incremental algorithms. Consequently, we confirm that it is better to arrive later than earlier to a stable roommates market. We also prove that when the equilibrium is restored after the arrival of a new agent, some agents will be better off under any stable solution for the new market than at any stable solution for the original market. We also propose a procedure to find these agents.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Abeledo H, Rothblum UG (1995) Paths to marriage stability. Discret Appl Math 63:1–12
Abraham DJ, Biró P, Manlove DF (2006) “Almost stable” matchings in the roommates problem. In: Proceedings of WAOA 2005: the 3rd workshop on approximation and online algorithms. Lecture notes in computer science, vol 3879, pp 1–14
Aharoni R, Fleiner T (2003) On a lemma of Scarf. J Comb Theory Ser B 87:72–80
Angelov N (2006) Modelling firm mergers as a roommates problem (preprint)
Blum Y, Rothblum UG (2002) “Timing is everything” and marital bliss. J Econ Theory 103:429-443
Blum Y, Roth AE, Rothblum UG (1997) Vacancy chains and equilibration in senior-level labor markets. J Econ Theory 76:362–411
Cantala D (2004) Restabilizing matching markets at senior level. Games Econ Behav 48:1–17
Cechlárová K (2002) Randomized matching mechanism revisited (preprint)
Cechlárová K, Fleiner T (2005) On a generalization of the stable roommates problem. ACM Trans Algorithms 1(1):143–156
Diamantoudi E, Miyagawa E, Xue L (2004) Random paths to stability in the roommates problem. Games Econ Behav 48:18–28
Eriksson K, Strimling P (2005) How unstable are matchings from the decentralized mate search? (preprint)
Gale D, Shapley LS (1962) College admissions and stability of marriage. Am Math Mon 69:9–15
Gale D, Sotomayor M (1985) Some remarks on the stable matching problem. Discret Appl Math 11:223–232
Gusfield D, Irving RW (1990) The stable marriage problem: structure and algorithms. MIT, Cambridge
Inarra E, Larrea C, Molis E (2007) Random paths to P-stability in the roommate problem. Int J Game Theory (forthcoming)
Irving RW (1985) An efficient algorithm for the “stable roommates” problem. J Algorithms 6:577–595
Jackson MO, Watts A (2002) The evolution of social and economic networks. J Econ Theory 106:265–295
Knuth DE (1976) Mariages stables. Les Presses de l’Universite de Montreal, Montreal
Kojima F, Ünver U (2007) Random paths to pairwise stability in many-to-many matching problems: a study on market equilibration. Int J Game Theory (forthcoming)
Ma J (1996) On randomised matching mechanism. Econ Theory 8(2):377–381
McVitie D, Wilson LB (1970) Stable marriage assignment for unequal sets. BIT 10:295–309
Pittel BG, Irving RW (1994) An upper bound for the solvability of a random stable roommates instance. Random Struct Algorithms 5:465–486
Roth AE, Sotomayor M (1990) Two-sided matching: a study in game-theoretic modeling and analysis. In: Econometric society monograph series. Cambridge University Press, London
Roth AE, Vande Vate JH (1990) Random paths to stability in two-sided matching. Econometrica 58:1475–1480
Roth AE, Sönmez T, Ünver U (2005) Pairwise kidney exchange. J Econ Theory 125(2):151–188
Scarf HE (1967) The core of an N person game. Econometrica 35:50–69
Tan JJM (1991) A necessary and sufficient condition for the existence of a complete stable matching. J Algorithms 12:154–178
Tan JJM, Hsueh JC (1995) A generalisation of the stable matching problem. Discret Appl Math 59:87–102
Yuan Y (1996) Residence exchange wanted: a stable residence exchange problem. Eur J Oper Res 90:536–546
Author information
Authors and Affiliations
Corresponding author
Additional information
K. Cechlárová was supported by VEGA grant No. 1/3001/06 and Science and Technology Assistance Agency contract No. APVT-20-004104.
T. Fleiner was supported by the Bolyai research fellowship of the Hungarian Academy of Sciences and by the K60802 OTKA grant.
Rights and permissions
About this article
Cite this article
Biró, P., Cechlárová, K. & Fleiner, T. The dynamics of stable matchings and half-matchings for the stable marriage and roommates problems. Int J Game Theory 36, 333–352 (2008). https://doi.org/10.1007/s00182-007-0084-3
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00182-007-0084-3