Abstract
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” 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.
The 2nd and 3rd author were partially supported by the IST Program of the European Union under contract number IST-015964 (AEOLUS). This work was partially supported by the Future and Emerging Technologies Unit of EC (IST priority – 6th FP), under contract no. FP6-021235-2 (project ARRIVAL).
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Ackermann, H., Roeglin, H., Voecking, B.: On the impact of combinatorial structure on congestion games. In: FOCS (2006)
Arndt, H.: Load balancing: dimension exchange on product graphs. In: 18th International Symposium on Parallel and Distributed Processing (2004)
Awerbuch, B., Azar, Y., Epstein, A.: The Price of Routing Unsplittable Flow. In: STOC (2005)
Berenbrink, P., Friedetzky, T., Goldberg, L.A., Goldberg, P., Hu, Z., Martin, R.: Distributed selfish load balancing. In: SODA (2006)
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)
Chien, S., Sinclair, A.: Convergece to Approximate Nash Equilibria in Congestion Games. In: SODA (2007)
Christodoulou, G., Koutsoupias, E.: The Price of Anarchy of Finite Congestion Games. In: STOC (2005)
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)
Cybenko, G.: Load balancing for distributed memory multiprocessors. J. Parallel Distrib. Comput. 7, 279–301 (1989)
Even-Dar, E., Mansour, Y.: Fast convergence of selfish rerouting. In: SODA (2005)
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)
Fabrikant, A., Papadimitriou, C., Talwar, K.: The Complexity of Pure Nash Equilibria. In: STOC (2004)
Fischer, S., Räcke, H., Vöcking, B.: Fast convergence to wardrop equilibria by adaptive sampling methods. In: STOC (2006)
Fotakis, D., Kontogiannis, S., Spirakis, P.: Selfish Unsplittable Flows. In: TCS, vol. 348, pp. 226–239 (2005)
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)
Ghosh, B., Muthukrishnan, S.: Dynamic load balancing in parallel and distributed networks by random matchings. In: SPAA (1994)
Goemans, M.X., Mirrokni, V.S., Vetta, A.: Sink equilibria and convergence. In: FOCS 2005 (2005)
Goldberg, P.W.: Bounds for the convergence rate of randomized local search in a multiplayer load-balancing game. In: PODC (2004)
Hayrapetyan, A., Tardos, É., Wexler, T.: The Effect of Collusion in Congestion Games. In: STOC (2006)
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)
Ieong, S., McGrew, R., Nudelman, E., Shoham, Y., Sun, Q.: Fast and compact: A simple class of congestion games. In: AAAI (2005)
Libman, L., Orda, A.: Atomic resource sharing in noncooperative networks. Telecommunication Systems 17(4), 385–409 (2001)
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)
Monderer, D., Shapley, L.: Potential Games. Games& Econ. Behavior 14, 124–143 (1996)
Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, Cambridge (1995)
Orda, A., Rom, R., Shimkin, N.: Competitive routing in multiuser communication networks. IEEE/ACM Trans. on Net. 1(5), 510–521 (1993)
Rosenthal, R.W.: A Class of Games Possessing Pure-Strategy Nash Equilibria. International Journal of Game Theory 2, 65–67 (1973)
Sandholm, W.H.: Population Games and Evolutionary Dynamics. MIT Press (to be published), http://www.ssc.wisc.edu/~whs/book/index.html
Sandholm, W.H.: Potential Games with Continuous Player Sets. Journal of Economic Theory 97, 81–108 (2001)
Extended version. http://students.ceid.upatras.gr/~kaporis/papers/fks-sagt-08.pdf
Weibull, J.W.: Evolutionary Game Theory. MIT Press, Cambridge (1995)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Fotakis, D., Kaporis, A.C., Spirakis, P.G. (2008). Atomic Congestion Games: Fast, Myopic and Concurrent. In: Monien, B., Schroeder, UP. (eds) Algorithmic Game Theory. SAGT 2008. Lecture Notes in Computer Science, vol 4997. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-79309-0_12
Download citation
DOI: https://doi.org/10.1007/978-3-540-79309-0_12
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-79308-3
Online ISBN: 978-3-540-79309-0
eBook Packages: Computer ScienceComputer Science (R0)