One of the main results shown through Roughgarden's notions of smooth games and Robust Price of Anarchy is that, for any sum-bounded utilitarian social function, the worst-case Price of Anarchy of Coarse Correlated Equilibria coincides with that of Pure Nash Equilibria in the class of weighted congestion games with non-negative and non-decreasing latency functions and that such a value can always be derived through the, so called, smoothness argument. We significantly extend this result by proving that, for a variety of (even non-sum-bounded) utilitarian and egalitarian social functions, and for a broad generalization of the class of weighted congestion games with non-negative (and possibly decreasing) latency functions, the worst-case Price of Anarchy of ϵ-approximate Coarse Correlated Equilibria still coincides with that of ϵ-approximate Pure Nash Equilibria, for any ϵ≥0. As a byproduct of our proof, it also follows that such a value can always be determined by making use of the primal-dual method we introduced in a previous work.
On the robustness of the approximate price of anarchy in generalized congestion games
Bilò, Vittorio
2022-01-01
Abstract
One of the main results shown through Roughgarden's notions of smooth games and Robust Price of Anarchy is that, for any sum-bounded utilitarian social function, the worst-case Price of Anarchy of Coarse Correlated Equilibria coincides with that of Pure Nash Equilibria in the class of weighted congestion games with non-negative and non-decreasing latency functions and that such a value can always be derived through the, so called, smoothness argument. We significantly extend this result by proving that, for a variety of (even non-sum-bounded) utilitarian and egalitarian social functions, and for a broad generalization of the class of weighted congestion games with non-negative (and possibly decreasing) latency functions, the worst-case Price of Anarchy of ϵ-approximate Coarse Correlated Equilibria still coincides with that of ϵ-approximate Pure Nash Equilibria, for any ϵ≥0. As a byproduct of our proof, it also follows that such a value can always be determined by making use of the primal-dual method we introduced in a previous work.File | Dimensione | Formato | |
---|---|---|---|
1-s2.0-S0304397522000172-main.pdf
solo utenti autorizzati
Tipologia:
Versione editoriale
Licenza:
NON PUBBLICO - Accesso privato/ristretto
Dimensione
533.43 kB
Formato
Adobe PDF
|
533.43 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.