Fast convergence of selfish rerouting

ABSTRACT

We consider n anonymous selfish users that route their communication through m parallel links. The users are allowed to reroute, concurrently, from overloaded links to underloaded links. The different rerouting decisions are concurrent, randomized and independent. The rerouting process terminates when the system reaches a Nash equilibrium, in which no user can improve its state.We study the convergence rate of several migration policies. The first is a very natural policy, which balances the expected load on the links, for the case that all users are identical and apply it, we show that the rerouting terminates in expected O(log log n + log m) stages. Later, we consider the Nash rerouting policies class, in which every rerouting stage is a Nash equilibrium and the users are greedy with respect to the next load they observe. We show a similar termination bounds for this class. We study the structural properties of the Nash rerouting policies, and derive both existence result and an efficient algorithm for the case that the number of links is small. We also show that if the users have different weights then there exists a set of weights such that every Nash rerouting terminates in Ω(√n) stages with high probability.

REFERENCES

• 1: S. Alpern and D. Reyniers, "Spatial Dispersion as a Dynamic Coordination Problem", Theory & Decision, 53:1, pp. 29--59, 2002.
• 2: D. Angluin and L. G. Valiant. Fast probabilistic algorithms for hamiltonian circuits and matchings. Journal of Computer and System Sciences, 18:155--193, 1979.
• 3: B. Awerbuh, Y. Azar, and Y. Richter, "Analysis of worse case Nash equilibria for restricted assignment", WOWA 2003.
• 4: L. E. J. Brouwer. Uber abbildung von mannig-faltigkeiten. Mathematische Annalen, 71:97--115, 1912.
• 5: Artur Czumaj , Piotr Krysta , Berthold Vöcking, Selfish traffic allocation for server farms, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509952]
• 6: Artur Czumaj , Berthold Vöcking, Tight bounds for worst-case equilibria, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.413-420, January 06-08, 2002, San Francisco, California
• 7: Devdatt Dubhashi , Desh Ranjan, Balls and bins: a study in negative dependence, Random Structures & Algorithms, v.13 n.2, p.99-124, Sept. 1998 [doi>10.1002/(SICI)1098-2418(199809)13:2<99::AID-RSA1>3.0.CO;2-M]
• 8: E. Even-Dar, A. Kesselman and Y. Mansour, "Convergence Time To Nash Equilibria," In Proceedings of the 30th ICALP, pp. 502--513, 2003.
• 9: Paul W. Goldberg, Bounds for the convergence rate of randomized local search in a multiplayer load-balancing game, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada [doi>10.1145/1011767.1011787]
• 10: Trond Grenager , Rob Powers , Yoav Shoham, Dispersion games: general definitions and some specific learning results, Eighteenth national conference on Artificial intelligence, p.398-403, July 28-August 01, 2002, Edmonton, Alberta, Canada
• 11: Dimitris Fotakis , Spyros C. Kontogiannis , Elias Koutsoupias , Marios Mavronicolas , Paul G. Spirakis, The Structure and Complexity of Nash Equilibria for a Selfish Routing Game, Proceedings of the 29th International Colloquium on Automata, Languages and Programming, p.123-134, July 08-13, 2002
• 12: E. Koutsoupias, C. H. Papadimitriou, "Worst-case equilibria," in Proceedings of 16th STACS, pp. 404--413, 1999.
• 13: L. Libman and A. Orda, "Atomic Resource Sharing in Noncooperative Networks ", Telecommunication Systems, 17:4, pp 385--409, 2001.
• 14: Peter Marbach, Priority service and max-min fairness, IEEE/ACM Transactions on Networking (TON), v.11 n.5, p.733-746, October 2003 [doi>10.1109/TNET.2003.818196]
• 15: M. Mitzenmacher, A. Richa and R. Sitaraman, "The power of two random choices: A survey of the techniques and results". In Handbook of Randomzied Computing, Rajasekaran et al., Kluuwer Academic Press, 2000.
• 16: V. Mirrokni and A. Vetta, "Convergence issues in competitive games", In Proceedings of the 7th International Workshop on Approximation Algorithms for Combinatorial Optimization, 2004.
• 17: J. F. Nash, "Non-cooperative games," Annals of Mathematics, Vol. 54, pp. 286--295, 1951.
• 18: Ariel Orda , Raphael Rom , Nahum Shimkin, Competitive routing in multiuser communication networks, IEEE/ACM Transactions on Networking (TON), v.1 n.5, p.510-521, Oct. 1993 [doi>10.1109/90.251910]
• 19: Tim Roughgarden , Éva Tardos, How bad is selfish routing?, Journal of the ACM (JACM), v.49 n.2, p.236-259, March 2002 [doi>10.1145/506147.506153]