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:Incollection
Entered by:chita
TitleAtomic Congestion Games among Coalitions
Bibtex cite IDRACTI-RU1-2008-69
Booktitle ACM Trans. Algorithms
Year published 2008
Volume V,
Number N.
Pages 1-27
Publisher ACM Journal Name
We consider algorithmic questions concerning the existence, tractability and quality of Nash equi- libria, in atomic congestion games among users participating in sel sh coalitions. We introduce a coalitional congestion model among atomic players and demonstrate many in- teresting similarities with the non-cooperative case. For example, there exists a potential function proving the existence of Pure Nash Equilibria (PNE) in the unrelated parallel links setting; in the network setting, the Finite Improvement Property collapses as soon as we depart from linear delays, but there is an exact potential (and thus PNE) for linear delays; 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 the number of coalitions is sublogarithmic. We also show crucial di erences, mainly concerning the hardness of algorithmic problems that are solved eciently in the noncooperative case. Although we demonstrate convergence to robust PNE, we also prove the hardness of computing them. On the other hand, we propose a generalized fully mixed Nash Equilibrium, that can be eciently constructed in most cases. Finally, we propose a natural improvement policy and prove its convergence in pseudopolynomial time to PNE which are robust against (even dynamically forming) coalitions of small size.
Fotakis, Dimitris
Kontogiannis, Spyros
Spirakis, Paul
coalitions-talg.pdf (main file)
Publication ID530