Anzeige
Erschienen in:
2013 | OriginalPaper | Buchkapitel
Price of Stability in Polynomial Congestion Games
verfasst von : George Christodoulou, Martin Gairing
Erschienen in: Automata, Languages, and Programming
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
The Price of Anarchy in congestion games has attracted a lot of research over the last decade. This resulted in a thorough understanding of this concept. In contrast the Price of Stability, which is an equally interesting concept, is much less understood.
In this paper, we consider congestion games with polynomial cost functions with nonnegative coefficients and maximum degree
d
. We give matching bounds for the Price of Stability in such games, i.e., our technique provides the exact value for any degree
d
.
For linear congestion games, tight bounds were previously known. Those bounds hold even for the more restricted case of dominant equilibria, which may not exist. We give a separation result showing that already for congestion games with quadratic cost functions this is not possible; that is, the Price of Anarchy for the subclass of games that admit a dominant strategy equilibrium is strictly smaller than the Price of Stability for the general class.