Concurrent imitation dynamics in congestion games

ABSTRACT

Imitating successful behavior is a natural and frequently applied approach when facing scenarios for which we have little or no experience upon which we can base our decision. In this paper, we consider such behavior in atomic congestion games. We propose to study concurrent imitation dynamics that emerge when each player samples another player and possibly imitates this agents' strategy if the anticipated latency gain is sufficiently large. Our main focus is on convergence properties. Using a potential function argument, we show that these dynamics converge in a monotonic fashion to stable states. In such a state none of the players can improve their latency by imitating others.

As our main result, we show rapid convergence to approximate equilibria. At an approximate equilibrium only a small fraction of agents sustains a latency significantly above or below average. In particular, imitation dynamics behave like fully polynomial time approximation schemes (FPTAS). Fixing all other parameters, the convergence time depends only in a logarithmic fashion on the number of agents.

Since imitation processes are not innovative they cannot discover unused strategies. Furthermore, strategies may become extinct with non-zero probability. For the case of singleton games, we show that the probability of this event occurring is negligible. Additionally, we prove that the social cost of a stable state reached by our dynamics is not much worse than an optimal state in singleton congestion games with linear latency functions.

While we concentrate on the case of symmetric network congestion games, most of our results do not explicitly use the network structure. They continue to hold accordingly for general symmetric and asymmetric congestion games when each player samples within his commodity.

REFERENCES

• 1: Heiner Ackermann , Simon Fischer , Martin Hoefer , Marcel Schöngens, Distributed algorithms for QoS load balancing, Proceedings of the twenty-first annual symposium on Parallelism in algorithms and architectures, August 11-13, 2009, Calgary, AB, Canada [doi>10.1145/1583991.1584046]
• 2: Heiner Ackermann , Heiko Röglin , Berthold Vöcking, On the impact of combinatorial structure on congestion games, Journal of the ACM (JACM), v.55 n.6, p.1-22, December 2008 [doi>10.1145/1455248.1455249]
• 3: Baruch Awerbuch , Yossi Azar , Amir Epstein, Large the price of routing unsplittable flow, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060599]
• 4: Baruch Awerbuch , Yossi Azar , Amir Epstein , Vahab Seyed Mirrokni , Alexander Skopalik, Fast convergence to nearly optimal solutions in potential games, Proceedings of the 9th ACM conference on Electronic commerce, July 08-12, 2008, Chicago, Il, USA [doi>10.1145/1386790.1386832]
• 5: Petra Berenbrink , Tom Friedetzky , Leslie Ann Goldberg , Paul W. Goldberg , Zengjian Hu , Russell Martin, Distributed Selfish Load Balancing, SIAM Journal on Computing, v.37 n.4, p.1163-1181, September 2007 [doi>10.1137/060660345]
• 6: P. Berenbrink, T. Friedetzky, I. Hajirasouliha, and Z. Hu. Convergence to equilibria in distributed, selfish reallocation processes with weighted tasks. In Proc. 15th European Symposium on Algorithms (ESA), pages 41--52, 2007.
• 7: Avrim Blum , Eyal Even-Dar , Katrina Ligett, Routing without regret: on convergence to nash equilibria of regret-minimizing algorithms in routing games, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA [doi>10.1145/1146381.1146392]
• 8: Steve Chien , Alistair Sinclair, Convergence to approximate Nash equilibria in congestion games, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.169-178, January 07-09, 2007, New Orleans, Louisiana
• 9: George Christodoulou , Elias Koutsoupias, The price of anarchy of finite congestion games, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060600]
• 10: Eyal Even-Dar , Alex Kesselman , Yishay Mansour, Convergence time to Nash equilibrium in load balancing, ACM Transactions on Algorithms (TALG), v.3 n.3, p.32-es, August 2007 [doi>10.1145/1273340.1273348]
• 11: Eyal Even-Dar , Yishay Mansour, Fast convergence of selfish rerouting, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 12: Alex Fabrikant , Christos Papadimitriou , Kunal Talwar, The complexity of pure Nash equilibria, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007445]
• 13: Angelo Fanelli , Michele Flammini , Luca Moscardelli, The Speed of Convergence in Congestion Games under Best-Response Dynamics, Proceedings of the 35th international colloquium on Automata, Languages and Programming, Part I, July 07-11, 2008, Reykjavik, Iceland [doi>10.1007/978-3-540-70575-8_65]
• 14: S. Fischer, L. Olbrich, and B. Vöcking. Approximating Wardrop equilibria with finitely many agents. Distributed Computing, 21(2):129--139, 2008.
• 15: Simon Fischer , Harald Räcke , Berthold Vöcking, Fast convergence to Wardrop equilibria by adaptive sampling methods, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132608]
• 16: Simon Fischer , Berthold Vöcking, Adaptive routing with stale information, Theoretical Computer Science, v.410 n.36, p.3357-3371, August, 2009 [doi>10.1016/j.tcs.2008.01.055]
• 17: Dimitris Fotakis , Alexis C. Kaporis , Paul G. Spirakis, Atomic Congestion Games: Fast, Myopic and Concurrent, Proceedings of the 1st International Symposium on Algorithmic Game Theory, April 30-May 02, 2008, Paderborn, Germany [doi>10.1007/978-3-540-79309-0_12]
• 18: 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]
• 19: Torben Hagerup , C. Rüb, A guided tour of Chernoff bounds, Information Processing Letters, v.33 n.6, p.305-308, February 1990 [doi>10.1016/0020-0190(90)90214-I]
• 20: J. Hofbauer and K. Sigmund. Evolutionary Games and Population Dynamics. Cambridge University Press, 1998.
• 21: S. Ieong, R. McGrew, E. Nudelman, Y. Shoham, and Q. Sun. Fast and compact: A simple class of congestion games. In Proc. 20th Conference on Artificial Intelligence (AAAI), pages 489--494, 2005.
• 22: E. Koutsoupias and C. Papadimitriou. Worst-case equilibria. In Proc. 16th Symposium on Theoretical Aspects of Computer Science (STACS), pages 404--413. Springer-Verlag, 1999.
• 23: Noam Nisan , Tim Roughgarden , Eva Tardos , Vijay V. Vazirani, Algorithmic Game Theory, Cambridge University Press, New York, NY, 2007
• 24: R. Rosenthal. A class of games possessing pure-strategy Nash equilibria. International Journal of Game Theory, 2:65--67, 1973.
• 25: 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]
• 26: Alexander Skopalik , Berthold Vöcking, Inapproximability of pure nash equilibria, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada [doi>10.1145/1374376.1374428]
• 27: J. Weibull. Evolutionary Game Theory. MIT press, 1995.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.m Miscellaneous

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.m Miscellaneous

General Terms:
Algorithms, Design, Performance, Theory

Keywords:
adaptive routing, dynamics, game theory, imitation