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:chita
TitleAtomic Congestion Games among Coalitions
Bibtex cite IDRACTI-RU1-2006-36
Booktitle 33rd International Colloquium on Automata, Languages and Programming TRACK A (ICALP 2006)
Year published 2006
Month July
Pages 572-583
Location Venice, Italy
Note LNCS 4051
We consider algorithmic questions concerning the existence, tractability and quality of atomic congestion games, among users that are considered to participate in (static) selfish coalitions. We carefully define a coalitional congestion model among atomic players. Our findings in this model are quite interesting, in the sense that we demonstrate many similarities with the non–cooperative case. For example, there exist potentials proving the existence of Pure Nash Equilibria (PNE) in the (even unrelated) parallel links setting; the Finite Improvement Property collapses as soon as we depart from linear delays, but there is an exact potential (and thus PNE) for the case of linear delays, in the network setting; the Price of Anarchy on identical parallel links demonstrates a quite surprising threshold behavior: it persists on being asymptotically equal to that in the case of the non–cooperative KP–model, unless we enforce a sublogarithmic number of coalitions. We also show crucial differences, mainly concerning the hardness of algorithmic problems that are solved efficiently in the non–cooperative case. Although we demonstrate convergence to robust PNE, we also prove the hardness of computing them. On the other hand, we can easily construct a generalized fully mixed Nash Equilibrium. Finally, we propose a new improvement policy that converges to PNE that are robust against (even dynamically forming) coalitions of small size, in pseudo–polynomial time. Keywords. Game Theory, Atomic Congestion Games, Coalitions, Convergence to Equilibria, Price of Anarchy.
Fotakis, Dimitris
Kontogiannis, Spyros
Spirakis, Paul
icalp06-paper171.pdf (main file)
Publication ID90