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:Inproceedings
Entered by:
TitleAtomic Congestion Games: Fast, Myopic and Concurrent
Bibtex cite IDRACTI-RU1-2010-11
Booktitle Theory of Computing Systems
Year published 2010
Month July
Volume 47
Number 1
Pages 38-59
Publisher Springer New York
Keywords Distributed congestion games,Atomic model,Approximate Nash Equilibria
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.
Fotakis, Dimitris
Kaporis, Alexis
Spirakis, Paul
fulltext.pdf (main file)
Publication ID737