Approximate Pure Nash Equilibria in Weighted Congestion Games: Existence, Efficient Computation, and Structure

Details Approximate Pure Nash Equilibria in Weighted Congestion Games: Existence, Efficient Computation, and Structure Approximate Pure Nash Equilibria in Weighted Congestion Games: Existence, Efficient Computation, and Structure

2011-07-12

arxiv.org/abs/1107.2248v2

Computer Science

Computer Science and Game Theory

31 pages

Scientific paper

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 potential function arguments. Unfortunately, this proof of existence is inefficient and computing equilibria is such games is a {\sf PLS}-hard problem. The situation gets worse when superlinear latency functions come into play; in this case, the Nash dynamics of the game may contain cycles and equilibria may not even exist. Given these obstacles, we consider approximate equilibria as alternative solution concepts. Do such equilibria exist? 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 $\Psi$-games. This allows us to show that these games have $d!$-approximate equilibria, where $d$ is the maximum degree of the latency functions. Our main technical contribution is an efficient algorithm for computing O(1)-approximate equilibria when $d$ is a constant. For games with linear latency functions, the approximation guarantee is $\frac{3+\sqrt{5}}{2}+O(\gamma)$ for arbitrarily small $\gamma>0$; for latency functions with maximum degree $d\geq 2$, it is $d^{2d+o(d)}$. The running time is polynomial in the number of bits in the representation of the game and $1/\gamma$. As a byproduct of our techniques, we also show the following structural statement for weighted congestion games with polynomial latency functions of maximum degree $d\geq 2$: polynomially-long sequences of best-response moves from any initial state to a $d^{O(d^2)}$-approximate equilibrium exist and can be efficiently identified in such games as long as $d$ is constant.

Affiliated with

Also associated with

No associations

Rating

Approximate Pure Nash Equilibria in Weighted Congestion Games: Existence, Efficient Computation, and Structure does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Approximate Pure Nash Equilibria in Weighted Congestion Games: Existence, Efficient Computation, and Structure, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Approximate Pure Nash Equilibria in Weighted Congestion Games: Existence, Efficient Computation, and Structure will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-565345