Abstract
In any two-sided matching market, a stable matching can be found by a central agency using the deferred acceptance procedure of Gale and Shapley. But if the market is decentralized and information is incomplete then stability of the ensuing matching is not to be expected. Despite the prevalence of such matching situations, and the importance of stability, little theory exists concerning instability. We discuss various measures of instability and analyze how they interact with the structure of the underlying preferences. Our main result is that even the outcome of decentralized matching with incomplete information can be expected to be “almost stable” under reasonable assumptions.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Abraham D, Biró P, Manlove DF (2006) “Almost stable” matchings in the roommates problem. In: Proceedings of WAOA 2005. Springer Lecture Notes in Computer Science, vol 3879. pp 1–14
Alpern S, Reyniers D (1999) Strategic mating with homotypic preferences. J Theor Biol 198:71–88
Alpern S, Reyniers D (2005) Strategic mating with common preferences. J Theor Biol 237:337–354
Bergstrom CT, Real LA (2000) Towards a theory of mutual mate choice: Lessons from two-sided matching. Evol Ecol Res 2:493–508
Eriksson K, Strimling P (2005) How unstable are matchings from decentralized mate search?. unpublished manuscript
Eriksson K, Sjöstrand J, Strimling P (2007) Optimal expected rank in a two-sided secretary problem. Oper Res (to appear)
Gale D, Shapley L (1962) College admissions and the stability of marriage. Am Math Mon 69:9–15
Gusfield D, Irving RW (1989) The stable marriage problem: Structure and algorithms. MIT Press, Cambridge
Kagel JH, Roth AE (2000) The dynamics of reorganization in matching markets: A laboratory experiment motivated by a natural experiment. Quart J Econ 115:201–235
Kalick SM, Hamilton TE (1986) The matching hypothesis reexamined. J Personality Soc Pscyhol 51(4):673–682
Niederle M, Roth AE (2006) Making markets thick: How norms governing exploding offers affect market performance. preprint
Pittel B (1989) The average number of stable matchings. SIAM J Discrete Math 2:530–549
Roth AE, Sotomayor MAO (1990) Two-sided matching. Cambridge University Press, Cambridge
Roth AE, Xing X (1997) Turnaround time and bottlenecks in market clearing: Decentralized matching in the market for clinical psychologists. J Polit Econ 105:284–329
Simão J, Todd PM (2002) Modeling mate choice in monogamous mating systems with courtship. Adaptive Behav 10(2):113–136
Todd PM, Miller GF (1999) From pride and prejudice to persuasion: Satisficing in mate search. In: Gigerenzer G, Todd PM (eds). Simple heuristics that make us smart. Oxford University Press, Oxford, pp 287–308
Ünver MU (2005) On the survival of some unstable two-sided matching mechanisms. Int J Game Theory 33(2):239–254
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Eriksson, K., Häggström, O. Instability of matchings in decentralized markets with various preference structures. Int J Game Theory 36, 409–420 (2008). https://doi.org/10.1007/s00182-007-0081-6
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00182-007-0081-6