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

Article

Atomic Congestion Games: Fast, Myopic and Concurrent

Authors:

Dimitris Fotakis,

Alexis C. Kaporis,

Paul G. SpirakisAuthors Info & Claims

SAGT '08: Proceedings of the 1st International Symposium on Algorithmic Game Theory

Pages 121 - 132

https://doi.org/10.1007/978-3-540-79309-0_12

Published: 30 April 2008 Publication History

Abstract

We study here the effect of concurrent greedy moves of players in atomic congestion games where <em>n</em>selfish agents (players) wish to select a resource each (out of <em>m</em>resources) so that her selfish delay there is not much. The problem of "maintaining" global progress while allowing concurrent play is exactly what is examined and answered here. We examine two orthogonal settings : (i) A game where the players decide their moves without global information, each acting "freely" by sampling resources randomly and locally deciding to migrate (if the new resource is better) via a random experiment. Here, the resources can have quite arbitrary latency that is load dependent. (ii) An "organised" setting where the players are pre-partitioned into selfish groups (coalitions) and where each coalition does an improving coalitional move. Our work considers concurrent selfish play for arbitrary latencies for the first time. Also, this is the first time where fast coalitional convergence to an approximate equilibrium is shown.

References

[1]

Ackermann, H., Roeglin, H., Voecking, B.: On the impact of combinatorial structure on congestion games. In: FOCS (2006).

[2]

Arndt, H.: Load balancing: dimension exchange on product graphs. In: 18th International Symposium on Parallel and Distributed Processing (2004).

[3]

Awerbuch, B., Azar, Y., Epstein, A.: The Price of Routing Unsplittable Flow. In: STOC (2005).

[4]

Berenbrink, P., Friedetzky, T., Goldberg, L.A., Goldberg, P., Hu, Z., Martin, R.: Distributed selfish load balancing. In: SODA (2006).

[5]

Blum, A., Even-Dar, E., Ligett, K.: Routing without regret: on convergence to nash equilibria of regret-minimizing algorithms in routing games. In: PODC (2006).

[6]

Chien, S., Sinclair, A.: Convergece to Approximate Nash Equilibria in Congestion Games. In: SODA (2007).

[7]

Christodoulou, G., Koutsoupias, E.: The Price of Anarchy of Finite Congestion Games. In: STOC (2005).

[8]

Christodoulou, G., Mirrokni, V.S., Sidiropoulos, A.: Convergence and approximation in potential games. In: Durand, B., Thomas, W. (eds.) STACS 2006. LNCS, vol. 3884, pp. 349- 360. Springer, Heidelberg (2006).

[9]

Cybenko, G.: Load balancing for distributed memory multiprocessors. J. Parallel Distrib. Comput. 7, 279-301 (1989).

[10]

Even-Dar, E., Mansour, Y.: Fast convergence of selfish rerouting. In: SODA (2005).

[11]

Even-Dar, E., Kesselman, A.,Mansour, Y.: Convergence Time to Nash Equilibria. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol. 2719, pp. 502-513. Springer, Heidelberg (2003).

[12]

Fabrikant, A., Papadimitriou, C., Talwar, K.: The Complexity of Pure Nash Equilibria. In: STOC (2004).

[13]

Fischer, S., Räcke, H., Vöcking, B.: Fast convergence to wardrop equilibria by adaptive sampling methods. In: STOC (2006).

[14]

Fotakis, D., Kontogiannis, S., Spirakis, P.: Selfish Unsplittable Flows. In: TCS, vol. 348, pp. 226-239 (2005).

[15]

Fotakis, D., Kontogiannis, S., Spirakis, P.: Atomic Congestion Games among Coalitions. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006. LNCS, vol. 4051, pp. 572-583. Springer, Heidelberg (2006).

[16]

Ghosh, B., Muthukrishnan, S.: Dynamic load balancing in parallel and distributed networks by random matchings. In: SPAA (1994).

[17]

Goemans, M.X., Mirrokni, V.S., Vetta, A.: Sink equilibria and convergence. In: FOCS 2005 (2005).

[18]

Goldberg, P.W.: Bounds for the convergence rate of randomized local search in a multiplayer load-balancing game. In: PODC (2004).

[19]

Hayrapetyan, A., Tardos, É., Wexler, T.: The Effect of Collusion in Congestion Games. In: STOC (2006).

[20]

Hosseini, S.H., Litow, B., Malkawi, M.I., McPherson, J., Vairavan, K.: Analysis of a graph coloring based distributed load balancing algorithm. J. Par. Distr. Comp. 10, 160-166 (1990).

[21]

Ieong, S., McGrew, R., Nudelman, E., Shoham, Y., Sun, Q.: Fast and compact: A simple class of congestion games. In: AAAI (2005).

[22]

Libman, L., Orda, A.: Atomic resource sharing in noncooperative networks. Telecommunication Systems 17(4), 385-409 (2001).

[23]

Mirrokni, V., Vetta, A.: Convergence Issues in Competitive Games. In: Jansen, K., Khanna, S., Rolim, J.D.P., Ron, D. (eds.) RANDOM 2004 and APPROX 2004. LNCS, vol. 3122, pp. 183-194. Springer, Heidelberg (2004).

[24]

Monderer, D., Shapley, L.: Potential Games. Games & Econ. Behavior 14, 124-143 (1996).

[25]

Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, Cambridge (1995).

[26]

Orda, A., Rom, R., Shimkin, N.: Competitive routing in multiuser communication networks. IEEE/ACMTrans. on Net. 1(5), 510-521 (1993).

[27]

Rosenthal, R.W.: A Class of Games Possessing Pure-Strategy Nash Equilibria. International Journal of Game Theory 2, 65-67 (1973).

[28]

Sandholm, W.H.: Population Games and Evolutionary Dynamics. MIT Press (to be published), http://www.ssc.wisc.edu/~whs/book/index.html

[29]

Sandholm, W.H.: Potential Games with Continuous Player Sets. Journal of Economic Theory 97, 81-108 (2001).

[30]

Extended version. http://students.ceid.upatras.gr/kaporis/papers/ fks-sagt-08.pdf

[31]

Weibull, J.W.: Evolutionary Game Theory. MIT Press, Cambridge (1995).

Cited By

Monnot BBenita FPiliouras G(2022)Routing Games in the Wild: Efficiency, Equilibration, Regret, and a Price of Anarchy Bound via Long DivisionACM Transactions on Economics and Computation10.1145/351274710:1(1-26)Online publication date: 8-Apr-2022
https://dl.acm.org/doi/10.1145/3512747
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
Monnot BBenita FPiliouras G(2017)Routing Games in the Wild: Efficiency, Equilibration and RegretWeb and Internet Economics10.1007/978-3-319-71924-5_24(340-353)Online publication date: 17-Dec-2017
https://dl.acm.org/doi/10.1007/978-3-319-71924-5_24
Show More Cited By

Atomic Congestion Games: Fast, Myopic and Concurrent

Recommendations

Atomic Congestion Games: Fast, Myopic and Concurrent
Special Section: Algorithmic Game Theory; Guest Editors: Burkhard Monien and Ulf-Peter Schroeder

We study here the effect of concurrent greedy moves of players in atomic congestion games where n selfish agents (players) wish to select a resource each (out of m resources) so that her selfish delay there is not much. The problem of “maintaining” ...
Approximation and Convergence of Large Atomic Congestion Games
We consider the question of whether and in what sense, Wardrop equilibria provide a good approximation for Nash equilibria in atomic unsplittable congestion games with a large number of small players. We examine two different definitions of small players. ...
Altruism in Atomic Congestion Games

This article studies the effects of altruism, a phenomenon widely observed in practice, in the model of atomic congestion games. Altruistic behavior is modeled by a linear trade-off between selfish and social objectives. Our model can be embedded in the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

SAGT '08: Proceedings of the 1st International Symposium on Algorithmic Game Theory

April 2008

361 pages

ISBN:9783540793083

Editors:
Burkhard Monien
Institut für Informatik, Universität Paderborn, Paderborn, Germany 33102
,
Ulf-Peter Schroeder
Institut für Informatik, Universität Paderborn, Paderborn, Germany 33102

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 30 April 2008

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 09 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Monnot BBenita FPiliouras G(2022)Routing Games in the Wild: Efficiency, Equilibration, Regret, and a Price of Anarchy Bound via Long DivisionACM Transactions on Economics and Computation10.1145/351274710:1(1-26)Online publication date: 8-Apr-2022
https://dl.acm.org/doi/10.1145/3512747
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
Monnot BBenita FPiliouras G(2017)Routing Games in the Wild: Efficiency, Equilibration and RegretWeb and Internet Economics10.1007/978-3-319-71924-5_24(340-353)Online publication date: 17-Dec-2017
https://dl.acm.org/doi/10.1007/978-3-319-71924-5_24
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
Ackermann HFischer SHoefer MSchöngens MMeyer auf der Heide FBender M(2009)Distributed algorithms for QoS load balancingProceedings of the twenty-first annual symposium on Parallelism in algorithms and architectures10.1145/1583991.1584046(197-203)Online publication date: 11-Aug-2009
https://dl.acm.org/doi/10.1145/1583991.1584046
Ackermann HBerenbrink PFischer SHoefer MTirthapura SAlvisi L(2009)Concurrent imitation dynamics in congestion gamesProceedings of the 28th ACM symposium on Principles of distributed computing10.1145/1582716.1582732(63-72)Online publication date: 10-Aug-2009
https://dl.acm.org/doi/10.1145/1582716.1582732
Harks TKlimm MMöhring R(2009)Characterizing the Existence of Potential Functions in Weighted Congestion GamesProceedings of the 2nd International Symposium on Algorithmic Game Theory10.1007/978-3-642-04645-2_10(97-108)Online publication date: 13-Oct-2009
https://dl.acm.org/doi/10.1007/978-3-642-04645-2_10
Kalles DKaporis ASpirakis P(2008)Myopic distributed protocols for singleton and independent-resource congestion gamesProceedings of the 7th international conference on Experimental algorithms10.5555/1788888.1788902(181-193)Online publication date: 30-May-2008
https://dl.acm.org/doi/10.5555/1788888.1788902

View Options

View options

Media

Figures

Other

Tables

View Table of Contents