Efficient computation of approximate pure Nash equilibria in congestion games

Introduction

Among other solution concepts, the notion of the pure Nash equilibrium plays a central role in Game Theory. It characterizes situations with non-cooperative deterministic players in which no player has any incentive to unilaterally deviate from the current situation in order to achieve a higher payoff. Questions related to their existence and efficient computation have been extensively addressed in the context of congestion games. In these games, pure Nash equilibria are guaranteed to exist through potential function arguments: any pure Nash equilibrium corresponds to a local minimum of a potential function. Unfortunately, this proof of existence is inefficient and computing a local minimum for this function is a computationally-hard task. This statement has been made formal in the work of Fabrikant et al. where it is proved that the problem of computing a pure Nash equilibrium is PLS-complete.

Such negative complexity results significantly question the importance of pure Nash equilibria as solution concepts that characterize the behavior of rational players. Approximate pure Nash equilibria, which characterize situations where no player can significantly improve her payoff by unilaterally deviating from her current strategy, could serve as alternative solution conceptsActually, approximate pure Nash equilibria may be more desirable as solution concepts in practical decision making settings since they can accommodate small modeling inaccuracies due to uncertainty (e.g., see the arguments in ). provided that they can be computed efficiently. In this paper, we study the complexity of computation of approximate pure Nash equilibria in congestion games and prove the first positive algorithmic results for important (and quite general) classes of congestion games. Our main result is a polynomial-time algorithm that computes $O(1)$-approximate pure Nash equilibria in congestion games under mild restrictions.

Problem statement and related work. Congestion games were introduced by Rosenthal . In a congestion game, players compete over a set of resources. Each resource incurs a latency to all players that use it; this latency depends on the number of players that use the resource according to a resource-specific, non-negative, and non-decreasing latency function. Among a given set of strategies (over sets of resources), each player aims to select one selfishly, trying to minimize her individual total cost, i.e., the sum of the latencies on the resources in her strategy. Typical examples include network congestion games where the network links correspond to the resources and each player has alternative paths that connect two nodes as strategies. Congestions games in which players have the same set of available strategies are called symmetric.

Rosenthal proved that congestion games admit a potential function with the following remarkable property: the difference in the potential value between two states (i.e., two snapshots of strategies) that differ in the strategy of a single player equals to the difference of the cost experienced by this player in these two states. This immediately implies the existence of a pure Nash equilibrium. Any sequence of improvement moves by the players strictly decreases the value of the potential and a state corresponding to a local minimum of the potential will eventually be reached; this corresponds to a pure Nash equilibrium. Monderer and Shapley proved that any game that admits such a cost-revealing (or exact) potential function is isomorphic to a congestion game.

The existence of a potential function allows us to view the problem of computing a pure Nash equilibrium as a local search problem , i.e., as the problem of computing a local minimum of the potential function. Fabrikant et al. proved that the problem is PLS-complete (informally, as hard as it could be given that there is an associated potential function). This negative result applies to symmetric congestion games as well as to non-symmetric network congestion games. Ackermann et al. studied the impact of combinatorial structure of congestion games to complexity and extended such negative results to games with linear latency functions. One consequence of PLS-completeness results is that almost all the states of the game are such that any sequence of players’ improvement moves that originates from these states must be exponentially long (in terms of the number of players) in order to reach a pure Nash equilibrium. Efficient algorithms are known only for special cases. For example, in symmetric network congestion games, Fabrikant et al. show that the Rosenthal’s potential function can be (globally) minimized efficiently by a flow computation.

The above negative results have led to the study of the complexity of approximate Nash equilibria. A $\rho$-approximate pure Nash equilibrium is a state, from which no player has an incentive to deviate so that she decreases her cost by a factor larger than $\rho$. Skopalik and Vöcking show that, in general, the problem is still PLS-complete for any polynomially computable $\rho$. Efficient algorithms are known only for special cases. For symmetric congestion games, Chien and Sinclair prove that the $(1+\epsilon)$-improvement dynamics converges to a $(1+\epsilon$)-approximate Nash equilibrium after a polynomial number of steps; this result holds under additional mild assumptions on the latency functions (a “bounded jump” property) and the participation of the players in the dynamics. Skopalik and Vöcking prove that this approach cannot be generalized. They present non-symmetric congestion games with latency functions satisfying the bounded-jump property, so that every sequence of approximate improvement moves from a given initial state to an approximate equilibrium is exponentially long. Daskalakis and Papadimitriou present algorithms for the broader class of anonymous games assuming that the number of players’ strategies is constant; for congestion games, this assumption is very restrictive. Efficient algorithms for approximate equilibria have been recently obtained for other classes of games such as constraint satisfaction , network formation , and facility location games .

In light of these negative results, several authors have considered other properties of the dynamics of congestion games. The papers consider the question of whether efficient states (in the sense that the total cost of the players, or social cost, is small compared to the optimum one) can be reached by best-response moves. Recall that such states are not necessary approximate Nash equilibria. Fanelli et al. proved that congestion games with linear latency functions converge to states that approximate the optimal social cost within a constant factor after an almost linear (in the number of players) number of best response moves under mild assumptions on the participation of each player in the dynamics. Negative results in indicate that these assumptions are necessary in order to obtain convergence in subexponential time. However, Awerbuch et al. show that using almost unrestricted sequences of ($1+\epsilon$)-improvement best-response moves in congestion games with polynomial latency functions, the players rapidly converge to efficient states. Similar approaches have been followed in the context of other games as well, such as multicast , cut , and valid-utility games .

A notion that is historically related to congestion games (but rather loosely connected to our work) is that of the price of anarchy, introduced by Koutsoupias and Papadimitriou . The price of anarchy captures the impact of selfishness on efficiency and is defined as the worst-case ratio of the social cost in any pure Nash equilibrium and the social optimum (see and the references therein for tight bounds on congestion games). Christodoulou et al. extended the notion of the price of anarchy to approximate equilibria and provided tight bounds for congestion games with polynomial latency functions.

Our contribution. We present the first polynomial-time algorithm that computes $O(1)$-approximate pure Nash equilibria in non-symmetric congestion games with polynomial latency functions of constant maximum degree. In particular, our algorithm computes $(2+\epsilon)$-approximate pure Nash equilibria in congestion games with linear latency functions, and $d^{O(d)}$ approximate equilibria for polynomial latency functions of maximum degree $d$. The algorithm is surprisingly simple. Essentially, starting from a specific initial state, it computes a sequence of best-response player moves of length that is bounded by a polynomial in the number of players and $1/\epsilon$. To the best of our knowledge, the existence of such short sequences was not known before and is interesting in itself. The sequence consists of phases so that the players that participate in each phase experience costs that are polynomially related. This is crucial in order to obtain convergence in polynomial time. Another interesting part of our algorithm is that, within each phase, it coordinates the best response moves according to two different (but simple) criteria; this is the main tool that guarantees that the effect of a phase to previous ones is negligible and, eventually, an approximate equilibrium is reached. The parameters used by the algorithm and its approximation guarantee have a nice relation to properties of Rosenthal’s potential function. Our bounds are marginally higher than the worst-case ratio of the potential value at an almost exact pure Nash equilibrium over the globally optimum potential value.

We remark that, following the classical definition of polynomial latency functions in the literature, we assume that they have non-negative coefficients. We show that this is a necessary limitation. In particular, by significantly extending the reduction of , we prove that the problem of computing a $\rho$-approximate equilibrium in congestion games with linear latency functions with negative offsets is PLS-complete. This negative statement also applies to games with polynomial latency functions with non-negative coefficients and maximum degree that is polynomial in the number of players.

Roadmap. We begin with definitions and preliminary results and observations in Section 2. The description of the algorithm then appears in Section 3. The analysis of the algorithm is presented in Section 4. We conclude with a discussion that includes the statement of our PLS-completeness result and open problems in Section 5. Due to lack of space, many proofs have been put in appendix.

Definitions and preliminaries

Players act selfishly; each of them aims to select a strategy that minimizes her cost, given the strategies of the other players. Given a state $S=(s_{1},s_{2},...,s_{n})$ and a strategy $s^{\prime}_{u}$ for player $u$, we denote by $(S_{-u},s^{\prime}_{u})$ the state obtained from $S$ when player $u$ deviates to strategy $s^{\prime}_{u}$. For a strategy $S$, an improvement move (or, simply, a move) for player $u$ is the deviation to any strategy $s^{\prime}_{u}$ that (strictly) decreases her cost, i.e., $c_{u}(S_{-u},s^{\prime}_{u})<c_{u}(S)$. For $q\geq 1$, such a move is called a $q$-move if it satisfies $c_{u}(S_{-u},s^{\prime}_{u})<\frac{c_{u}(S)}{q}$. A best-response move is a move that minimizes the cost of the player (of course, given the strategies of the other players). So, from state $S$, a move of player $u$ to strategy $s_{u}$ is a best-response move (and is denoted by ${\mathcal{BR}}_{u}(S)$) when $c_{u}(S_{-u},s^{\prime}_{u})=\min_{s\in\Sigma_{u}}c_{u}(S_{-u},s)$. With some abuse in notation, we use ${\mathcal{BR}}_{u}(\mathbf{0})$ to denote the best-response of player $u$ assuming that no other player participates in the game.

A state $S$ is called a pure Nash equilibrium (or, simply, an equilibrium) when $c_{u}(S)\leq c_{u}(S_{-u},s^{\prime}_{u})$ for every player $u\in N$ and every strategy $s^{\prime}_{u}\in\Sigma_{u}$. In this case, we say that no player has (any incentive to make) a move. Similarly, a state is called a $q$-approximate pure Nash equilibrium (henceforth called, simply, a $q$-approximate equilibrium) when no player has a $q$-move.

For any state $S$ of a congestion game with a set of players $N$, a set of resource $E$, and latency functions $(f_{e})_{e\in E}$, it holds that

In the rest of the paper, the term potential function is used specifically for Rosenthal’s potential function.

We now present a simple observation which will be used extensively in the analysis of our algorithm. Consider a sequence of moves in which only players from a subset $F$ of $N$ participate while players in $N\setminus F$ are frozen to their strategies throughout the whole sequence. We will think of this sequence as a sequence of moves in a subgame played among the players of $F$ on the resources of $E$. In this subgame, each player in $F$ has the same set of strategies as in the original game; players of $N\setminus F$ do not participate in the subgame, although they contribute to the latency of the resources at which they have been frozen. Thus, the modified latency function of resource $e$ is then $f^{F}_{e}(x)=f_{e}(x+t_{e})$, where $t_{e}$ stands for the number of players of $N\setminus F$ on resource $e$. Then, it is not hard to see that the subgame is a congestion game as well. Clearly, if $f_{e}$ is a linear (respectively, polynomial of maximum degree $d$) function with non-negative coefficients, so is $f^{F}_{e}$ and the bound established in Lemma 2.3 (respectively, Lemma 2.4, see below) also holds for the subgame. From the perspective of a player in $F$, nothing changes. At any state $S$, such a player experiences the same cost in both games and therefore has the same incentive to move, regardless whether we view $S$ as a state of the original game or the subgame. However, one should be careful with the definition of the potential for the subgame (denoted by $\Phi_{F}$) and use the modified latency functions $f^{F}_{e}$ instead of $f_{e}$. Throughout the paper, for a subset of players $F\subseteq N$, we use the notation $n^{F}_{e}(S)$ to denote the number of players in $F$ that use resource $e$ at state $S$.

Let $S$ be a state of the congestion game with a set of players $N$ and let $F\subseteq N$. Then, $\Phi(S)\leq\Phi_{F}(S)+\Phi_{N\setminus F}(S)$ and $\Phi(S)\geq\Phi_{F}(S)$.

The approximation guarantee of our algorithm for congestion games of a particular class (e.g., with linear latency functions) is strongly related to the worst-case ratio (among all congestion games in the class) between the potential of an approximate equilibrium (the factor of approximation may be picked to be close to $1$) and the minimum potential value. Below, we present upper bounds on this quantity; these upper bounds are used as parameters by our algorithm. The next lemma deals with the case of linear latency functions.

Consider a congestion game with linear latency functions. Let $q\in[1,2)$ and let $S$ be a $q$-approximate equilibrium. Then, $\Phi(S)\leq\frac{2q}{2-q}\Phi(S^{*})$, where $S^{*}$ is a state of the game with minimum potential.

Our next (rather rough) bound applies to polynomial latency functions of maximum degree $d$. It is obtained by observing that the desired ratio is at most $(d+1)$ times the known upper bound of $d^{O(d)}$ for the price of anarchy of $2$-approximate equilibria .

Consider a congestion game with polynomial latency functions of maximum degree $d$, where $d\geq 2$. Let $q\in$ and let $S$ be a $q$-approximate equilibrium. Then, $\Phi(S)/\Phi(S^{*})\in d^{O(d)}$, where $S^{*}$ is a state of the game with the minimum potential.

The algorithm

In this section we describe our algorithm. It takes as input a congestion game ${\cal G}$ with $n$ players and polynomial latency functions of maximum degree $d$ and produces a state of ${\cal G}$. The algorithm uses a constant parameter $\psi>0$ and two more parameters $q$ and $p$. Denote by $\theta_{d}(q)$ the upper bound on the worst-case ratio (among all possible congestion games with polynomial latency functions of degree $d$) between the potential of any $q$-approximate equilibrium and the minimum potential value that are provided by Lemmas 2.3 and 2.4, i.e., $\theta_{1}(q)=\frac{2q}{2-q}$ and $\theta_{d}(q)=d^{O(d)}$ for $d\geq 2$. We set the parameter $q$ to be slightly larger than $1$ (in particular, $q=1+n^{-\psi}$) and parameter $p$ to be slightly larger than $\theta_{d}(q)$ (in particular, $p=\left(\frac{1}{\theta_{d}(q)}-n^{\psi}\right)^{-1}$).

We remark that step 1 partitions the players into at most $n$ non-empty blocks. Then, the for-loop at lines 1-10 enumerates only phases $i$ such that $B_{i}$ is non-empty, i.e., it considers at most $n$ phases.

We conclude this section with two remarks that will be treated formally in the next section. First, the selection of the boundaries of each block to be polynomially-related is crucial in order to bound the number of steps. Second, but more importantly, we notice that each player in block $B_{i}$ does not move after phase $i$. At the end of this phase, the algorithm guarantees that none of these players has a $p$-move to make. The most challenging part of the analysis will be to show that the players do not have any $p(1+4n^{-\psi})$-move to make after any subsequent phase. In this respect, the definition of the phases, the selection of parameter $p$ and its relation to $\theta_{d}(q)$ play the crucial role.

Analysis of the algorithm

This section is devoted to proving our main result.

For every constant $\psi>0$, the algorithm computes a $\rho_{d}$-approximate equilibrium for every congestion game with polynomial latency functions of constant maximum degree $d$ and $n$ players, where $\rho_{1}=2+O(n^{-\psi})$ and $\rho_{d}\in d^{O(d)}$. Moreover, the number of player moves is at most polynomial in $n$.

The proof of the theorem follows by a series of lemmas. The most crucial one is Lemma 4.3 where we show that the potential $\Phi_{R_{i}}(S^{i-1})$ of the subgame among the players in $R_{i}$ at the beginning of phase $i\geq 2$ is significantly smaller than $b_{i}$. In general, players that move during phase $i$ experience cost that is polynomially related to $b_{i}$ and each of them decreases her cost (and, consequently, the potential) by a quantity that is also polynomially related to $b_{i}$. This argument is used in Lemma 4.4 (together with Lemma 4.3) in order to show that the number of steps of the algorithm is polynomial in $n$. More importantly, Lemma 4.3 is used in the proof of Lemma 4.5 in order to show that players in block $B_{i}$ are not affected significantly after phase $i$ (notice that players in $B_{i}$ do not move after phase $i$). Using this lemma, we conclude in Lemma 4.6 that the players are in a $p(1+4n^{-\psi})$-approximate equilibrium after the execution of the algorithm. The statement of the theorem then follows by taking into account the parameters of the algorithm.

Let us warm up with the following lemma (to be used in the proof of Lemma 4.3) that relates the potential $\Phi_{R_{i}}(S^{i})$ with the latency the players in $R_{i}$ experience when they make their last move within phase $i$.

Let $c(u)$ denote the cost of player $u\in R_{i}$ just after making her last move within phase $i$. Then,

We now present the key lemma of our proof.

For every phase $i\geq 2$, it holds that $\Phi_{R_{i}}(S^{i-1})\leq\frac{b_{i}}{2^{d}n^{\psi}}$.

Proof. Assume the contrary, that $\Phi_{R_{i}}(S^{i-1})>\frac{b_{i}}{2^{d}n^{\psi}}$. We will show that state $S^{i-1}$ would not be a $q$-approximate equilibrium for the players in $R_{i}\cap B_{i}$, which contradicts the definition of phase $i-1$ of the algorithm.

First observe that a player $u$ in $B_{i+1}$ is assigned to the strategy ${\mathcal{BR}}_{u}(\mathbf{0})$ in the beginning of the algorithm and does not move during the first $i-1$ phases. Hence, by the definition of the latency functions, she does not experience a cost more than $n^{d}b_{i+1}$ at state $S^{i-1}$. Hence, the potential $\Phi_{R_{i}\cap B_{i+1}}(S^{i-1})$, which is upper-bounded by the total cost of players in $R_{i}\cap B_{i+1}$, satisfies

We now use the fact $\Phi_{R_{i}}(S^{i-1})\leq\Phi_{R_{i}\cap B_{i}}(S^{i-1})+\Phi_{R_{i}\cap B_{i+1}}(S^{i-1})$ (see Claim 2.2), inequality (1), and the assumption $\Phi_{R_{i}}(S^{i-1})>\frac{b_{i}}{2^{d}n^{\psi}}$ to obtain

Further, we consider the dynamics of the subgame among the players in $R_{i}$ at phase $i$. For each player $u$ in $R_{i}$, we denote by $c(u)$ the cost player $u$ experiences just after she makes her last move in phase $i$. Observe that every player $u$ in $B_{i}\cap R_{i}$ decreases the potential of the subgame among the players of $R_{i}$ by at least $(p-1)c(u)$ when she performs her last $p$-move. Hence,

The last three inequalities follow by Claim 2.2 and inequalities (1) and (2), respectively.

Furthermore, since each player $u$ in $R_{i}\cap B_{i+1}$ plays a best-response during phase $i$, her cost after her last move will be at most the cost she would experience by deviating to strategy ${\mathcal{BR}}_{u}(\mathbf{0})$, which is at most $n^{d}b_{i+1}$. Then, the total cost of the players of $R_{i}\cap B_{i+1}$ is at most $n^{d+1}b_{i+1}$. Now, using Lemma 4.2, the last observation, inequalities (3) and (2), we obtain

Now, let $S^{*}$ be the state in which the players in $R_{i}\cap B_{i}$ play their strategies in $S^{i}$ and the players in $R_{i}\cap B_{i+1}$ (as well as every other player) play their strategies in $S^{i-1}$. Consider the deviation of each player $u$ in $R_{i}\cap B_{i+1}$ from her strategy in $S^{i}$ to her strategy ${\mathcal{BR}}_{u}(\mathbf{0})$ in $S^{*}$. Recall that the cost each player $u$ in $R_{i}\cap B_{i+1}$ experiences when playing strategy ${\mathcal{BR}}_{u}(\mathbf{0})$ is at most $n^{d}b_{i+1}$ which means that the increase her deviation incurs to the potential of the subgame among the players in $R_{i}$ is at most $n^{d}b_{i+1}$. Hence,

Now, using the fact that $\Phi_{R_{i}\cap B_{i}}(S^{*})\leq\Phi_{R_{i}}(S^{*})$, together with inequalities (5), (4), and (2), we have

The last inequality implies that the global minimum of the potential value of the subgame among the players of $R_{i}\cap B_{i}$ (when all other players are frozen to their strategies in $S^{i-1}$) is strictly smaller than $\frac{1}{\theta_{d}(q)}\Phi_{R_{i}\cap B_{i}}(S^{i-1})$. Due to the definition of $\theta_{d}(q)$ and Lemmas 2.3 and 2.4, this contradicts the fact that $S^{i-1}$ is a $q$-approximate equilibrium for the players in $R_{i}\cap B_{i}$. $\sqcap$$\sqcup$

We are ready to bound the number of best-response moves. As a matter of fact, our upper bound is dominated by the number of best-response moves in the very first phase of the algorithm. We remark that a weaker result could be obtained without resorting to Lemma 4.3.

The algorithm terminates after at most $O\left(n^{5\psi+3d+3}\right)$ best-response moves.

Proof. We will upper-bound the total number of moves during the execution of the algorithm. After the first $n$ best-response moves in line 1, the number of phases executed by the algorithm is at most $n$. At the beginning of the first phase, the latency of any player in $R_{1}$ is at most $n^{d}b_{1}$ (due to the definition of block $B_{1}$ and of the latency functions). Hence, $\Phi_{R_{1}}(S^{0})\leq\sum_{u\in R_{1}}{c_{u}(S^{0})}\leq n^{d+1}b_{1}$. The minimum latency experienced by any player in $R_{1}$ is at least $b_{3}$, so each move in this step decreases the potential $\Phi_{R_{1}}$ by at least $(q-1)b_{3}$. So the total number of moves is at most $\frac{n^{d+1}b_{1}}{(q-1)b_{3}}=2^{2d+2}n^{5\psi+3d+3}$.

At the beginning of any other phase $i\geq 2$, we have that $\Phi_{R_{i}}(S^{i-1})\leq\frac{b_{i}}{2^{d}n^{\psi}}$ (by Lemma 4.3). The minimum latency experienced by any player in $R_{i}$ is at least $b_{i+2}$, so each move in this step decreases the potential $\Phi_{R_{i}}$ by at least $(q-1)b_{i+2}$. So the total number of moves is at most $\frac{b_{i}}{2^{d}n^{\psi}(q-1)b_{3}}=2^{d+2}n^{4\psi+2d+2}$.

In total, we have $O\left(n^{5\psi+3d+3}\right)$ best-response moves. $\sqcap$$\sqcup$

The proof of the following lemma strongly relies on Lemma 4.3. Intuitively, Lemma 4.3 implies that the cost experienced by any player of $R_{i}$ while moving during phase $i$ is considerably lower than the cost of players in blocks $B_{1},\ldots,B_{i-1}$ (who are not supposed to move anymore). The latter means that, for every player $u$ in $B_{1},\ldots,B_{i-1}$, after phase $i$, neither the cost of $u$ may increase considerably, nor the cost that $u$ could experience by a possible deviation may decrease considerably.

Let $u$ be a player in the block $B_{t}$, where $t\leq m-2$. Let $s_{u}^{\prime}$ be a strategy different from the one assigned to $u$ by the algorithm at the end of phase $t$. Then, for each phase $i\geq t$, it holds that

Proof. We will prove the lemma using induction on $i$. For $i=t$, the claim follows by the definition of phase $i$ of the algorithm. Assume that the claim is true for a phase $i$ with $t\leq i\leq m-2$. In the following, we show that the claim is true for the phase $i+1$ as well.

then the claim holds. By the hypothesis of induction, we have

Combining the above three inequalities, we obtain that

In order to complete the proof of the inductive step we are left to prove (6) and (7). We do so by proving that if one of these two inequalities does not hold, this would violate the statement of Lemma 4.3.

Assume that (6) does not hold, i.e., $c_{u}(S^{i+1})>c_{u}(S^{i})+\frac{b_{i+1}}{n^{\psi}}$ for some player $u$ of block $B_{t}$, where $t\leq i$. We will show that the potential $\Phi_{R_{i+1}}(S^{i+1})$ at state $S^{i+1}$ of the subgame among the players in $R_{i+1}$ is larger than $\frac{b_{i+1}}{2^{d}n^{\psi}}$. Since the potential decreases during phase $i+1$, $\Phi_{R_{i+1}}(S^{i})$ should also be larger than $\frac{b_{i+1}}{2^{d}n^{\psi}}$, contradicting Lemma 4.3. Indeed, since player $u$ does not move during phase $i+1$, the increase in her cost from state $S^{i}$ to state $S^{i+1}$ implies the existence of a set of resources $C\subseteq s_{u}$ in her strategy with the following properties: each resource $e\in C$ is also used by at least one player of $R_{i+1}$ in state $S^{i+1}$ and, furthermore, $\sum_{e\in C}{f_{e}(n_{e}(S^{i+1}))}>\frac{b_{i+1}}{n^{\psi}}$. By Claim 2.1, we obtain that $\Phi_{R_{i+1}}(S^{i+1})>\frac{b_{i+1}}{n^{\psi}}$.

Similarly, assume that (7) does not hold for a player $u$ of block $B_{t}$ and a strategy $s^{\prime}_{u}$ that is different from $s_{u}$, the strategy assigned to $u$ in phase $t$, i.e., $c_{u}(S^{i}_{-u},s^{\prime}_{u})>c_{u}(S^{i+1}_{-u},s^{\prime}_{u})+\frac{b_{i+1}}{n^{\psi}}$. Recall that player $u$ does not move during phase $i+1$. This implies that there exists a set of resources $C\subseteq s^{\prime}_{u}$ with the following properties: each resource $e\in C$ is used by at least one player of $R_{i+1}$ in state $S^{i}$ and, furthermore, $\sum_{e\in C}{f_{e}(n_{e}(S^{i}_{-u},s^{\prime}_{u}))}\geq\frac{b_{i+1}}{n^{\psi}}$. Hence, by Claim 2.1 and the definition of the latency functions, we have $\Phi_{R+1}(S^{i})\geq\sum_{e\in C}{f_{e}(n_{e}(S^{i}))}\geq\sum_{e\in C}{\frac{1}{2^{d}}f_{e}(n_{e}(S^{i}_{-u},s^{\prime}_{u}))}>\frac{b_{i+1}}{2^{d}n^{\psi}}$. Again, this contradicts Lemma 4.3.

Hence, (6) and (7) hold and the proof of the inductive step is complete. $\sqcap$$\sqcup$

The next lemma follows easily by Lemma 4.5, the definition of $b_{i}$’s, and the definition of the last phase of the algorithm.

The state computed by the algorithm is a $p\left(1+\frac{4}{n^{\psi}}\right)$-approximate equilibrium.

Proof. We have to show that in the state $S^{m-1}$, computed by the algorithm after the last phase, no player has an incentive to deviate to another strategy in order to decrease her cost by a factor of $p\left(1+\frac{4}{n^{\psi}}\right)$. The claim is certainly true for the players in the blocks $B_{m-1}$ and $B_{m}$ by the definition of the last phase of the algorithm. Let $u$ be a player in block $B_{t}$ with $t\leq m-2$ and let $s^{\prime}_{u}$ be any strategy different from the one assigned to $u$ by the algorithm after phase $t$. We apply Lemma 4.5 to player $u$. By the definition of $b_{i}$’s, we have $\sum_{k=t+1}^{m}{b_{k}}\leq 2b_{t+1}$. Also, $c_{u}(S^{m-1}_{-u},s^{\prime}_{u})\geq b_{t+1}$, since $u$ belongs to block $B_{t}$. Hence, Lemma 4.5 implies that

as desired. The last inequality follows since $p\geq 1$. $\sqcap$$\sqcup$

By the definition of the parameters $q$ and $p$ in our algorithm, we obtain that the state computed is a $\rho_{d}$-approximate equilibrium with

where $\theta_{1}(q)=\frac{2q}{2-q}$, $\theta_{d}(q)\in d^{O(d)}$ and $q=1+n^{-\psi}$. By making simple calculations, we obtain that $\rho_{1}\leq 2+O(n^{-\psi})$ and $\rho_{d}\in d^{O(d)}$. This completes the proof of Theorem 4.1. $\sqcap$$\sqcup$

Discussion and open problems

We remark that the number of best response moves computed by our algorithm depends neither on the number of the resources nor on the number of strategies per player. In fact, our algorithm delegates to the players the computation of their best-response move; the overall running time then depends also on the time required by the players to compute a best-response move from any state of the game and (pseudo-)state $\mathbf{0}$. Of course, the players are expected to be able to do this computation efficiently.

The guarantee of our algorithm depends strongly on the fact that the latency functions have non-negative coefficients. Is this a severe limitation? We answer this question negatively in the next theorem where we prove that the problem of computing approximate equilibria is PLS-complete for congestion games with linear latency functions that have negative offsets (but incurring non-negative latency to any player using the corresponding resource).

Finding an $\rho$-approximate equilibrium in a congestion game with linear laency functions with negative coefficients is PLS-complete, for every polynomial-time computable $\rho>1$.

The reduction yields a congestion game in which every resource is contained in strategies of at most two players. It can also be turned into a congestion game with polynomial latency functions that have degree polynomial in $n$ (see Section B).

Our work reveals several open problems. The most challenging one is whether the guarantee for approximate equilibria that can be computed efficiently can be improved. For example, can we compute $(1+\epsilon)$-approximate equilibria in congestion games with linear latency functions in polynomial time for every (polynomially small) $\epsilon>0$? We believe that this is not the case and our algorithm is close to optimal in this sense. It would be very interesting to see how the best possible approximation guarantee relates to the worst-case ratio of the potential at an almost exact equilibrium over the minimum potential. Here, we point out that we have examples of congestion games for which the upper bound of $2$, provided by Lemma 2.3, is tight when $q$ approaches $1$. Extending this question to polynomial latencies is interesting as well. Note that a nice consequence of our work is that, besides being approximate equilibria, the states computed have low price of anarchy as well (e.g., at least $7.33+O(\epsilon)$ for linear latency functions according to the bounds in ). Providing improved guarantees for the social cost of approximate equilibria that can be computed efficiently or related trade-offs is another interesting line of research. Finally, we strongly believe that our techniques could be applicable to other potential games as well. Typical examples include constraint satisfaction games such as the cut and parity games studied in ; we plan to consider such games in future work.

References

Appendix A Proofs omitted from Sections 2 and 4

The first inequality follows easily by the definition of function $\Phi$. The second one can be obtained by the following derivation:

Proof of Claim 2.2.

We use the definition of the potential function for the original game and the subgames, the definitions of the modified latency functions $f^{F}_{e}(x)=f_{e}(x+n^{N\setminus F}_{e}(S))$ and $f^{N\setminus F}_{e}(x)=f_{e}(x+n^{F}_{e}(S))$, and the equality $n_{e}(S)=n^{F}_{e}(S)+n^{N\setminus F}_{e}(S)$ to obtain

as desired for the first part of the claim. For the second part, we have

Proof of Lemma 2.3.

In the proof, we will need the following technical claim.

For every non-negative integers $x,y$, it holds true $xy\leq\frac{1}{2}x^{2}-\frac{1}{2}x+y^{2}$.

Proof. For $x=1$, the claim clearly holds. Otherwise, observe that $\frac{1}{2}x^{2}-\frac{1}{2}x\geq\frac{1}{4}x^{2}$. Then $0\leq(\frac{x}{2}-y)^{2}=\frac{1}{4}x^{2}+y^{2}-xy\leq\frac{1}{2}x^{2}-\frac{1}{2}x+y^{2}-xy$ and claim follows. $\sqcap$$\sqcup$

For each player $u$ we denote by $s_{u}$ and $s^{*}_{u}$ the strategies she uses at states $S$ and $S^{*}$, respectively. Using the $q$-approximate equilibrium condition, that is $c_{u}(S)\leq q\cdot c_{u}(S_{-u},s^{*}_{u})$, we obtain

for each player $u\in N$. Summing over all players, we get that their total cost is

In the following, we use the definitions of the potential and the latency functions, the fact that $q\geq 1$, inequality (8) \bigg{(}n_{e}(S)\cdot n_{e}(S^{*})\leq\frac{1}{2}n_{e}(S)^{2}-\frac{1}{2}n_{e}(S)+n_{e}(S^{*})^{2}\bigg{)}, and Claim A.1 to obtain

and, equivalently, $\Phi(S)\leq\frac{2q}{2-q}\Phi(S^{*})$. $\sqcap$$\sqcup$

Proof of Lemma 2.4.

Observe that $\Phi(S)\leq\sum_{u\in N}{c_{u}(S)}$ (see Claim 2.1). We will also show that $\Phi(S^{*})\geq\frac{1}{d+1}\sum_{u\in N}{c_{u}(S^{*})}$. The desired bound then follows by the fact that the price of anarchy of $2$-approximate equilibria is at most $d^{O(d)}$. Notice that the price of anarchy is at least $\sum_{u\in N}{c_{u}(S)}/\sum_{u\in N}{c_{u}(S^{*})}$.

We will use the property $\int_{0}^{y}{f(x)}dx\leq\sum_{j=1}^{y}{f(j)},$ that holds for every non-decreasing function $f:[0,y]\rightarrow R$ and integer $y\geq 1$. We prove the desired inequality as follows.

Proof of Lemma 4.2.

We denote by $s_{u}$ the strategy of player $u$ at state $S^{i}$. We rank the players that use resource $e$ in $S^{i}$ according to the timing of their last moves (using consecutive integers $1,2,...$). We denote by $\mbox{rank}_{e}(u)$ the number of players in $R_{i}$ with the smaller ranking than $u$ on resource $e$. Then, we get $c(u)\geq\sum_{e\in s_{u}}{f^{R_{i}}_{e}(\mbox{rank}_{e}(u))}$, since any resource $e$ in $s_{u}$ is occupied by at least $\mbox{rank}_{e}(u)$ players from $R_{i}$ at state $S^{i}$: $u$ and the players with ranks $1,2,...,\mbox{rank}_{e}(u)-1$ that made their last move before $u$. Hence, by the definition of the potential function (expressed using the modified latency functions for the subgame among the players of $R_{i}$), we have

Appendix B Proof of Theorem 5.1

We prove the theorem by reworking the reduction in . From now on, we refer to it as the original or old construction or proof. In the following, we outline our modifications in the original construction (in Section B.1) and prove the correctness of the new one (in Section B.2). Finally, we give a detailed description of the new construction in Section B.3.

Recall that the original proof is a reduction from the PLS-complete problem Flip which is the following:

An instance of the problem Flip consists of a boolean circuit $C$ with $n$ inputs and $m$ outputs. A feasible solution is a bit vector $x_{1},\ldots,x_{n}$ and the objective value is defined as $c(x)=\sum_{i=1}^{k}y_{i}2^{i-1}$ where $y$ is the output produced by $C$ with input $x$. The neighborhood $N(x)$ of solution $x$ is the set of bit vectors $x^{\prime}$ of length $n$ that differs from $x$ in one bit. The objective is to find a local minimum.

The proof describes a transformation of $C$ into a congestion game $G(C)$ which has the property that every pure Nash equilibrium of $G(C)$ corresponds to a local optimum of $C$. Furthermore, it is ensured that every equilibrium is also an $\alpha$-approximate equilibrium for $\alpha\geq\max\{\rho,2\}$ by ensuring that every strategy change of a player decreases her latency by a factor of at least $\alpha$.

Our new construction has the additional property that every resource is part of at most two players’ strategies. Therefore, it suffices to specify only the latency values for one and two players for each resource. For the sake of readability, we depict latency functions by the two values $a/b$, which correspond to $f_{e}(1)=a$ and $f_{e}(2)=b$. This can obviously be turned into a linear function by setting $f_{e}(x)=(b-a)x+2a-b$.

To simplify the presentation, there are many latency functions with $f_{e}(1)=0$. However, we can set $f_{e}(1)=1$ and scale all other latency values by a factor of $|E|\alpha$. This modification does not change the players’ preferences and, by choosing $\alpha\geq 2\rho$, the theorem still holds. Thus, the latency functions can be described as polynomials with positive coefficients. However, their degree has to be polynomial in the number of players.

A close look at the original reduction reveals that most of the resources are used by at most two players. The only resources for which this is not the case are the resources Bit1k of the subgames $G(S)$ and all Lock resources. Unfortunately, those resources are part of the lockable circuits, the most important feature of this reduction. We will replace these resources and add new strategies and new players to the game. See Figures 2 to 6 for a complete description of the players’ strategies, the resources, and latency functions.

In the original construction, a gate player has two strategies which correspond to the two values of the output of that gate. Her best response is determined by the players that correspond to the inputs of this gate. This requires latency functions for the bit resources that are not linear, i.e., latency of for two players and latency of $\alpha^{2k}$ for three players. We can avoid this, by the following changes:

Instead of one strategy One, a gate player $G_{i}$ now has two strategies OneA and OneB. If input $a$ of her gate is $1$, her best response is not to choose OneA. If input $b$ of her gate is $1$, her best response is not to choose OneB. As before, choosing Zero is only a best response if both inputs are $1$. For gates that have $g_{i}$ as input, there is no difference between $G_{i}$ choosing OneA or OneB and the semantics of NAND is preserved by this construction. The Lock resources that also required nonlinear latency functions in the original construction are replaced by individual copies for each gate player.

The Lock resources play a central role in the reduction. They ensure that a state is either expensive, i,.e., some player has latency of at least $M$, or the state is part of a sequence of states that simulates an improvement step in the Flip-instance. We call such a sequence a superstep (see Figure 1).

Finally, the Controller now has two reset strategies instead of one in the old construction. This is necessary in order to ensure that the $Y$ players are actually reset to their One strategies before locking a circuit.

B.2 Proof of correctness

None of the states in $Z_{1},\ldots,Z_{4}$ is an equilibrium.

The proof of the lemma considers the sets one after the other and shows that in each of them there is a player that has an improving move. In our modified construction, we need to show that none of the resources that we added or modified prevents such a move.

None of the states in $Z_{5}$ or $Z_{6}$ is an equilibrium.

Suppose $s$ is a base state in equilibrium. Then, the bit vector $x$ represented by the input players is a local optimum of $C$.

B.3 Detailed description of G​(C)𝐺𝐶G(C)

Recall that $\beta=\alpha^{2K+1}$ with $K$ being the total number of gates over all circuits and $\gamma=2\alpha\beta$. That is, $\alpha\ll\beta\ll\gamma\ll M$.