Anzeige
Erschienen in:
2011 | OriginalPaper | Buchkapitel
The Complexity of Approximate Nash Equilibrium in Congestion Games with Negative Delays
verfasst von : Frédéric Magniez, Michel de Rougemont, Miklos Santha, Xavier Zeitoun
Erschienen in: Internet and Network Economics
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We extend the study of the complexity of computing an
ε
-approximate Nash equilibrium in symmetric congestion games from the case of positive delay functions to delays of arbitrary sign. Our results show that with this extension the complexity has a richer structure, and it depends on the exact nature of the signs allowed. We first prove that in symmetric games with increasing delay functions and with
α
-bounded jump the
ε
-Nash dynamic converges in polynomial time when all delays are negative, similarly to the case of positive delays. We are able to extend this result to monotone delay functions. We then establish a hardness result for symmetric games with increasing delay functions and with
α
-bounded jump when the delays can be both positive and negative: in that case computing an
ε
-approximate Nash equilibrium becomes
PLS
-complete, even if each delay function is of constant sign or of constant absolute value.