Abstract
We consider the loss in social welfare caused by individual rationality in matching scenarios. We give both theoretical and experimental results comparing stable matchings with socially optimal ones, as well as studying the convergence of various natural algorithms to stable matchings. Our main goal is to design mechanisms that incentivize agents to participate in matchings that are socially desirable. We show that theoretically, the loss in social welfare caused by strategic behavior can be substantial. However, under some natural distributions of utilities, we show experimentally that stable matchings attain close to the optimal social welfare. Furthermore, for certain graph structures, simple greedy algorithms for partner-switching (some without convergence guarantees) converge to stability remarkably quickly in expectation. Even when stable matchings are significantly socially suboptimal, slight changes in incentives can provide good solutions. We derive conditions for the existence of approximately stable matchings that are also close to socially optimal, which demonstrates that adding small switching costs can make socially optimal matchings stable.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Roth, A.E., Peranson, E.: The redesign of the matching market for American physicians: Some engineering aspects of economic design. American Economic Review 89(4), 748–780 (1999)
Roth, A.E., Sonmez, T., Ünver, M.U.: Pairwise kidney exchange. Journal of Economic Theory 125(2), 151–188 (2005)
Roth, A.E., Sotomayor, M.: Two-Sided Matching: A Study in Game-Theoretic Modeling and Analysis. Econometric Society Monograph Series. Cambridge University Press, Cambridge (1990)
Roth, A.E., Xing, X.: Jumping the gun: Imperfections and institutions related to the timing of market transactions. The American Economic Review 84(4) (1994)
Immorlica, N., Mahdian, M.: Marriage, Honesty, and Stability. In: Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (2005)
Dawande, M., Kumar, S., Mookerjee, V., Sriskandarajah, C.: Maximum Commonality Problems: Applications and Analysis. Management Science 54(1) (2008)
Abdulkadiroglu, A., Pathak, P., Roth, A.: The New York City High School Match. American Economic Review 95(2), 364–367 (2005)
Abdulkadiroglu, A., Pathak, P., Roth, A.: Strategy-proofness versus Efficiency in Matching with Indifferences: Redesigning the NYC High School Match. American Economic Review (to appear, 2009)
Becker, G.: A Treatise On The Family. Family Process 22(1), 127–127 (1983)
Jovanovic, B.: Job Matching and the Theory of Turnover. The Journal of Political Economy 87(5), 972 (1979)
Abraham, D., Blum, A., Sandholm, T.: Clearing algorithms for barter exchange markets: enabling nationwide kidney exchanges. In: Proc. of ACM Conf. on Electronic Commerce, pp. 295–304. ACM Press, New York (2007)
Gale, D., Shapley, L.S.: College admissions and the stability of marriage. The American Mathematical Monthly 69(1), 9–15 (1962)
Irving, R., Leather, P., Gusfield, D.: An efficient algorithm for the ”optimal” stable marriage. Journal of the ACM (JACM) 34(3), 532–543 (1987)
Thaler, R., Sunstein, C.: Nudge. Yale University Press, New Haven (2008)
Ackermann, H., Goldberg, P., Mirrokni, V., Roglin, H., Vocking, B.: Uncoordinated two-sided markets. In: Proceedings of the 9th ACM Conference on Electronic Commerce, EC (2008)
Roth, A., Vande Vate, J.: Random Paths to Stability in Two-Sided Matching. Econometrica 58(6), 1475–1480 (1990)
Goemans, M., Li, L., Mirrokni, V., Thottan, M.: Market sharing games applied to content distribution in ad hoc networks. IEEE Journal on Selected Areas in Communications 24(5), 1020–1033 (2006)
Mirrokni, V.: Approximation Algorithms for Distributed and Selfish Agents. PhD thesis, Massachusetts Institute Of Technology (2005)
Das, S., Kamenica, E.: Two-sided bandits and the dating market. In: Proc. IJCAI, Edinburgh, UK, August 2005, pp. 947–952 (2005)
Anshelevich, E., Das, S., Naamad, Y.: Anarchy, Stability, and Utopia: Creating Better Matchings, http://www.cs.rpi.edu/~eanshel
Anshelevich, E., Dasgupta, A., Kleinberg, J., Tardos, E., Wexler, T., Roughgarden, T.: The price of stability for network design with fair cost allocation. In: Proc. FOCS, pp. 295–304 (2004)
Anshelevich, E., Dasgupta, A., Tardos, E., Wexler, T.: Near-optimal network design with selfish agents. In: Proceedings STOC, pp. 511–520. ACM Press, New York (2003)
Christodoulou, G., Koutsoupias, E.: On the Price of Anarchy and Stability of Correlated Equilibria of Linear Congestion Games. In: Brodal, G.S., Leonardi, S. (eds.) ESA 2005. LNCS, vol. 3669, pp. 59–70. Springer, Heidelberg (2005)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Anshelevich, E., Das, S., Naamad, Y. (2009). Anarchy, Stability, and Utopia: Creating Better Matchings. In: Mavronicolas, M., Papadopoulou, V.G. (eds) Algorithmic Game Theory. SAGT 2009. Lecture Notes in Computer Science, vol 5814. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-04645-2_15
Download citation
DOI: https://doi.org/10.1007/978-3-642-04645-2_15
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-04644-5
Online ISBN: 978-3-642-04645-2
eBook Packages: Computer ScienceComputer Science (R0)