Anarchy, Stability, and Utopia: Creating Better Matchings | SpringerLink
Skip to main content

Anarchy, Stability, and Utopia: Creating Better Matchings

  • Conference paper
Algorithmic Game Theory (SAGT 2009)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 5814))

Included in the following conference series:

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.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. 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)

    Article  Google Scholar 

  2. Roth, A.E., Sonmez, T., Ünver, M.U.: Pairwise kidney exchange. Journal of Economic Theory 125(2), 151–188 (2005)

    Article  MATH  MathSciNet  Google Scholar 

  3. 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)

    MATH  Google Scholar 

  4. 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)

    Google Scholar 

  5. Immorlica, N., Mahdian, M.: Marriage, Honesty, and Stability. In: Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (2005)

    Google Scholar 

  6. Dawande, M., Kumar, S., Mookerjee, V., Sriskandarajah, C.: Maximum Commonality Problems: Applications and Analysis. Management Science 54(1) (2008)

    Google Scholar 

  7. Abdulkadiroglu, A., Pathak, P., Roth, A.: The New York City High School Match. American Economic Review 95(2), 364–367 (2005)

    Article  Google Scholar 

  8. 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)

    Google Scholar 

  9. Becker, G.: A Treatise On The Family. Family Process 22(1), 127–127 (1983)

    Google Scholar 

  10. Jovanovic, B.: Job Matching and the Theory of Turnover. The Journal of Political Economy 87(5), 972 (1979)

    Article  MathSciNet  Google Scholar 

  11. 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)

    Google Scholar 

  12. Gale, D., Shapley, L.S.: College admissions and the stability of marriage. The American Mathematical Monthly 69(1), 9–15 (1962)

    Article  MATH  MathSciNet  Google Scholar 

  13. Irving, R., Leather, P., Gusfield, D.: An efficient algorithm for the ”optimal” stable marriage. Journal of the ACM (JACM) 34(3), 532–543 (1987)

    Article  MathSciNet  Google Scholar 

  14. Thaler, R., Sunstein, C.: Nudge. Yale University Press, New Haven (2008)

    Google Scholar 

  15. 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)

    Google Scholar 

  16. Roth, A., Vande Vate, J.: Random Paths to Stability in Two-Sided Matching. Econometrica 58(6), 1475–1480 (1990)

    Article  MATH  MathSciNet  Google Scholar 

  17. 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)

    Article  Google Scholar 

  18. Mirrokni, V.: Approximation Algorithms for Distributed and Selfish Agents. PhD thesis, Massachusetts Institute Of Technology (2005)

    Google Scholar 

  19. Das, S., Kamenica, E.: Two-sided bandits and the dating market. In: Proc. IJCAI, Edinburgh, UK, August 2005, pp. 947–952 (2005)

    Google Scholar 

  20. Anshelevich, E., Das, S., Naamad, Y.: Anarchy, Stability, and Utopia: Creating Better Matchings, http://www.cs.rpi.edu/~eanshel

  21. 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)

    Google Scholar 

  22. 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)

    Google Scholar 

  23. 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)

    Chapter  Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Editor information

Editors and Affiliations

Rights and permissions

Reprints 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)

Publish with us

Policies and ethics