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:Article
Entered by:chita
TitleAtomic Congestion Games among Coalition
Bibtex cite IDRACTI-RU1-2006-87
Journal In ACM Transactions on Algorithms (TALG)
Year published 2006
Pages 1-12
Note waiting for publication
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 ID89