World Scientific
  • Search
  •   
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×

System Upgrade on Tue, May 28th, 2024 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.
Special Issue on Unconventional ComputingNo Access

DISTRIBUTED LEARNING OF EQUILIBRIA IN A ROUTING GAME

    https://doi.org/10.1142/S012962640900016XCited by:3 (Source: Crossref)

    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 Berenbrinket al., Distributed Selfish Load Balancing, SODA '06: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm (ACM, 2006) pp. 354–363. Google Scholar
    • Richard 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 Scholar
    • R. 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
    • Eyal Even-Dar, Alexander Kesselman and Yishay Mansour, 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 Scholar
    • S. 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
    • L. Fleischer, Theoretical Computer Science 348(3), 217 (2005), DOI: 10.1016/j.tcs.2005.09.014. Crossref, Web of ScienceGoogle 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
    • C. Harris, Games and Economic Behavior 22(2), 238 (1998), DOI: 10.1006/game.1997.0582. Crossref, Web of ScienceGoogle Scholar
    • Morris W.   Hirsch , Stephen   Smale and Robert   Devaney , Differential Equations, Dynamical Systems, and an Introduction to Chaos ( Elsevier Academic Press , 2003 ) . Google Scholar
    • J. Hofbauer and K. Sigmund, Bulletin of the American Mathematical Society 4, 479 (2003). Google Scholar
    • J. Hofbauer and S. Sorin, 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
    • L. Libman and A. Orda, Telecommunication Systems 17(4), 385 (2001), DOI: 10.1023/A:1016770831869. Crossref, Web of ScienceGoogle Scholar
    • D. Monderer and L. S. Shapley, Games and Economics Behavior 14, 124 (1996), DOI: 10.1006/game.1996.0044. Crossref, Web of ScienceGoogle Scholar
    • John F. Nash, Proc. of the National Academy of Sciences 36, 48 (1950), DOI: 10.1073/pnas.36.1.48. Crossref, Web of ScienceGoogle Scholar
    • A. Orda, R. Rom and N. Shimkin, IEEE/ACM Transactions on Networking (TON) 1(5), 510 (1993), DOI: 10.1109/90.251910. Crossref, Web of ScienceGoogle Scholar
    • M. A. L. Thathachar, P. S. Sastry and V. V. Phansalkar, IEEE transactions on system, man, and cybernetics 24(5), (1994). Google Scholar
    • Robert W. Rosenthal, International journal of Game Theory 2, 65 (1973), DOI: 10.1007/BF01737559. Crossref, Web of ScienceGoogle 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
    • Tim Roughgarden and Éva Tardos, Journal of the ACM 49(2), 236 (2002), DOI: 10.1145/506147.506153. Crossref, Web of ScienceGoogle 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