research unit 1

This site is powered by Aigaion - A PHP/Web based management system for shared and annotated bibliographies. For more information visit


Type of publication:Techreport
Entered by:
TitleAtomic congestion games: fast, myopic and concurrent
Bibtex cite IDRACTI-RU1-2007-12
Year published 2007
Month July
Institution Computer Engineering and Informatics Department, Univ. Patras. Also RA Computer Technology Institute
Address University of Patras, Building B, Computer Engineering and Informatics Department, 26504
Keywords Conccurent Congestion Games,Nash dynamics
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. Such games usually admit a global potential that decreases by sequential and selfishly improving moves. However, concurrent moves may not always lead to global convergence. On the other hand, concurrent play is desirable because it might essentially improve the system convergence time to some balanced state. 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 prepartitioned into selfish groups (coalitions) and where each coalition does an improving coalitional move. Here the concurrency is among the members of the coalition. In this second setting, the resources have latency functions that are only linearly dependent on the load, since this is the only case so far where a global potential exists. In both cases (i), (ii) we show that the system converges to an ?approximate? equilibrium very fast (in logarithmic rounds where the logarithm is taken on the maximum value of the global potential). This is interesting, since two quite orthogonal settings lead to the same result. 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. All our results refer to atomic games (ie players are finite and distinct).
Spirakis, Paul
Kaporis, Alexis
Fotakis, Dimitris
fks.pdf (main file)
Publication ID13