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

Introduction

Among other solution concepts, the notion of the pure Nash equilibrium plays a central role in Game Theory. Pure Nash equilibria in a game characterize 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. Unfortunately, it is well known that there are games that do not have pure Nash equilibria. Furhermore, even in games where the existence of equilibria is guaranteed, their computation can be a computationally hard task. Such negative 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 exist and can be computed efficiently. In this paper, we present the first positive algorithmic results for approximate pure Nash equilibria in weighted congestion games. Our main contribution is a polynomial-time algorithm that computes $O(1)$-approximate pure Nash equilibria under mild restrictions on the game parameters; these restrictions apply to important subclasses of games in which not even the existence of such approximate equilibria was known prior to our work.

Problem statement and related work. In a weighted congestion game, players compete over a set of resources. Each player has a positive weight. Each resource incurs a latency to all players that use it; this latency depends on the total weight of the 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 weighted congestion games in networks, where the network links correspond to the resources and each player has alternative paths that connect two nodes as strategies.

The case of unweighted congestion games (i.e., when all players have unit weight) has been widely studied in literature. Rosenthal proved that these 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. For weighted congestion games, potential functions exist only in the case where the latency functions are linear or exponential (see ). Actually, in games with polynomial latency functions (of constant maximum degree higher than $1$), pure Nash equilibria may not exist . In general, the problem of deciding whether a given weighted congestion game has a pure Nash equilibrium is NP-hard .

Potential functions provide only inefficient proofs of existence of pure Nash equilibria. Fabrikant et al. proved that the problem of computing a pure Nash equilibrium in a (unweighted) congestion game is PLS-complete (informally, as hard as it could be given that there is an associated potential function; see ). This negative result holds even in the case of linear latency functions . One consequence of PLS-completeness results is that almost all states in some congestion games are such that any sequence of players’ improvement moves that originates from these states and reaches pure Nash equilibria is exponentially long. Such phenomena have been observed even in very simple weighted congestion games (see ). Efficient algorithms are known only for special cases. For example, Fabrikant et al. show that the Rosenthal’s potential function can be (globally) minimized efficiently by a flow computation in unweighted congestion games in networks when the strategy sets of the players are symmetric.

The above negative results have led to the study of the complexity of approximate pure Nash equilibria (or, simply, approximate 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$. In our recent work , we present an algorithm for computing $O(1)$-approximate equilibria for unweighted congestion games with polynomial latency functions of constant maximum degree. The restriction on the latency functions is necessary since, for more general latency functions, Skopalik and Vöcking show that the problem is still PLS-complete for any polynomially computable $\rho$ (see also the discussion in ). Improved bounds are known for special cases. For symmetric unweighted congestion games, Chien and Sinclair prove that the $(1+\epsilon)$-improvement dynamics converges to a $(1+\epsilon$)-approximate equilibrium after a polynomial number of steps; this result holds under mild assumptions on the latency functions and the participation of the players in the dynamics. Efficient algorithms for approximate equilibria have been recently obtained for other classes of games such as constraint satisfaction , anonymous games , network formation , and facility location games .

In light of the negative results mentioned above, 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 in linear weighted congestion games. In particular, Awerbuch et al. show that using almost unrestricted sequences of ($1+\epsilon$)-improvement best-response moves, the players rapidly converge to efficient states. Unfortunately, these states are not approximate equilibria, in general. Similar approaches have been followed in the context of other games as well, such as multicast , cut , and valid-utility games .

Our contribution. To the best of our knowledge, no efficient algorithm for computing approximate equilibria is known for (any broad enough subclass of) weighted congestion games. We fill this gap by presenting an algorithm for computing $O(1)$-approximate equilibria in weighted congestion games with polynomial latency functions of constant maximum degree. 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 of maximum degree $d\geq 2$, it is $d^{2d+o(d)}$. The algorithm runs in time that is polynomial in the number of bits in the representation of the game and $1/\gamma$.

This result is much more surprising than it looks at first glance. In particular, weighted congestion games with superlinear latency functions do not admit potential functions, the main tool that is exploited by all known positive algorithmic results for (approximate) equilibria in congestion games. Given this, it is not even clear that $O(1)$-approximate equilibria exist. In order to bypass this obstacle, we introduce a new class of potential games (that we call $\Psi$-games), which “approximate” weighted congestion games with polynomial latency functions in the following sense. $\Psi$-games of degree $1$ are linear weighted congestion games. Each weighted congestion game of degree $d\geq 2$ has a corresponding $\Psi$-game of degree $d$ defined in such a way that any $\rho$-approximate equilibrium in the latter is a $d!\rho$-approximate equilibrium for the former. As an intermediate new result, we obtain that weighted congestion games with polynomial latency functions of degree $d$ have $d!$-approximate equilibria.

So, our algorithm is actually applied to $\Psi$-games. It has a simple general structure, similar to our recent algorithm for unweighted congestion games , but has also important differences that are due to the dependency of the cost of each player on the weights of other players. Given a $\Psi$-game of degree $d$ and an arbitrary initial state, the algorithm computes a sequence of best-response player moves of length that is bounded by a polynomial in the number of bits in the representation of the game and $1/\gamma$. 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. Within each phase, the algorithm 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 approximation guarantee is slightly higher than a quantity that characterizes the potential functions of $\Psi$-games; this quantity (which we call the stretch) is defined as the worst-case ratio of the potential value at an almost exact pure Nash equilibrium over the globally optimum potential value and is almost $\frac{3+\sqrt{5}}{2}$ for linear weighted congestion games and $d^{d+o(d)}$ for $\Psi$-games of degree $d\geq 2$. Our analysis follows the same main steps as in our recent paper but uses significantly more involved arguments due to the definition of $\Psi$-games.

We also present a similar but slightly inferior algorithm that is applied directly to weighted congestion games of maximum degree $d\geq 2$ and reveals a rather surprising structural property of their Nash dynamics: starting from any initial state, the algorithm identifies a polynomially-long sequence of best-response moves that lead to a $d^{O(d^{2})}$-approximate equilibrium. Even though the definition of this algorithm does not make any use of properties of $\Psi$-games, the analysis is heavily based on them, similarly to the analysis of our main algorithm.

We remark that, following the classical definition of polynomial latency functions in the literature, we assume that they have non-negative coefficients. This is a necessary limitation since the problem of computing a $\rho$-approximate equilibrium in (unweighted) congestion games with linear latency functions with negative offsets is PLS-complete for any polynomial-time computable $\rho\geq 1$ .

Roadmap. We begin with preliminary general definitions in Section 2. Section 3 is devoted to $\Psi$-games and their properties. We present our algorithm and its analysis in Section 4 and conclude with open problems in Section 5. Due to lack of space, most of the proofs as well as our structural result appears in Appendix.

Definitions and preliminaries

In general, a game can be defined as follows. It has a set of $n$ players ${\cal N}$; each player $u\in{\cal N}$ has a set of available strategies $\Sigma_{u}$. A snapshot of strategies, with one strategy per player, is called a state. Each state $S\in\prod_{u\in{\cal N}}{\Sigma_{u}}$ incurs a positive cost $c_{u}(S)$ to player $u$. 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$ and a strategy $s^{\prime}_{u}\in\Sigma_{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 state $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 $\rho\geq 1$, such a move is called a $\rho$-move if it satisfies $c_{u}(S_{-u},s^{\prime}_{u})<\frac{c_{u}(S)}{\rho}$. 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)$. 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{\cal N}$ and every strategy $s^{\prime}_{u}\in\Sigma_{u}$, i.e., when no player has a move. In this case, we say that no player has (any incentive to make) a move. Similarly, a state is called a $\rho$-approximate pure Nash equilibrium (henceforth called, simply, a $\rho$-approximate equilibrium) when no player has a $\rho$-move. Also, a state is called a $\rho$-approximate equilibrium for a subset of players $A\subseteq{\cal N}$ if no player in $A$ has a $\rho$-move. We use the term Nash dynamics of a game in order to refer to the directed graph with nodes that correspond to the possible states of the game and directed edges that indicate improvement player moves; pure Nash equilibria correspond to sinks of the Nash dynamics.

A weighted congestion game ${\cal G}$ can be represented by the tuple $\left(N,E,(w_{u})_{u\in{\cal N}},(\Sigma_{u})_{u\in{\cal N}},(f_{e})_{e\in E}\right)$. There is a set of $n$ players ${\cal N}$ and a set of resources $E$. Each player $u$ has a positive weight $w_{u}$ and a set of available strategies $\Sigma_{u}$; each strategy $s_{u}$ in $\Sigma_{u}$ consists of a non-empty set of resources, i.e., $s_{u}\subseteq 2^{E}$. Each resource $e\in E$ has a non-negative and non-decreasing latency function $f_{e}$ defined over non-negative reals, which denotes the latency incurred to the players using resource $e$; this latency depends on the total weight of players whose strategies include the particular resource. For a state $S$, let us define $N_{e}(S)$ to be the multi-set of the weights of the players that use resource $e$ in $S$, i.e., $N_{e}(S)=\{w_{u}:u\in{\cal N}\mbox{ such that }e\in s_{u}\}$. Also, we use the notation $L(A)$ to denote the sum of the elements of a finite multi-set of reals $A$. Then, the latency incurred by resource $e$ to a player $u$ that uses it is $f_{e}(L(N_{e}(S)))$. The cost of a player $u$ at a state $S$ is the total latency she experiences at the resources in her strategy $s_{u}$ multiplied by her weight, i.e., $c_{u}(S)=w_{u}\sum_{e\in s_{u}}{f_{e}(L(N_{e}(S)))}$. We consider weighted congestion games in which the resources have polynomial latency functions with (integer) maximum degree $d\geq 1$ with non-negative coefficients. More precisely, the latency function of resource $e$ is $f_{e}(x)=\sum_{k=0}^{d}{a_{e,k}x^{k}}$ with $a_{e,k}\geq 0$. The special case of linear weighted congestion games (i.e., with latency functions of degree $1$) is of particular interest. In general, the size of the representation of a weighted congestion game is the number of bits required to represent the parameters $a_{e,k}$ of the latency functions, the weights of the players, and their strategy sets. In weighted congestion games in networks, the network links are the resources. Each player $u$ aims to connect a pair of nodes $(s_{u},t_{u})$ and her strategies are all paths connecting $s_{u}$ with $t_{u}$ in the network. Note that the representation of such games does not need to keep the whole set of strategies explicitly; it just has to represent the parameters $a_{e,k}$, the weight and the source-destination node pair of each player, and the network.

ΨΨ\Psi-games

Our aim in this section is to define a new class of games which we call $\Psi$-games and study their properties. We will need the following interesting family of functions which have also been used in in a slightly different context.

So, $\Psi_{k}(A)$ is essentially the sum of all monomials of total degree $k$ on the elements of $A$. Each term in the sum has coefficient $k!$. Clearly, $\Psi_{1}(A)=L(A)$. For $k\geq 2$, compare $\Psi_{k}(A)$ with $L(A)^{k}$ which can also be expressed as the sum of the same terms, albeit with different coefficients in $\{1,...,k!\}$, given by the multinomial theorem.

We are ready to define $\Psi$-games. A $\Psi$-game ${\cal G}$ of (integer) degree $d\geq 1$ can be represented by the tuple $({\cal N},E,(w_{u})_{u\in{\cal N}},(\Sigma_{u})_{u\in{\cal N}},(a_{e,k})_{e\in E,k=0,1,...,d})$. Similarly to weighted congestion games, there is a set of $n$ players ${\cal N}$ and a set of resources $E$. Each player $u$ has a weight $w_{u}$ and a set of available strategies $\Sigma_{u}$; each strategy $s_{u}\in\Sigma_{u}$ consists of a non-empty set of resources, i.e., $s_{u}\subseteq 2^{E}$. Each resource $e$ is associated with $d+1$ non-negative numbers $a_{e,k}$ for $k=0,1,...,d$. Again, for a state $S$, we define $N_{e}(S)$ to be the multi-set of weights of the players that use resource $e$ at state $S$. Then, the cost of a player $u$ at a state $S$ is defined as

Of course, the general definitions in the beginning of Section 2 apply also to $\Psi$-games. With some abuse in notation, we also use $\mathbf{0}$ to refer to the pseudo-state in which no player selects any strategy and ${\mathcal{BR}}_{u}(\mathbf{0})$ to denote the best-response of player $u$ assuming that no other player participates in the game.

Clearly, given a weighted congestion game with polynomial latency functions of maximum degree $d$, there is a corresponding $\Psi$-game with degree $d$, i.e., the one with the same sets of players, resources, and strategy sets, and parameter $a_{e,k}$ for each resource $e$ and integer $k=0,1,...,d$ equal to the corresponding coefficient of the latency function $f_{e}$. Observe that $\Psi$-games of degree $1$ are linear weighted congestion games. As we will see below, in a sense, a $\Psi$-game of degree $d\geq 2$ is an approximation of its corresponding weighted congestion game.

We remark here that a different approximation of weighted congestion games has been recently considered by Kollias and Roughgarden . Given a weighted congestion game, they define a new game by answering the following question: how should the product of the total weight of the players that use the resource times its latency be shared as cost among these players so that the resulting game is a potential game? Their games use a different sharing than the weight-proportional one used by weighted congestion games. In contrast, our approach is to define an artificial latency on each resource $e$ (by replacing the term $a_{e,k}L(N_{e}(S))^{k}$ with $a_{e,k}\Psi_{k}(N_{e}(S))$ in the latency functions) so that weight-proportional sharing yields a potential game. This guarantees the relation between approximate equilibria in weighted congestion games and $\Psi$-games presented in Lemma 3.4 below, which is crucial for our purposes.

Properties of $\Psi$-games. We begin with a very important property of $\Psi$-games.

The function $\Phi(S)=\sum_{e}{\sum_{k=0}^{d}{\frac{a_{e,k}}{k+1}\Psi_{k+1}(N_{e}(S))}}$ is a potential function for $\Psi$-games of degree $d$.

As a corollary, we conclude that the Nash dynamics of $\Psi$-games are acyclic; hence, these games admit pure Nash equilibria. Recall that $\Psi$-games of degree $1$ are linear weighted congestion games; for this specific case, Theorem 3.2 has been proved in .

In the following, we study the relation between the approximation guarantee of a state for a $\Psi$-game and its corresponding weighted congestion game with polynomial latency functions.

Consider a weighted congestion game with polynomial latency functions of degree $d$ and its corresponding $\Psi$-game. Then, for each player $u$ and state $S$, $c_{u}(S)\leq\hat{c}_{u}(S)\leq d!c_{u}(S)$.

Using Claim 3.3, we can obtain a relation between approximate equilibria as well.

Any $\rho$-approximate pure Nash equilibrium for a $\Psi$-game of degree $d$ is a $d!\rho$-approximate pure Nash equilibrium for the corresponding weighted congestion game with polynomial latencies.

Since pure Nash equilibria always exist in $\Psi$-games, the last statement (applied with $\rho=1$) implies the following.

Every weighted congestion game with polynomial latency functions of maximum degree $d$ has a $d!$-approximate pure Nash equilibrium.

Subgames and partial potentials. We now define restrictions of the potential function of $\Psi$-games. Given a state $S$ and a set of players $A\subseteq{\cal N}$, we denote by $N_{e}^{A}(S)$ the multiset of the weights of players in $A$ that use resource $e$ in $S$. Then, we define

We can think of $\Phi^{A}$ as the potential of a subgame in which only the players of $A$ participate.

We also use the notion of the partial potential to account for the contribution of subsets of players to the potential function. Consider sets of players $A$ and $B$ with $B\subseteq A\subseteq{\cal N}$. Then, the $B$-partial potential of the subgame among the players in $A$ is defined as

The next four claims present basic properties of partial potentials.

Let $S$ be a state of a $\Psi$-game and let $B\subseteq A\subseteq{\cal N}$. Then, $\Phi_{B}^{A}(S)\leq\Phi_{B}(S)$.

Let $A\subseteq{\cal N}$ be a set of players and let $S$ and $S^{\prime}$ be states such that each player in $A$ uses the same strategy in $S$ and $S^{\prime}$. Then, for every set of players $B\subseteq A$, $\Phi^{A}_{B}(S)=\Phi^{A}_{B}(S^{\prime})$.

Let $S$ be a state of a $\Psi$-game and let $u$ be a player. Then, $\Phi_{u}(S)=\hat{c}_{u}(S)$.

Let $u$ be a player and $A\subseteq{\cal N}$ a set of players that contains $u$. Then, for any two states $S$ and $S^{\prime}$ that differ only in the strategy of player $u$, it holds that $\Phi_{A}(S)-\Phi_{A}(S^{\prime})=\hat{c}_{u}(S)-\hat{c}_{u}(S^{\prime})$.

In particular, Claim 3.9 implies that the $A$-partial potential can be thought of as a potential function defined over all states in which each player in ${\cal N}\setminus A$ uses the same strategy.

We proceed with the following interesting property that shows that the potential function of $\Psi$-games is cost-revealing. It also implies that the potential of a state lower-bounds the total cost of all players.

For every state $S$ of a $\Psi$-game and any set of players $A\subseteq{\cal N}$, it holds that $\Phi_{A}(S)\leq\sum_{u\in A}{\hat{c}_{u}(S)}$.

The stretch of the potential function. An important quantity for our purposes is the stretch of the potential function of $\Psi$-games; a general definition that applies to every potential game follows.

Consider a potential game with a positive potential function $\Phi$ and let $S^{*}$ be the state of minimum potential. The $\rho$-stretch of the potential function of the game is the maximum over all $\rho$-approximate pure Nash equilibria $S$ of the ratio $\Phi(S)/\Phi(S^{*})$.

The next two statements provide bounds on the $\rho$-stretch of the potential function of $\Psi$-games of degree $1$ (i.e., linear weighted congestion games) and $d\geq 2$, respectively.

For every $\rho\in[1,11/10]$, the $\rho$-stretch of the potential function of a linear weighted congestion game is at most $\frac{3+\sqrt{5}}{2}+6(\rho-1)$.

The $\rho$-stretch of the potential function of a $\Psi$-game of degree $d\geq 2$ is at most $\rho(\rho+1)^{d}(d+1)^{d+1}$.

In the rest of the paper, we denote by $\theta_{d}(\rho)$ the upper bounds on the $\rho$-stretch given by Lemmas 3.12 and 3.13, namely $\theta_{1}(\rho)=\frac{3+\sqrt{5}}{2}+6(\rho-1)$ and $\theta_{d}(\rho)=\rho(\rho+1)^{d}(d+1)^{d+1}$. The next lemma extends these bounds to partial potentials.

Consider a $\Psi$-game of degree $d$ and a state $S$ which is a $\rho$-approximate pure Nash equilibrium for a set of players $R\subseteq{\cal N}$. Then, $\Phi_{R}(S)\leq\theta_{d}(\rho)\Phi_{R}(S^{*})$ for any state $S^{*}$ such that each player in ${\cal N}\setminus R$ uses the same strategy in $S$ and $S^{*}$.

The algorithm

In this section we describe our algorithm (Algorithm 1; see the table below). The algorithm takes as input a $\Psi$-game ${\cal G}$ of degree $d$ with $n$ players, an arbitrary initial state $S$ of the game, and a small positive parameter $\gamma$. It produces as output a state of ${\cal G}$. The algorithm starts by initializing its parameters, namely $\hat{c}_{\max}$, $\hat{c}_{\min}$, $m$, $g$, $q$, and $p$ (lines 1-6). It first computes the minimum possible cost $\hat{c}_{\min}$ among all players and the maximum cost $\hat{c}_{\max}$ experienced by players in the initial state $S$. Then, it sets the parameter $m$ equal to $\log{\left(\hat{c}_{\max}/\hat{c}_{\min}\right)}$; in this way, $m$ is polynomial in the number of bits in the representation of the game (i.e., polynomial in the number of bits necessary to store the parameters $a_{e,k}$ and the weights of the players). Then, the parameter $q$ is set close to $1$ (namely, $q=1+\gamma$) and parameter $p$ is set close to $\theta_{d}(q)$ (namely, $p=\left(\frac{1}{\theta_{d}(q)}-2\gamma\right)^{-1}$). Recall that $\theta_{d}(q)$ is the bound on the $q$-stretch of the potential function of $\Psi$-games of degree $d$ in the statements of Lemmas 3.12 (for $d=1$) and 3.13 (for $d\geq 2$).

Then, the algorithm runs a sequence of phases; within each phase, it coordinates best-response moves of the players. This process starts (line 7) by computing a decreasing sequence of boundaries $b_{0}$, $b_{1}$, $b_{2}$, …, $b_{m}$ that will be used to define the sets of players that are considered to move within each phase. Then, it executes phase (lines 8-10). During this phase, as long as there are players of cost at least $b_{1}$ that have a $q$-move, they play a best-response strategy. Hence, after the end of the phase, all players with cost higher than $b_{1}$ are in a $q$-approximate equilibrium. Then, the algorithm uses set $F$ to keep the players whose strategies have been irrevocably decided; $F$ is initialized to $\emptyset$ in line 11. Phases $1$ to $m-1$ (lines 12-17) constitute the heart of our algorithm. During each such phase $i$, the algorithm repeatedly checks whether, in the current state, there is a player that either has cost higher than $b_{i}$ that has a $p$-move or her cost is in $[b_{i+1},b_{i})$ and has a $q$-move. While such a player is found, she deviates to her best-response strategy. The phase terminates when no such player exists and the algorithm irrevocably decides the strategy of the players that have cost at least $b_{i}$. These players are included in set $F$; at this point, they are guaranteed to be at a $p$-approximate equilibrium. Subsequent moves by other players may either increase their cost or decrease the cost they could experience by deviating to another strategy. As we will show, these changes are not significant and each player will still be at an almost $p$-approximate equilibrium at the end of all phases. The fact that plays a crucial role towards proving such a claim is that, at the end of each phase $i$, any player with cost in $[b_{i+1},b_{i})$ is guaranteed to be in a $q$-approximate equilibrium. Note that $b_{m}\leq\hat{c}_{\min}$ and, eventually, all players will be included in set $F$.

We remark that the sequence of the phases is similar to the one in our algorithm for unweighted congestion games with polynomial latency functions of constant degree $d$ in . However, there is an important difference. In that context, each player is considered to move during only two consecutive phases; these phases are defined statically based only on the characteristics of the particular player. The main reason that allows this is that the cost that a player may experience by following a specific strategy may change by at most a polynomial factor (namely, at most $n^{d}$) during the execution of the algorithm. This is not the case in the context of $\Psi$-games since the fact that the cost of a player depends on the weights of the other players does not satisfy this polynomial relation. So, in the current algorithm, the players that are considered to move within each phase are decided dynamically based on the cost they experience during a phase. In this way, a player may (be considered to) move in many different phases.

Below, we will prove the following statement.

Algorithm 1 computes a $\hat{\rho}_{d}$-approximate equilibrium for every $\Psi$-game of constant degree $d$, where $\hat{\rho}_{1}=\frac{3+\sqrt{5}}{2}+O(\gamma)$ and $\hat{\rho}_{d}\in d^{d+o(d)}$. The running time is polynomial in $\gamma^{-1}$ and in the number of bits in the representation of the game.

Combined with Lemma 3.4, Theorem 4.1 immediately yields the following result for weighted congestion games.

When Algorithm 1 is applied to the $\Psi$-game corresponding to a weighted congestion game with polynomial latency functions of constant degree $d$, it computes a state which is a $\rho_{d}$-approximate equilibrium for the latter, where $\rho_{1}=\frac{3+\sqrt{5}}{2}+O(\gamma)$ and $\rho_{d}\in d^{2d+o(d)}$ for $d\geq 2$.

The rest of this section is devoted to proving Theorem 4.1. Throughout the section we consider the application of the algorithm on a $\Psi$-game of degree $d$ and denote by $S^{i}$ the state computed by the algorithm after the execution of phase $i$ for $i=0,1,...,m-1$. Also, we use $R_{i}$ to denote the set of players that make at least one move during phase $i$. Our arguments are split in three parts. First, we present a key property maintained by our algorithm stating that the $R_{i}$-partial potential is small when the phase $i\geq 1$ starts. Then, we use this fact together with the parameters of the algorithm to prove that the running time is polynomial. The proof of the approximation guarantee follows. Recall that the players whose strategies are irrevocably decided during phase $j\geq 1$ are at a $p$-approximate equilibrium at the end of the phase. The purpose of the third part of the proof is to show that for each such player, neither her cost increases significantly nor the cost she would experience by deviating to another strategy decreases significantly after phase $j$. Hence, the approximation guarantee in the final state computed by the algorithm is slightly higher than $p$.

We remark that the analysis follows the same general steps as in our recent paper on unweighted congestion games . However, due to the definition of $\Psi$-games and the dependency of players’ cost on the weights, different and significantly more involved arguments are required, especially in the first and third step.

The key property maintained by our algorithm is the following.

For every phase $i\geq 1$, it holds that $\Phi_{R_{i}}(S^{i-1})\leq\gamma^{-1}nb_{i}$.

We will now use Lemma 4.3 and the properties of $\Psi$-games to prove that the algorithm terminates quickly.

The algorithm terminates after a number of steps that is polynomial in the number of bits in the representation of the game and $\gamma^{-1}$.

Proof. Clearly, if the number of strategies is polynomial in the number of resources, computing a best-response strategy for a player $u$ can be trivially performed in polynomial time (by the definition of $\hat{c}_{u}$). This is also the case for weighted congestion games in networks (where the number of strategies of a player can be exponential) using a shortest path computation. So, it remains to bound the total number of player moves.

At the initial state, the total cost of the players and, consequently (by Lemma 3.10), its potential is at most $n\hat{c}_{\max}$. Each of the players that move during phase decreases her cost and, consequently (by Theorem 3.2), the potential by at least $(q-1)b_{1}=\gamma g^{-1}\hat{c}_{\max}$. Hence, the total number of moves in phase is at most $n\gamma^{-1}g$. For $i\geq 1$, we have $\Phi_{R_{i}}(S^{i})\leq nb_{i}\gamma^{-1}$ (by Lemma 4.3). Each of the players in $R_{i}$ that move during phase $i$ decreases her cost and, consequently (by Claim 3.9), the $R_{i}$-partial potential by at least $(q-1)b_{i+1}=b_{i}g^{-1}\gamma$. Hence, phase $i$ completes after at most $ng\gamma^{-2}$ moves. In total, we have at most $mng\gamma^{-2}$ moves. The theorem follows by observing that $g$ depends polynomially on $m$, $n$, and $\gamma^{-1}$. $\sqcap$$\sqcup$

It remains to prove that our algorithm computes approximate equilibria. Our proofs will exploit Lemma 4.3 as well as the following lemma which relates the cost of a player in a state to the partial potential of two different subgames.

Consider a $\Psi$-game of degree $d$, a player $u$ and a set of players $R\subseteq{\cal N}\setminus\{u\}$. Then, for every state $S$ and every $\epsilon>0$, it holds that

where $\xi_{\epsilon}=(1+1/\epsilon)^{d}d^{d}-1$.

Using Lemmas 4.3 and 4.5, we will show that neither the cost of a player increases significantly after the phase at the end of which her strategy was irrevocably decided (in Lemma 4.6), nor the cost she would experience by deviating to another strategy decreases significantly (in Lemma 4.7).

Let $u$ be a player whose strategy was irrevocably decided at phase $j$. Then, $\hat{c}_{u}(S^{m-1})\leq(1+2\gamma)\hat{c}_{u}(S^{j})$.

Proof. For every $i>j$ and $\epsilon>0$, we apply Lemma 4.5 for strategy $S^{i}$, player $u$, and the set of players $R_{i}$ that move during phase $i$ to obtain

The equality holds by Claim 3.7 since the players in ${\cal N}\setminus R_{i}$ do not move during phase $i$. The second inequality follows by Claim 3.6. The last one follows by Claim 3.8 and since the $R_{i}$-partial potential decreases during phase $i$.

We now set $\epsilon=(1+\gamma)^{1/m}-1$. This implies that $(1+\epsilon)^{m}=1+\gamma$. Also, by Claim A.2 (in Appendix A), we get $\epsilon\geq\frac{\gamma}{m}(1+\gamma)^{1/m-1}\geq(m(1+\gamma^{-1}))^{-1}$ and, by the definition of the parameters $g$ and $\gamma$, $\xi_{\epsilon}=(1+m(1+\gamma^{-1}))^{d}d^{d}-1\leq\frac{g\gamma^{3}}{2n}\leq\frac{g\gamma}{2(1+\gamma^{-1})n}$. Using the above inequality together with these observations, we obtain

The second inequality is obvious, the third one follows by Lemma 4.3 and by the relation between $\epsilon$ and $\gamma$, the equality follows by the definition of $b_{i}$, the fourth inequality follows since $g\geq 2$ which implies that $\sum_{i\geq 1}{g^{-i}}\leq 2g^{-1}$, the fifth one follows by our observation about $\xi_{\epsilon}$ above, and the last one follows since, by the definition of the algorithm, the fact that the strategy of player $u$ is irrevocably decided at phase $j$ implies that $\hat{c}_{u}(S^{j})\geq b_{j}$. $\sqcap$$\sqcup$

Let $u$ be a player whose strategy was irrevocably decided at phase $j$ and let $s^{\prime}_{u}$ be any of her strategies. Then, $\hat{c}_{u}(S^{m-1}_{-u},s^{\prime}_{u})\geq(1-2\gamma)\hat{c}_{u}(S^{j}_{-u},s^{\prime}_{u})$.

We are now ready to use the last two lemmas in order to prove the approximation guarantee of the algorithm. This will complete the proof of Theorem 4.1.

Given a $\Psi$-game of degree $d$, the algorithm computes a $\hat{\rho}_{d}$-approximate equilibrium with $\hat{\rho}_{1}\leq\frac{3+\sqrt{5}}{2}+O(\gamma)$ and $\hat{\rho}_{d}\leq d^{d+o(d)}$.

Conclusions and open problems

Due to lack of space, the modification of Algorithm 1 that yields our structural result for weighted congestion games with superlinear latency functions is presented in Appendix D.

Our work reveals interesting open problems. The obvious one is whether approximate equilibria with a better approximation guarantee can be computed in polynomial time. We believe that our techniques have reached their limits for linear weighted congestion games. However, in the case of superlinear latency functions, approximations of weighted congestion games by potential games different than $\Psi$-games might yield improved (existential or algorithmic) approximation guarantees. On the conceptual level, it is interesting to further explore applications of approximations of non-potential games by potential ones like the one we have exploited in the current paper.

References

Appendix A Two technical inequalities

The following technical inequalities are extensively used in our proofs and are included here for easy reference.

$\sum_{t=1}^{s}{(\alpha_{t}+\beta_{t})^{k}}\leq\left(\left(\sum_{t=1}^{s}{\alpha_{t}^{k}}\right)^{1/k}+\left(\sum_{t=1}^{s}{\beta_{t}^{k}}\right)^{1/k}\right)^{k}$, for any integer $k\geq 1$ and $\alpha_{t},\beta_{t}\geq 0$.

For every $\alpha\in(0,1)$ and $z>1$, it holds that $z^{\alpha}-1\geq\alpha(z-1)z^{\alpha-1}$.

Proof. The function $h(x)=x^{\alpha}$ is concave in $[1,+\infty)$. This means that, for every $z>1$, the line connecting points $(1,1)$ and $(z,h(z))$ has slope higher than the derivative of $h$ at point $z$, i.e., $\frac{z^{\alpha}-1}{z-1}\geq\alpha z^{\alpha-1}$. Equivalently, $z^{\alpha}-1\geq\alpha(z-1)z^{\alpha-1}$. $\sqcap$$\sqcup$

Appendix B Omitted proofs from Section 3

The following lemma is proved in (the full version of) and is extensively used in our proofs.

For any integer $k\geq 1$, any finite multi-set of non-negative reals $A$, and any non-negative real $b$ the following hold:

Consider a player $u$, a state $S$ in which $u$ plays strategy $s_{u}$ and state $(S_{-u},s^{\prime}_{u})$ where $u$ has deviated to strategy $s^{\prime}_{u}$. Using the definition of the potential function, we have

The third equality follows by Lemma B.1d and the facts that $N_{e}(S)=N_{e}(S_{-u},s^{\prime}_{u})\cup\{w_{u}\}$ for every resource $e\in s_{u}\setminus s^{\prime}_{u}$ and $N_{e}(S_{-u},s^{\prime}_{u})=N_{e}(S)\cup\{w_{u}\}$ for every resource $e\in s^{\prime}_{u}\setminus s_{u}$. The last equality follows by the definition of $\hat{c}_{u}$. $\sqcap$$\sqcup$

B.2 Proof of Claim 3.3

We will use Lemma B.1a and the definitions of $c_{u}(S)$ and $\hat{c}_{u}(S)$. Let $s_{u}$ be the strategy of player $u$ at state $S$. Using the first inequality of Lemma B.1a, we have

Also, using the second inequality in Lemma B.1a, we have

B.3 Proof of Lemma 3.4

Let $S$ be $\rho$-approximate equilibrium for a $\Psi$-game of degree $d$, $u$ a player and $s^{\prime}_{u}$ a strategy of $u$ different than her strategy $s_{u}$ in $S$. Using the $\rho$-approximate equilibrium condition for player $u$ and Claim 3.3, we have

B.4 Proof of Claim 3.6

Let $k\geq 1$ be an integer and consider a resource $e$ which is used by at least one player of $B$ in $S$. By the definition of $\Psi_{k}$, observe that $\Psi_{k}(N^{A}_{e}(S))-\Psi_{k}(N^{A\setminus B}_{e}(S))$ is equal to $k!$ times the sum of all monomials of degree $k$ among the elements of $N^{A}_{e}(S)$ that contain at least one element in $N^{B}_{e}(S)$. Similarly, $\Psi_{k}(N_{e}(S))-\Psi_{k}(N^{{\cal N}\setminus B}_{e}(S))$ is equal to $k!$ times the sum of all monomials of degree $k$ among the elements of $N_{e}(S)$ that contain at least one element in $N^{B}_{e}(S)$. Since $N^{A}_{e}(S)\subseteq N_{e}(S)$, we have that

The inequality holds trivially (with equality) if no player from $B$ uses resource $e$ in $S$. Using this inequality and the definition of the partial potential, we have

B.5 Proof of Claim 3.7

Observe that $N^{A^{\prime}}_{e}(S)=N^{A^{\prime}}_{e}(S^{\prime})$ for each resource $e$ and any $A^{\prime}\subseteq A$. By the definition of the potential of the subgame among the players of $A^{\prime}$, we have $\Phi^{A^{\prime}}(S)=\Phi^{A^{\prime}}(S^{\prime})$. Then, by the definition of the partial potential, $\Phi^{A}_{B}(S)=\Phi^{A}(S)-\Phi^{A\setminus B}(S)=\Phi^{A}(S^{\prime})-\Phi^{A\setminus B}(S^{\prime})=\Phi^{A}_{B}(S^{\prime})$. $\sqcap$$\sqcup$

B.6 Proof of Claim 3.8

Let $s_{u}$ be the strategy of player $u$ in $S$. We use the definition of the partial potential, the definitions of the potential for the original game and the subgame among the players in ${\cal N}\setminus\{u\}$, Lemma B.1d, and the definition of $\hat{c}_{u}(S)$ to obtain

B.7 Proof of Claim 3.9

The first equality follows by the definition of the $A$-partial potential, the second one follows by Claim 3.7 since each player in ${\cal N}\setminus A$ uses the same strategy in $S$ and $S^{\prime}$ and the last one follows by Theorem 3.2. $\sqcap$$\sqcup$

B.8 Proof of Lemma 3.10

Let $A=\{u_{1},u_{2},...,u_{|A|}\}$. Let $A_{0}=\emptyset$ and $A_{t}=\{u_{1},...,u_{t}\}$ for $t=1,2,...,|A|$. Then, using the definition of the partial potential and Claims 3.6 and 3.8, we have

B.9 Proof of Lemma 3.12

Let $S^{*}$ be the state of minimum potential and $S$ be a $\rho$-approximate equilibrium. For each player $u$, we denote by $s_{u}$ and $s^{*}_{u}$ the strategies she plays at states $S$ and $S^{*}$, respectively. Using the $\rho$-approximate equilibrium condition $c_{u}(S)\leq\rho\cdot c_{u}(S_{-u},s^{*}_{u})$, the definition of the cost of player $u$, and the definition of function $\Psi_{1}$, we obtain

By summing over all players, by exchanging sums, and using the definition of $N_{e}(S^{*})$, we obtain

We now apply the inequality $xy\leq\frac{\sqrt{5}-1}{2(3-\sqrt{5})}y^{2}+\frac{\sqrt{5}-2}{3-\sqrt{5}}x^{2}$ that holds for any pair of non-negative $x$ and $y$ on the rightmost part of the above derivation to obtain

Now, observe that $\Psi_{1}(N_{e}(S^{*}))^{2}\geq\sum_{u:e\in s^{*}_{u}}{w^{2}_{u}}$ for every resource $e$. Furthermore, $\Psi_{1}(N_{e}(S^{*}))^{2}+\sum_{u:e\in s^{*}_{u}}{w^{2}_{u}}=\Psi_{2}(N_{e}(S^{*}))$. Hence, we have

We now use the definition of $\Phi(S)$, the fact that for every player $u$ and resource $e\in s_{u}$, it holds that $w_{u}\leq\Psi_{1}(N_{e}(S))$, and the definition of the cost of player $u$. We have

By applying inequality (1) to the rightmost part of this derivation, we obtain

The last inequality implies that $\Phi(S)$ is not larger than $\frac{(5-\sqrt{5})\rho}{2(1-(2\sqrt{5}-4)\rho)}\Phi(S^{*})$ which can be easily proved to be at most $\left(\frac{3+\sqrt{5}}{2}+6(\rho-1)\right)\Phi(S^{*})$ when $\rho\in[1,11/10]$. $\sqcap$$\sqcup$

B.10 Proof of Lemma 3.13

Consider a $\rho$-approximate equilibrium $S$ of a $\Psi$-game and let $S^{*}$ be the state of minimum potential. We denote by $s_{u}$ and $s^{*}_{u}$ the strategy of player $u$ at states $S$ and $S^{*}$, respectively.

By Lemma 3.10, the $\rho$-approximate equilibrium condition $\hat{c}_{u}(S)\leq\rho\cdot\hat{c}_{u}(S_{-u},s^{*}_{u})$, and the definition of the potential function, we have

We now use the fact that $N_{e}(S_{-u},s^{*}_{u})\subseteq N_{e}(S)\cup\{w_{u}\}$, Lemma B.1c, and the fact that $\Psi_{t+1}(N_{e}(S^{*}))\geq(t+1)!\sum_{u:e\in s^{*}_{u}}{w^{t+1}_{u}}$ to obtain

Using Lemma B.1b (observe that it implies that $\Psi_{t}(A)\leq\Psi_{k+1}(A)^{\frac{t}{k+1}}$ for any non-negative integer $t\leq k+1$ and multi-set of reals $A$), the binomial theorem, inequality $\alpha^{\lambda}+\beta^{\lambda}\leq(\alpha+\beta)^{\lambda}$ for every $\alpha,\beta\geq 0$ and $\lambda\geq 1$, and the definition of the potential function, we obtain

We now apply Minkowski inequality twice on the double sum at the rightmost part of this last inequality and use the definition of the potential function to obtain

By Claim A.2, we have $(1+1/\rho)^{\frac{1}{d+1}}-1\geq\left(\rho^{\frac{1}{d+1}}(\rho+1)^{\frac{d}{d+1}}(d+1)\right)^{-1}$. Using this observation, inequality (4) implies that

B.11 Proof of Lemma 3.14

for every two multi-sets of positive reals $A$ and $B$. To see why (7) holds, observe that the product $\Psi_{k-t}(A)\Psi_{t}(B)$ equals $(k-t)!t!$ times the sum of all products of monomials of degree $k-t$ with elements of $A$ with monomials of degree $t$ with elements of $B$.

Given state $S$ in the original game, we define the $\Psi$-game $\left(R,(w_{u})_{u\in R},(\Sigma_{u})_{u\in R},(\bar{a}_{e,t})_{e\in E,t=0,...,d}\right)$ with

Observe that the parameters $\bar{a}_{e,k}$ depend only on the strategies of players in ${\cal N}\setminus R$ in $S$.

Now, given any state $S^{\prime}$ in the original game, we denote by $\bar{S}^{\prime}$ the state in the new game in which each player in $R$ uses the strategy she uses in $S^{\prime}$. We also use the notation $\bar{c}_{u}$ for the cost of a player $u\in R$ in the new game and $\bar{\Phi}$ for its potential function.

We will first show that $\bar{c}_{u}(\bar{S}^{\prime})=\hat{c}_{u}(S^{\prime})$ for every state $\bar{S}^{\prime}$ of the new game such that each player $u\in{\cal N}\setminus R$ uses the same strategy in $S^{\prime}$ and $S$. Consequently, since state $S$ is a $\rho$-approximate equilibrium for the players in $R$ in the original game, state $\bar{S}$ is a $\rho$-approximate equilibrium in the new game. We have

The first equality follows by the definition of $\bar{c}_{u}(\bar{S}^{\prime})$, the second one follows since $N_{e}(\bar{S}^{\prime})=N^{R}_{e}(S^{\prime})$ and by the definition of $\bar{a}_{e,k}$, the third one follows by exchanging the sums and since each player in ${\cal N}\setminus R$ use the same strategy in states $S$ and $S^{\prime}$ (hence, $N_{e}^{{\cal N}\setminus R}(S)=N_{e}^{{\cal N}\setminus R}(S^{\prime})$), the fourth one follows by equality (7), and the last one follows by the definition of $\hat{c}_{u}(S^{\prime})$.

We now show that $\bar{\Phi}(\bar{S}^{\prime})=\Phi_{R}(S^{\prime})$. We have

The first equality follows by the definition of $\bar{\Phi}(\bar{S}^{\prime})$, the second one follows since $N_{e}(\bar{S}^{\prime})=N^{R}_{e}(S^{\prime})$ and by the definition of $\bar{a}_{e,k}$, the third one follows by exchanging the sums and since each player in ${\cal N}\setminus R$ use the same strategy in states $S$ and $S^{\prime}$, the fourth one follows by simply changing the counter in the rightmost sum, the fifth one is obvious, the sixth one follows by property (7), and the last two ones follow by the definition of the (partial) potentials.

Since the state $\bar{S}$ is a $\rho$-approximate equilibrium for the new game, the bounds on the $\rho$-stretch established in Lemmas 3.12 and 3.13 imply that $\bar{\Phi}(\bar{S})\leq\theta_{d}(\rho)\bar{\Phi}(\bar{S}^{*})$. By our last equality above, we obtain that $\Phi_{R}(S)\leq\theta_{d}(\rho)\Phi_{R}(S^{*})$ and the proof is complete. $\sqcap$$\sqcup$

Appendix C Omitted proofs from Section 4

In order to prove the key property maintained by our algorithm, we will need the following lemma which relates the $R_{i}$-partial potential to the cost they experience when they make their last move within phase $i$.

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

Proof. Rename the players in $R_{i}$ as $u_{1},u_{2},...,u_{|R_{i}|}$ so that $u_{j}$ is the $j$-th player that performed her last move within phase $i\geq 1$. Also, denote by $S^{i,j}$ the state in which player $u_{j}$ performed her last move. Let $R^{|R_{i}|}_{i}=\emptyset$ and $R^{j}_{i}=\{u_{j+1},u_{j+2}...,u_{|R_{i}|}\}$ for $j=0,1,2,...,|R_{i}|-1$. Then,

The first three inequalities follow by the definition of the partial potential functions and the definition of sets $R_{i}^{j}$. The fourth inequality follows by Claim 3.7 since players in ${\cal N}\setminus R^{j}_{i}$ do not move after state $S^{i,j}$ and until the end of the phase. The inequality follows by Claim 3.6 and the last equality follows by Claim 3.8 and the definition of $\hat{c}(u)$. $\sqcap$$\sqcup$

We now proceed to the proof of Lemma 4.3. For the sake of contradiction, we assume that $\Phi_{R_{i}}(S^{i-1})>\gamma^{-1}nb_{i}$ and we denote by $P_{i}$ and $Q_{i}$ the set of players in $R_{i}$ whose last move was a $p$-move and $q$-move, respectively. Since each player in $P_{i}$ decreases her cost by at least $(p-1)\hat{c}(u)$ during her last move within phase $i$ (see Claim 3.9), we have

By Lemma C.1 and the fact that each player in $Q_{i}$ experiences a cost of at most $b_{i}$ when she makes her last move within phase $i$, we have

Using the last two inequalities and our assumption, we obtain that

Now, consider state $S^{i-1}$ and let $X_{i}$ and $Y_{i}$ be the sets of players in $R_{i}$ with cost at least $b_{i}$ and smaller than $b_{i}$, respectively. Notice that, by the definition of phase $i-1$, $S^{i-1}$ is a $q$-approximate equilibrium for the players in $X_{i}$. We construct a new $\Psi$-game of degree $d$ among the players in $\cal N$ as follows. The new game has all resources of the original game; the parameters $a_{e,k}$ for these resources are the same as in the original game. In addition, the new game has a new resource $e_{u}$ for each player $u\in Y_{i}$; the parameters for this resource are $a_{e_{u},0}=b_{i}/w_{u}$ and $a_{e_{u},k}=0$ for $k=1,...,d$. Each player in ${\cal N}\setminus Y_{i}$ has the same set of strategies in the two games. The strategy set of player $u\in Y_{i}$ consists of the strategy $s_{u}$ she uses in $S^{i-1}$ as well as strategy $s^{\prime}_{u}\cup\{e_{u}\}$ for each strategy $s^{\prime}_{u}\not=s_{u}$ she has in the original game.