---
res:
bibo_abstract:
- 'We consider structural and algorithmic questions related to the Nash dynamics
of weighted congestion games. In weighted congestion games with linear latency
functions, the existence of pure Nash equilibria is guaranteed by a potential
function argument. Unfortunately, this proof of existence is inefficient and computing
pure Nash equilibria in such games is a PLS-hard problem even when all players
have unit weights. The situation gets worse when superlinear (e.g., quadratic)
latency functions come into play; in this case, the Nash dynamics of the game
may contain cycles and pure Nash equilibria may not even exist. Given these obstacles,
we consider approximate pure Nash equilibria as alternative solution concepts.
A ρ--approximate pure Nash equilibrium is a state of a (weighted congestion) game
from which no player has any incentive to deviate in order to improve her cost
by a multiplicative factor higher than ρ. Do such equilibria exist for small values
of ρ? And if so, can we compute them efficiently?We provide positive answers to
both questions for weighted congestion games with polynomial latency functions
by exploiting an “approximation” of such games by a new class of potential games
that we call Ψ-games. This allows us to show that these games have d!-approximate
pure Nash equilibria, where d is the maximum degree of the latency functions.
Our main technical contribution is an efficient algorithm for computing O(1)-approximate
pure Nash equilibria when d is a constant. For games with linear latency functions,
the approximation guarantee is 3+√5/2 + Oγ for arbitrarily small γ > 0; for latency
functions with maximum degree d≥ 2, it is d2d+o(d). The running time is polynomial
in the number of bits in the representation of the game and 1/γ. As a byproduct
of our techniques, we also show the following interesting structural statement
for weighted congestion games with polynomial latency functions of maximum degree
d ≥ 2: polynomially-long sequences of best-response moves from any initial state
to a dO(d2)-approximate pure Nash equilibrium exist and can be efficiently identified
in such games as long as d is a constant.To the best of our knowledge, these are
the first positive algorithmic results for approximate pure Nash equilibria in
weighted congestion games. Our techniques significantly extend our recent work
on unweighted congestion games through the use of Ψ-games. The concept of approximating
nonpotential games by potential ones is interesting in itself and might have further
applications.@eng'
bibo_authorlist:
- foaf_Person:
foaf_givenName: Ioannis
foaf_name: Caragiannis, Ioannis
foaf_surname: Caragiannis
- foaf_Person:
foaf_givenName: Angelo
foaf_name: Fanelli, Angelo
foaf_surname: Fanelli
- foaf_Person:
foaf_givenName: Nick
foaf_name: Gravin, Nick
foaf_surname: Gravin
- foaf_Person:
foaf_givenName: Alexander
foaf_name: Skopalik, Alexander
foaf_surname: Skopalik
foaf_workInfoHomepage: http://www.librecat.org/personId=40384
bibo_doi: 10.1145/2614687
bibo_issue: '1'
bibo_volume: 3
dct_date: 2015^xs_gYear
dct_language: eng
dct_publisher: ACM@
dct_title: 'Approximate Pure Nash Equilibria in Weighted Congestion Games: Existence,
Efficient Computation, and Structure@'
...