Uncoordinated two-sided matching markets

ABSTRACT

Various economic interactions can be modeled as two-sided markets. A central solution concept to these markets are stable matchings, introduced by Gale and Shapley. It is well known that stable matchings can be computed in polynomial time, but many real-life markets lack a central authority to match agents. In those markets, matchings are formed by actions of self-interested agents. Knuth introduced uncoordinated two-sided markets and showed that the uncoordinated better response dynamics may cycle. However, Roth and Vande Vate showed that the random better response dynamics converges to a stable matching with probability one, but did not address the question of convergence time.

In this paper, we give an exponential lower bound for the convergence time of the random better response dynamics in two-sided markets. We also extend the results for the better response dynamics to the best response dynamics, i.e., we present a cycle of best responses, and prove that the random best response dynamics converges to a stable matching with probability one, but its convergence time is exponential. Additionally, we identify the special class of correlated matroid two-sided markets with real-life applications for which we prove that the random best response dynamics converges in expected polynomial time.

References

1. D. Abraham, A. Levavi, D. Manlove, and G. O'Malley. The stable roommates problem with globally-ranked pairs. In Proceedings of the 3rd International Workshop on Internet and Network Economics (WINE), pages 431--444, 2007.
2. H. Ackermann, P. W. Goldberg, V. S. Mirrokni, H. Röglin, and B. Vöcking. A unified approach to congestion games and two-sided markets. In Proceedings of the 3rd International Workshop on Internet and Network Economics (WINE), pages 30--41, 2007.
3. H. Ackermann, H. Röglin, and B. Vöcking. Pure Nash equilibria in player-specific and weighted congestion games. In Proceedings of the 2nd International Workshop on Internet and Network Economics (WINE), pages 50--61, 2006.
4. F. Echenique and J. Oviedo. A theory of stability in many-to-many matching markets. Theoretical Economics, 1(2):233--273, 2006.
5. W. Feller. An Introduction to Probability Theory and Its Applications. John Wiley & Sons, Inc., 2nd edition, 1957.
6. T. Fleiner. A fixed-point approach to stable matchings and some applications. Mathematics of Operations Research, 28(1):103--126, 2003.
7. L. Fleischer, M. X. Goemans, V. S. Mirrokni, and M. Sviridenko. Tight approximation algorithms for maximum general assignment problems. In Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 611--620, 2006.
8. D. Gale and L. S. Shapley. College admissions and the stability of marriage. American Mathematical Monthly, 69:9--15, 1962.
9. M. X. Goemans, E. L. Li, V. S. Mirrokni, and M. Thottan. Market sharing games applied to content distribution in ad-hoc networks. In Proceedings of the 5th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc), pages 55--66, 2004.
10. D. Gusfield and R. W. Irving. The stable Marriage Problem: Structure and Algorithms. MIT Press, 1989.
11. C. Hoffman, A. E. Holroyd, and Y. Peres. A stable marriage of poisson and lebesgue. Annals of Probability, 34(4):1241--1272, 2006.
12. A. S. Kelso and V. P. Crawford. Job matchings, coalition formation, and gross substitute. Econometrica, 50:1483--1504, 1982.
13. D. E. Knuth. Marriage Stables et leurs relations avec d'autres problèmes Combinatories. Les Presses de l'Université de Montréal, 1976.
14. D. Lebedev, F. Mathieu, L. Viennot, A.-T. Gai, J. Reynier, and F. de Montgolfier. On using matching theory to understand p2p network design. CoRR, abs/cs/0612108, 2006.
15. F. Mathieu. Upper bounds for stabilization in acyclic preference-based systems. In Proceedings of the 9th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), pages 372--382, 2007.
16. V. S. Mirrokni. Approximation Algorithms for Distributed and Selfish Agents. PhD thesis, Massachusetts Institute of Technology, 2005.
17. A. E. Roth. The evolution of the labor market for medical interns and residents: A case study in game theory. Journal of Political Economy, 92:991--1016, 1984.
18. A. E. Roth. The national residency matching program as a labor market. Journal of American Medical Association, 275(13):1054--1056, 1996.
19. A. E. Roth and M. A. O. Sotomayor. Two-sided Matching: A study in game-theoretic modeling and analysis. Cambridge University Press, 1990.
20. A. E. Roth and J. H. V. Vate. Random paths to stability in two-sided matching. Econometrica, 58(6):1475--1480, 1990.

Index Terms

• Applied computing

  • Law, social and behavioral sciences

    • Economics

• Theory of computation

  • Design and analysis of algorithms