DISTRIBUTED LEARNING OF EQUILIBRIA IN A ROUTING GAME
Abstract
We focus on the problem of learning equilibria in a particular routing game similar to the Wardrop traffic model. We describe a routing game played by a large number of players and present a distributed learning algorithm that we prove to converge weakly to equilibria for the system. The proof of convergence is based on a differential equation governing the global evolution of the system that is inferred from all the local evolutions of the agents in play. We prove that the differential equation converges with the help of Lyapunov techniques.
References
-
E. Altman , Y. Hayel and H. Kameda , Evolutionary Dynamics and Potential Games in Non-Cooperative Routing , Wireless Networks: Communication, Cooperation and Competition (WNC3 2007) ( 2007 ) . Google Scholar - M. Beckmann, C. B. McGuire, and C. B. Winsten. Studies in the economics of transportation. 1956 . Google Scholar
Petra Berenbrink , Distributed Selfish Load Balancing, SODA '06: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm (ACM, 2006) pp. 354–363. Google ScholarRichard Cole , Yevgeniy Dodis and Tim Roughgarden , How much can taxes help selfish routing?, Proceedings of the 4th ACM Conference on Electronic Commerce (EC-03) (ACM Press, 2003) pp. 98–107. Google ScholarR. Cominetti , J. R. Correa and N. E. Stier-Moses , Network Games with Atomic Players, Automata, Languages and Programming: Proceedings of the 33rd International Colloquium4051 (2006) pp. 525–536. Google Scholar-
Jean-Pierre Demailly , Analyse Numérique et Equations Différentielles ( Presses Universitaires de Grenoble , 1991 ) . Google Scholar E. Even-Dar , A. Kesselman and Y. Mansour , Convergence Time to Nash Equilibria, 30th International Conference on Automata, Languages and Programming (ICALP) (2003) pp. 502–513. Google Scholar- ACM Transactions on Algorithms 3(3), (2007), DOI: 10.1145/1273340.1273348. Google Scholar
Eyal Even-Dar and Yishay Mansour , Fast Convergence of Selfish Rerouting, SODA '05: Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms (Society for Industrial and Applied Mathematics, 2005) pp. 772–781. Google ScholarS. Fischer , H. Räcke and B. Vöcking , Fast Convergence to Wardrop Equilibria by Adaptive Sampling Methods, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing (2006) pp. 653–662. Google Scholar-
S. Fischer and B. Vocking , On the Evolution of Selfish Routing , Algorithms–ESA 2004: 12th Annual European Symposium, Proceedings ( 2004 ) . Google Scholar S. Fischer and B. Vöcking , Adaptive Routing with Stale Information, Proceedings of the twenty-fourth annual ACM SIGACT-SIGOPS symposium on Principles of distributed computing (2005) pp. 276–283. Google Scholar- Theoretical Computer Science 348(3), 217 (2005), DOI: 10.1016/j.tcs.2005.09.014. Crossref, Web of Science, Google Scholar
Paul W. Goldberg , Bounds for the Convergence Rate of Randomized Local Search in a Multiplayer Load-Balancing Game, PODC '04: Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing (ACM, 2004) pp. 131–140. Google Scholar- Games and Economic Behavior 22(2), 238 (1998), DOI: 10.1006/game.1997.0582. Crossref, Web of Science, Google Scholar
-
Morris W. Hirsch , Stephen Smale and Robert Devaney , Differential Equations, Dynamical Systems, and an Introduction to Chaos ( Elsevier Academic Press , 2003 ) . Google Scholar - Bulletin of the American Mathematical Society 4, 479 (2003). Google Scholar
- Discrete and Continuous Dynamical Systems-Series B 6(1), (2006). Google Scholar
E. Koutsoupias and C. Papadimitriou , Worst-case Equilibria, STACS99 (1999) pp. 404–413. Google Scholar-
M. A. L. Thathachar and K. S. Narendra , Learning Automata: An Introduction ( Prentice Hall , Englewood Cliffs , 1989 ) . Google Scholar -
H. J. Kushner , Approximation and Weak Convergence Methods for Random Processes, with Applications to Stochastic Systems Theory ( MIT Press , Cambridge, MA , 1984 ) . Google Scholar - Telecommunication Systems 17(4), 385 (2001), DOI: 10.1023/A:1016770831869. Crossref, Web of Science, Google Scholar
- Games and Economics Behavior 14, 124 (1996), DOI: 10.1006/game.1996.0044. Crossref, Web of Science, Google Scholar
- Proc. of the National Academy of Sciences 36, 48 (1950), DOI: 10.1073/pnas.36.1.48. Crossref, Web of Science, Google Scholar
- IEEE/ACM Transactions on Networking (TON) 1(5), 510 (1993), DOI: 10.1109/90.251910. Crossref, Web of Science, Google Scholar
- IEEE transactions on system, man, and cybernetics 24(5), (1994). Google Scholar
- International journal of Game Theory 2, 65 (1973), DOI: 10.1007/BF01737559. Crossref, Web of Science, Google Scholar
T. Roughgarden , How unfair is optimal routing?, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms (2002) pp. 203–204. Google Scholar- Journal of the ACM 49(2), 236 (2002), DOI: 10.1145/506147.506153. Crossref, Web of Science, Google Scholar
-
L. Olbrich , S. Fischer and B. Vöcking , Approximating Wardrop Equilibria with Finitely Many Agents , DISC07 ( 2007 ) . Google Scholar -
D. W. Stroock and S. R. S. Varadhan , Multidimensional Diffusion Processes ( Springer , 1979 ) . Google Scholar J. Wardrop , Some Theoretical Aspects of Road Traffic Research, Proceedings of the Institution of Civil Engineers1 (1952) pp. 352–362. Google Scholar-
Jörgen W. Weibull , Evolutionary Game Theory ( The MIT Press , 1995 ) . Google Scholar