More Web Proxy on the site http://driver.im/

research-article

Concurrent imitation dynamics in congestion games

Authors:

Heiner Ackermann,

Petra Berenbrink,

Martin HoeferAuthors Info & Claims

PODC '09: Proceedings of the 28th ACM symposium on Principles of distributed computing

Pages 63 - 72

https://doi.org/10.1145/1582716.1582732

Published: 10 August 2009 Publication History

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]

H. Ackermann, S. Fischer, M. Hoefer, and M. Sch&#246;ngens. Distributed Algorithms for QoS Load Balancing. In Proc. 21st Symposium Parallelism in Algorithms and Architectures (SPAA), 2009.

Digital Library

[2]

H. Ackermann, H. R&#246;glin, and B. V&#246;cking. On the impact of combinatorial structure on congestion games. J ACM, 55(6), 2008.

Digital Library

[3]

B. Awerbuch, Y. Azar, and A. Epstein. The price of routing unsplittable flow. In Proc. 37th Symposium on Theory of Computing (STOC), pages 57--66, 2005.

Digital Library

[4]

B. Awerbuch, Y. Azar, A. Epstein, V. Mirrokni, and A. Skopalik. Fast convergence to nearly optimal solutions in potential games. In Proc. 9th Conference on Electronic Commerce, pages 264--273, 2008.

Digital Library

[5]

P. Berenbrink, T. Friedetzky, L. Goldberg, P. Goldberg, Z. Hu, and R. Martin. Distributed selfish load balancing. SIAM J. Comput., 37(4):1163--1181, 2007.

Digital Library

[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.

Digital Library

[7]

A. Blum, E. Even-Dar, and K. Ligett. Routing without regret: On convergence to Nash equilibria of regret-minimizing algorithms in routing games. In Proc. 25th Symposium on Principles of Distributed Computing (PODC), pages 45--52, 2006.

Digital Library

[8]

S. Chien and A. Sinclair. Convergence to approximate Nash equilibria in congestion games. In Proc. 18th Symposium on Discrete Algorithms (SODA), pages 169--178, 2007.

Digital Library

[9]

G. Christodoulou and E. Koutsoupias. The price of anarchy of finite congestion games. In Proc. 37th Symposium on Theory of Computing (STOC), pages 67--73, 2005.

Digital Library

[10]

E. Even-Dar, A. Kesselman, and Y. Mansour. Convergence time to Nash equilibrium in load balacing. ACM Transact. Algorithms}, 3(3), 2007.

Digital Library

[11]

E. Even-Dar and Y. Mansour. Fast convergence of selfish rerouting. In Proc. 16th Symposium on Discrete Algorithms (SODA), pages 772--781, 2005.

Digital Library

[12]

A. Fabrikant, C. Papadimitriou, and K. Talwar. The complexity of pure Nash equilibria. In Proc. 36th Symposium on Theory of Computing (STOC), pages 604--612, 2004.

Digital Library

[13]

A. Fanelli, M. Flammini, and L. Moscardelli. The speed of convergence in congestion games under best-response dynamics. In Proc. 35th International Colloquium on Automata, Languages and Programming (ICALP), pages 796--807, 2008.

Digital Library

[14]

S. Fischer, L. Olbrich, and B. V&#246;cking. Approximating Wardrop equilibria with finitely many agents. Distributed Computing, 21(2):129--139, 2008.

Digital Library

[15]

S. Fischer, H. R&#228;cke, and B. V&#246;cking. Fast convergence to Wardrop equilibria by adaptive sampling methods. In Proc. 38th Symposium on Theory of Computing (STOC), pages 653--662, 2006.

Digital Library

[16]

S. Fischer and B. V&#246;cking. Adaptive routing with stale information. Theoretical Computer Science, 2008. Invited paper. To appear.

Digital Library

[17]

D. Fotakis, A. Kaporis, and P. Spirakis. Atomic congestion games: Fast, myopic and concurrent. In Proc. 1st Symposium on Algorithmic Game Theory (SAGT), pages 121--132, 2008.

Digital Library

[18]

P. Goldberg. Bounds for the convergence rate of randomized local search in a multiplayer load-balancing game. In Proc. 23rd Symposium on Principles of Distributed Computing (PODC), pages 131--140, 2004.

Digital Library

[19]

T. Hagerup and C. R&#252;b. A guided tour of Chernoff bounds. Inf. Process. Lett., 33:305--308, 1990.

Digital Library

[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.

Digital Library

[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.

Digital Library

[23]

N. Nisan, T. Roughgarden, E. Tardos, and V. Vazirani, editors. Algorithmic Game Theory. Cambridge University Press, 2007.

Digital Library

[24]

R. Rosenthal. A class of games possessing pure-strategy Nash equilibria. International Journal of Game Theory, 2:65--67, 1973.

Digital Library

[25]

T. Roughgarden and &#201;. Tardos. How bad is selfish routing? J ACM, 49(2):236--259, 2002.

Digital Library

[26]

A. Skopalik and B. V&#246;cking. Inapproximability of pure Nash equilibria. In Proc. 40th Symposium on Theory of Computing (STOC), pages 355--364, 2008.

Digital Library

[27]

J. Weibull. Evolutionary Game Theory. MIT press, 1995.

Cited By

Akbari HBerenbrink PSauerwald T(2018)A simple approach for adapting continuous load balancing processes to discrete settingsDistributed Computing10.1007/s00446-016-0266-y29:2(143-161)Online publication date: 26-Dec-2018
https://dl.acm.org/doi/10.1007/s00446-016-0266-y
Palaiopanos GPanageas IPiliouras G(2017)Multiplicative weights update with constant step-size in congestion gamesProceedings of the 31st International Conference on Neural Information Processing Systems10.5555/3295222.3295337(5874-5884)Online publication date: 4-Dec-2017
https://dl.acm.org/doi/10.5555/3295222.3295337
Panageas IPiliouras GConitzer VBergemann DChen Y(2016)Average Case Performance of Replicator Dynamics in Potential Games via Computing Regions of AttractionProceedings of the 2016 ACM Conference on Economics and Computation10.1145/2940716.2940784(703-720)Online publication date: 21-Jul-2016
https://dl.acm.org/doi/10.1145/2940716.2940784
Show More Cited By

Index Terms

Concurrent imitation dynamics in congestion games

Recommendations

Concurrent imitation dynamics in congestion games

Imitating successful behavior is a natural and frequently applied approach when facing complex decision problems. In this paper, we design protocols for distributed latency minimization in atomic congestion games based on imitation. We propose to study ...
Analysis of the dynamics of multi-team Bertrand game with heterogeneous players

In this article, we study the dynamics of a two-team Bertrand game with players having heterogeneous expectations. We study the equilibrium solutions and the conditions of their locally asymptotic stability. Numerical simulations are used to illustrate ...
Payoff-Based Dynamics for Multiplayer Weakly Acyclic Games

We consider repeated multiplayer games in which players repeatedly and simultaneously choose strategies from a finite set of available strategies according to some strategy adjustment process. We focus on the specific class of weakly acyclic games, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PODC '09: Proceedings of the 28th ACM symposium on Principles of distributed computing

August 2009

356 pages

ISBN:9781605583969

DOI:10.1145/1582716

General Chair:
Srikanta Tirthapura
Iowa State University, USA
,
Program Chair:
Lorenzo Alvisi
The University of Texas at Austin, USA

Copyright © 2009 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 10 August 2009

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

PODC '09

Sponsor:

PODC '09: ACM Symposium on Principles of Distributed Computing

August 10 - 12, 2009

AB, Calgary, Canada

Acceptance Rates

PODC '09 Paper Acceptance Rate 27 of 110 submissions, 25%;

Overall Acceptance Rate 740 of 2,477 submissions, 30%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

16
Total Citations
View Citations
257
Total Downloads

Downloads (Last 12 months)6
Downloads (Last 6 weeks)2

Reflects downloads up to 21 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Akbari HBerenbrink PSauerwald T(2018)A simple approach for adapting continuous load balancing processes to discrete settingsDistributed Computing10.1007/s00446-016-0266-y29:2(143-161)Online publication date: 26-Dec-2018
https://dl.acm.org/doi/10.1007/s00446-016-0266-y
Palaiopanos GPanageas IPiliouras G(2017)Multiplicative weights update with constant step-size in congestion gamesProceedings of the 31st International Conference on Neural Information Processing Systems10.5555/3295222.3295337(5874-5884)Online publication date: 4-Dec-2017
https://dl.acm.org/doi/10.5555/3295222.3295337
Panageas IPiliouras GConitzer VBergemann DChen Y(2016)Average Case Performance of Replicator Dynamics in Potential Games via Computing Regions of AttractionProceedings of the 2016 ACM Conference on Economics and Computation10.1145/2940716.2940784(703-720)Online publication date: 21-Jul-2016
https://dl.acm.org/doi/10.1145/2940716.2940784
Chen PLu C(2016)Generalized mirror descents in congestion gamesArtificial Intelligence10.1016/j.artint.2016.09.002241(217-243)Online publication date: Dec-2016
https://doi.org/10.1016/j.artint.2016.09.002
Auletta VFerraioli DPasquale FPenna PPersiano G(2016)Convergence to Equilibrium of Logit Dynamics for Strategic GamesAlgorithmica10.1007/s00453-015-0025-776:1(110-142)Online publication date: 1-Sep-2016
https://dl.acm.org/doi/10.1007/s00453-015-0025-7
Berenbrink PHoefer MSauerwald T(2014)Distributed Selfish Load Balancing on NetworksACM Transactions on Algorithms10.1145/262967111:1(1-29)Online publication date: 11-Aug-2014
https://dl.acm.org/doi/10.1145/2629671
Paul SRamanujam R(2014)Subgames within Large Games and the Heuristic of ImitationStudia Logica10.1007/s11225-014-9549-0102:2(361-388)Online publication date: 27-Feb-2014
https://doi.org/10.1007/s11225-014-9549-0
Iellamo SChen LCoupechoux M(2013)Proportional and double imitation rules for spectrum access in cognitive radio networksComputer Networks10.1016/j.comnet.2013.03.00857:8(1863-1879)Online publication date: Jun-2013
https://doi.org/10.1016/j.comnet.2013.03.008
Iellamo SChen LCoupechoux M(2012)Imitation-based spectrum access policy for CSMA/CA-based cognitive radio networks2012 IEEE Wireless Communications and Networking Conference (WCNC)10.1109/WCNC.2012.6214274(2780-2785)Online publication date: Apr-2012
https://doi.org/10.1109/WCNC.2012.6214274
Harks THoefer MKlimm MSkopalik A(2012)Computing pure Nash and strong equilibria in bottleneck congestion gamesMathematical Programming10.1007/s10107-012-0521-3141:1-2(193-215)Online publication date: 8-Mar-2012
https://doi.org/10.1007/s10107-012-0521-3
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents