Computing approximate Nash equilibria in network congestion games with polynomially decreasing cost functions

Abstract

We consider the problem of computing approximate Nash equilibria in monotone congestion games (a class of games generalizing network congestion games) with polynomially decreasing cost functions. In particular, we consider the case in which each resource j has a cost $c_j$ and the cost that each player incurs when using j is given by $c_j/x^{\beta }$ for some constant ${\beta }>0$, where x is the number of players using j. Observe that, for ${\beta }=1$, we obtain the fundamental Shapley cost sharing method. We design a parametric distributed algorithm for computing ${\alpha }$-approximate Nash equilibria. The complexity of this algorithm depends on ${\alpha }$, being polynomial for ${\alpha }=\varOmega (p^{\beta })$, for every fixed ${\beta }>0$, with p being the number of players. Our algorithm provides the first non-trivial approximability results for this class of games and achieves an almost tight performance for network games in directed graphs. For the case of ring networks, we show that an approximate equilibrium can be polynomially computed for every fixed ${\alpha } >1$. On the negative side, we prove that the problem of computing a Nash equilibrium in Shapley network cost sharing games is PLS-complete even in undirected graphs, where previous hardness results where known only in the directed case.

1 Introduction

In the last years, with the advent of the Internet, considerable research interest has been devoted to modeling and analyzing behavioral dynamics in non-cooperative networks, where selfish users compete for limited resources. One of the most natural and investigated frameworks in this setting is that of the congestion games introduced by Rosenthal [24], in which the set of the strategies of each player corresponds to some collection of subsets of a given set of common resources (when the set of resources is given by the set of edges of a graph, we speak of network congestion games). The cost of a strategy is the sum of the costs of the selected resources, where the cost of each single resource depends on its congestion, i.e., the number of players using it.

These games are particularly suited to model selfish routing in unregulated networks as well as the phenomenon of spontaneous network formation. In the former case, the cost of each resource is assumed to increase with its congestion, whereas in the latter the cost decreases. Rosenthal proved that each congestion game admits an exact potential function, that is, a real-valued function on the set of all possible strategy profiles such that the difference in the potential between two strategy profiles that differ in the strategic choice of a single player is equal to the difference of the costs experienced by this player in the two profiles. This implies that each congestion game has a pure Nash equilibrium [22] (from now on, simply, Nash equilibrium), that is a strategy profile in which no player can decrease her cost by unilaterally deviating to a different strategy. Moreover, it also follows that a Nash equilibrium can always be reached by the so called Nash dynamics, that is, the iterative process in which, at each step, an unsatisfied player is allowed to switch to a better strategy, i.e. lowering her cost.

Monderer and Shapley [21] proved that the class of congestion games and the one of exact potential games are equivalent. Questions related to the performance of Nash equilibria, such as the price of anarchy [17] and price of stability [3], have been extensively addressed in the context of congestion games and some of their variations. The complexity of computing Nash equilibria is another topic extensively studied in the context of algorithmic game theory, with respect both to mixed [15] and to pure strategies [11]. In this paper, we focus on the problem of computing (approximate) Nash equilibria in a variant of congestion games, that we call monotone congestion games, which includes the class of network congestion games.

1.1 Related work

The complexity of computing (approximate) Nash equilibria in (network) congestion games with increasing cost functions is fairly well-understood. Fabrikant et al. [11] prove that computing a Nash equilibrium is PLS-complete in both non-symmetric network games and general symmetric games (a game is symmetric if the players share the same set of strategies). Ackermann et al. [1] shows that PLS-completeness holds even for network games with linear cost functions. For the special case of symmetric network congestion games, instead, Fabrikant et al. [11] show how to efficiently compute a Nash equilibrium by solving a min-cost flow problem.

These impossibility results together with the fact that in many real-life applications it may be the case that a player incurs a cost for changing her strategy, have naturally led researchers to consider the notion of approximate Nash equilibria. An ${\alpha }$-approximate Nash equilibrium, for some ${\alpha }\ge 1$, is a strategy profile in which no player can improve her payoff by a multiplicative factor of at least ${\alpha }$ by unilaterally deviating to a different strategy. Skopalik and Vöcking [25] prove that computing an ${\alpha }$-approximate Nash equilibrium is PLS-complete for any polynomial time computable ${\alpha } \ge 1$. Moreover they also show that ${\alpha }$-approximate better-response dynamics can require an exponential number of steps to converge. This PLS-hardness result implies that any dynamics for reaching an approximate equilibrium that requires only polynomial-time computation per iteration does not always converge in a polynomial number of iterations, unless ${\mathsf{PLS}} \subseteq {\mathsf{P}}$.

On the positive side, Chien and Sinclair [10] show that, in symmetric games with positive delays, an ${\alpha }$-approximate Nash equilibrium can be reached after a polynomial number of steps of the Nash dynamics. Magniez et al. [19] extended the result of [10] to symmetric games with only negative delays, while they showed that the problem becomes PLS-complete if both positive and negative delays are present. Caragiannis et al. [6] provide a polynomial time algorithm that computes a $(2+\gamma )$-approximate Nash equilibrium (for arbitrary small $\gamma >0$) for games with linear cost functions and a $d^{O(d)}$-approximate Nash equilibrium for games with polynomial cost functions with constant maximum degree d. They [7] extend these results to weighted congestion games; finally, Caragiannis and Fanelli [5] show the existence of a d-approximate Nash equilibrium.

Much less is known about the complexity of computing (approximate) Nash equilibria in congestion games with decreasing cost functions. Indeed, there are results only for special cases of network games under the Shapley cost sharing method [3], i.e., games in which each resource has a cost which is equally split among all the players using it. Specifically, given a graph each player i wants to connect a pair of nodes $(s_i,t_i)$. Syrgkanis [26] shows that computing a Nash equilibrium in these games is PLS-complete if the underlying graph is directed. Moreover, he provides an analogous PLS-completeness result in undirected graphs for suitably decreasing cost sharing functions not including Shapley. Albers and Lenzner [2] consider the case in which the graph is undirected and $s_i=s$ for each player i and prove that any optimal network (i.e., a minimum cost Steiner tree whose set of terminals is given by the union of the source-destination nodes of all the players) is an $H_p$-approximate Nash equilibrium, where p is the number of players.

We stress that the algorithm proposed by Caragiannis et al. [6, 7] cannot be extended to deal with decreasing cost functions since it strongly exploits the following facts (here, linear functions are considered, but a similar discussion can be made for polynomial functions): (i) if, given a game, some players are frozen on some strategies, the resulting game is a congestion game with less players and different cost functions, but always belonging to the class of linear cost functions; (ii) the potential value of an ${\alpha }$-approximate Nash equilibrium approximates the minimum of the potential function by a factor of order ${\alpha }$. It can be easily verified that neither property (i) nor property (ii) hold in congestion games with decreasing cost functions. Thus, there exists a tremendous theoretical gap regarding the computability of (approximate) Nash equilibria in network games under the Shapley cost sharing method. In fact, on the one hand, the only positive result, holding for undirected graphs, is the $H_p$ approximation of [2], that can be computed in polynomial time only in the broadcast case in which there is a player for each (destination) node except s; on the other hand, the only negative result is that, in directed networks, no pure Nash equilibria can be computed in polynomial time [26].

In this paper we explicitly consider also ring networks. In fact, they have an important role and are frequently considered in the context of communication networks, as they are the simplest non-acyclic topology to be analyzed and can be considered as a first step for coping with more involved topologies. Studies on the performance of Nash equilibria of congestion games for ring topologies can be found in [9, 12, 20].

1.2 Our contribution

Our aim is to address the class of network congestion games with polynomially decreasing cost functions. Since network games have the property that, whenever a given strategy (subset of edges) s fulfills the connectivity requirement of a player, then any superset $s'\supset s$ with redundant edges also does, we introduce the general class of the monotone congestion games (see Definition 1), that properly includes that of network congestion games. In these games, the strategy set of each player is closed under resource addition. Roughly speaking, in monotone games, a player can always add any subset of resources to those that already form a feasible solution for her. We remark that this feature, while indifferent for plain Nash equilibria, as no strategy at equilibrium will contain redundant resources, can be profitably exploited in order to compute low factor approximate Nash equilibria.

Building upon this observation, we consider the complexity of computing (approximate) Nash equilibria in monotone congestion games with polynomially decreasing cost functions, providing both positive and negative results. In particular, we consider the case in which each resource j has a cost $c_j$ and the cost that each player incurs when using j is given by $c_j/x^{\beta }$ for some constant ${\beta }>0$, where x is the number of players using j. Observe that, for ${\beta }=1$, we obtain the Shapley cost sharing method, so that our model widely generalizes the models previously studied in the literature.

On the positive side, we design a distributed algorithm that computes an approximate Nash equilibrium with provable performance guarantee. In particular, assuming that a $\rho$-approximate best-response for the game can be computed in time t, for a fixed parameter $\gamma \in \left( 1,\frac{rp}{\rho }\right)$, our algorithm returns a $\gamma (p^{-1}+\rho )$-approximate Nash equilibrium in time $t\cdot (rp)^{O\left( \frac{{\beta }\log p}{\log \gamma }\right) }$, where r is the number of resources and p the number of players. The computational complexity of the algorithm heavily depends on the choice of $\gamma$: when $\gamma \in O(1)$, the complexity is quasi-polynomial, while when $\gamma \in \varOmega (p^{1+\epsilon })$, for a fixed constant $\epsilon >0$, it becomes polynomial.

It is worth noticing that the provided algorithm could be implemented by exploiting the setting of distributed shared memory (e.g., see Chapter 12 of [18]), in which well known algorithms as the Berkeley Algorithm can be used in order to guarantee mutual exclusion and bounded waiting. Moreover, global variables can be easily handled in the critical sections in order to store the current state of the game.

Our algorithm provides the first non-trivial approximability results for this class of games and achieves an almost tight performance for network games in directed graphs, as described in detail in Sect. 4, where we also prove a stronger result for the case of ring networks, e.g., that an ${\alpha }$-approximate Nash equilibrium can be polynomially computed even for any fixed ${\alpha } >1$ and without exploiting the monotonicity property.

On the negative side, we prove that the problem of computing a Nash equilibrium in network games under the Shapley cost sharing method is PLS-complete even for undirected graphs, thus closing a long standing open question which had been answered before by Syrgkanis [26] only for the case of directed graphs.

1.3 Paper organization

The remainder of this paper is organized as follows. In the next section we formalize the model and give the basic notation and definitions. In Sect. 3 we provide the main positive result of the paper: an algorithm computing an approximate Nash equilibrium. Section 4 discusses the application of this algorithm to network congestion games, and also proves that a Nash equilibrium can be more efficiently computed in the case of ring networks. Section 5 shows that, under the Shapley cost sharing method, the problem of computing a Nash equilibrium is PLS-complete. Finally, Sect. 6 gives some conclusive remarks and outlines some interesting open questions.

2 Model

A congestion game with polynomially decreasing latency functions is a tuple $(P,R,({{{\mathcal {S}}}}_i)_{i\in P},(c_j)_{j\in R},{\beta })$, where P is a set of p players, R a set of r resources, ${{{\mathcal {S}}}}_i\subseteq 2^R\setminus \{\emptyset \}$ is the set of strategies of player $i\in P$, $c_j>0$ is the cost of resource $j\in R$ and ${\beta }>0$ is a real value. A strategy profile ${{{\varvec{\sigma }}}}=(\sigma _1,\ldots ,\sigma _p)$ is the outcome in which each player $i\in P$ chooses strategy $\sigma _i\in {{{\mathcal {S}}}}_i$. The cost that player i experiences in strategy profile ${{\varvec{\sigma }}}$ is defined as $cost_i({{{\varvec{\sigma }}}})=\sum _{j\in \sigma _i}\frac{c_j}{p_j({{{\varvec{\sigma }}}})^{\beta }}$, where $p_j({{{\varvec{\sigma }}}})=|\{i\in P:j\in \sigma _{i}\}|$ denotes the number of players using resource j in ${{\varvec{\sigma }}}$.

Given a strategy profile ${{\varvec{\sigma }}}$, a player $i\in P$ and a strategy $S\in {{{\mathcal {S}}}}_i$, we denote with ${{{\varvec{\sigma }}}}_{-i}\diamond S$ the strategy profile obtained from ${{\varvec{\sigma }}}$ when i switches from strategy $\sigma _i$ to strategy S. A strategy profile ${{\varvec{\sigma }}}$ is a (pure-strategy) Nash equilibrium if, for each $i\in P$ and $S\in {{{\mathcal {S}}}}_i$, $cost_i({{{\varvec{\sigma }}}})\le cost_i({{{\varvec{\sigma }}}}_{-i}\diamond S)$, that is, no player can lower her cost by unilaterally switching to a different strategy. More generally, given a value ${\alpha }\ge 1$, ${{\varvec{\sigma }}}$ is an ${\alpha }$-approximate Nash equilibrium if, for each $i\in P$ and $S\in {{{\mathcal {S}}}}_i$, $cost_i({{{\varvec{\sigma }}}})\le {\alpha }\cdot cost_i({{{\varvec{\sigma }}}}_{-i}\diamond S)$, that is, no player can lower her cost of a factor of more than ${\alpha }$ by unilaterally switching to a different strategy. Clearly, a Nash equilibrium is an ${\alpha }$-approximate Nash equilibrium with ${\alpha }=1$.

For a fixed strategy profile ${{\varvec{\sigma }}}$ and a player $i\in P$, a best-response for i in ${{\varvec{\sigma }}}$ is a strategy $br_i({{{\varvec{\sigma }}}})\in {{{\mathcal {S}}}}_i$ such that $cost_i({{{\varvec{\sigma }}}}_{-i}\diamond br_i({{{\varvec{\sigma }}}}))=\min _{S\in \mathcal{S}_i}\{cost_i({{{\varvec{\sigma }}}}_{-i}\diamond S)\}$. A strategy $S\in \mathcal{S}_i$ is an ${\alpha }$-approximate best-response for i in ${{\varvec{\sigma }}}$ if $cost_i({{{\varvec{\sigma }}}}_{-i}\diamond S)\le {\alpha }\cdot cost_i({{{\varvec{\sigma }}}}_{-i}\diamond br_i({{{\varvec{\sigma }}}}))$. It follows that ${{\varvec{\sigma }}}$ is an ${\alpha }$-approximate Nash equilibrium if and only if each player $i\in P$ is playing an ${\alpha }$-approximate best-response. Given a game ${{\mathcal {G}}}$, we denote with $\varPi _{br}(\mathcal{G})$ the problem of computing a best-response for a generic player $i\in P$ in a generic strategy profile ${{\varvec{\sigma }}}$ of ${{\mathcal {G}}}$. As we will see, there are games for which such a problem is in $\mathsf P$ and others for which it is ${\mathsf{NP}}$-hard.

Let $\varPhi :\times _{i \in P}{{{\mathcal {S}}}}_i\rightarrow {\mathbb {R}}_+$ be the function such that $\varPhi ({{\varvec{\sigma }}})=\sum _{j\in R}\sum _{i=1}^{p_j({{\varvec{\sigma }}})}\frac{c_j}{i^{\beta }}.$ Function $\varPhi$, originally defined by Rosenthal [24] for the general class of the congestion games, is an exact potential function, that is $\varPhi ({{\varvec{\sigma }}}_{-i}\diamond S)-\varPhi ({{\varvec{\sigma }}})=cost_i({{\varvec{\sigma }}}_{-i}\diamond S)-cost_i({{\varvec{\sigma }}})$ for each strategy profile ${{\varvec{\sigma }}}$ and strategy $S\in {{{\mathcal {S}}}}_i$.

Definition 1

We say that a congestion game is monotone if, for each player $i\in P$, the set of strategies ${{{\mathcal {S}}}}_i$ is closed under resource addition, that is, for each $S\in {{{\mathcal {S}}}}_i$ and $R'\subseteq R$, it holds that $S\cup R'\in {{{\mathcal {S}}}}_i$.

Given two strategies $S,S'\in {{{\mathcal {S}}}}_i$, we say that $S'$ is dominated by S if $S\subset S'$. Note that, by definition, no player ever plays a dominated strategy in a Nash equilibrium and no best response is a dominated strategy, whereas, for suitable values of ${\alpha }$, this cannot be a priori excluded in an ${\alpha }$-approximate Nash equilibrium. Moreover, it is worth noticing that, since no best response is a dominated strategy, if the problem of computing a best response is NP-hard for a given (non-monotone) congestion game ${{\mathcal {G}}}$, it is NP-hard also for the “corresponding” monotone congestion game ${{\mathcal {G}}}'$ having the same set of players and resources and such that, for each player i, the set of non-dominated strategies of i in ${{\mathcal {G}}}'$ is equal to the set of strategies of i in ${{\mathcal {G}}}$. Notice also that, for a monotone congestion game, it is sufficient to provide, for each player, the set of non-dominated strategies in order to fully describe the game.

An interesting and well-studied class of monotone congestion games is represented by network congestion games. In these games, the set of resources is represented by the set of edges of a weighted graph $G=(V,E,c)$ (thus $|E|=r$), where $|V|=n$, which may be either directed or undirected, and the set of strategies for each player is defined in implicit form as follows: each player $i\in P$ is associated with a set of $k_i$ subsets of nodes $V_{ij} \subseteq V$ for $j=1,\ldots ,k_i$ that she wishes to serve in some way (for instance, by providing them a connection, a fault-tolerant connection, a point-to-point connection, etc). Note that differently from classical congestion game, here the representation of the game does not keep the whole set of strategies explicitly. Several interesting subcases, all of them assuming $k_i=1$ for any $i\in P$, have been considered so far in the literature, such as multi-source games in which $|V_{i1}|=|V_i|=2$ for each $i\in P$, multicast games in which, in addition, $V_i\cap V_{i'}=\{s\}$ for each $i,i'\in P$ and broadcast games in which, as a further restriction, one has $\bigcup _{i\in P}V_i=V$. Finally, Shapley games are congestion games with polynomially decreasing latency functions in which ${\beta }=1$. Note that, differently from congestion games in which the strategies are given explicitly in the instance, $\varPi _{br}({{{\mathcal {G}}}})$ is NP-hard for several network congestion games ${{\mathcal {G}}}$, even restricting to the case in which $k_i=1$ for any $i\in P$; in particular, computing a best response is NP-hard for a player i for which $|V_{i1}|=|V_i|>2$ (by a trivial reduction from the Steiner Tree problem), while it is in P for multi-source games (by a trivial reduction to the shortest path problem). See Sect. 4 for further details.

3 The approximation algorithm

Fix a monotone congestion game with polynomially decreasing latency functions ${{\mathcal {G}}}$. Throughout this section we assume, without loss of generality, that ${{\mathcal {G}}}$ is normalized in such a way that $c_j\ge 1$ for each $j\in R$.

In the approximation algorithm we are going to provide, we need to compute, as a subroutine, best responses; since $\varPi _{br}({{{\mathcal {G}}}})$ may be NP-hard, we assume that each player $i\in P$ can compute a $\rho$-approximate best-response (with $\rho \ge 1$), denoted with ${\widetilde{br}}_i({{{\varvec{\sigma }}}})$, by using an algorithm of time complexity (depending on the game ${{\mathcal {G}}}$) $t:=t({{{\mathcal {G}}}})$.

For any set of resources $R'\subseteq R$, define $c(R')=\sum _{j\in R'}c_j$ and, for each player $i\in P$, let $\mathsf{S}^*_i=\text {argmin}_{S\in \mathcal{S}_i}\left\{ c(S)\right\}$ be the minimum cost strategy for player i. Finally, let $c_{max}=\max _{j\in R}\{c_j\}$. For a fixed parameter $\gamma \in \left( 1,\frac{rp}{\rho }\right)$, set $\varDelta =\frac{r p^{{\beta }+1}}{\gamma }$. Since both $\gamma >1$ and $\varDelta >1$, it follows that $\log _{\gamma }x=O(\log x)$ and $\log _{\varDelta }x=O(\log x)$ for each $x\in {\mathbb {R}}$.

Definition 2

For any $\ell \ge 0$, a player i belongs to class $cl^P_{\ell }$ (or is of class $cl^P_{\ell }$) if $c(\mathsf{S}^*_i)\in (\varDelta ^{\ell -1},\varDelta ^{\ell }]$, while a resource j belongs to class $cl^R_{\ell }$ if $c_j\in (\varDelta ^{\ell -1},\varDelta ^{\ell }]$.

Note that the maximum player class is $L=\lceil \log _{\varDelta }(r\cdot c_{max})\rceil =O(\log r + \log c_{max})$ which is polynomial in the size of ${{\mathcal {G}}}$. We denote by $p_{\ell }=|cl^P_{\ell }|$ the number of players of class $cl^P_{\ell }$, by ${\overline{p}}_{\ell }=\sum _{\ell '=\ell +3}^L p_{\ell '}$ the number of players of class at least $\ell +3$ and set $P_{\ell }=\sum _{\ell '=\ell -2}^{\ell +2}p_{\ell '}$, where we use the convention $p_{-2}=p_{-1}=p_{L+1}=p_{L+2}=0$.

Our approximation algorithm is based on the following idea: the strategy $\sigma _i$ chosen by each player $i\in P$ is composed of two parts: a fixed strategy, denoted as ${\mathsf{FS}}_i$, which is independent of what the other players do and is kept fixed throughout the whole execution of the algorithm, and a variable strategy, denoted as ${\mathsf{VS}}_i$, which may change over time and expresses the player’s reaction to the choices of the others.

For a player $i \in cl^P_{\ell }$, let cl(i) denote the index of the player class containing i, i.e., $cl(i)=\ell$. Similarly, for a resource $j\in cl^R_{\ell }$, let cl(j) denote the index of the resource class containing j, i.e., $cl(j)=\ell$. The fixed strategy of each player $i\in P$ is defined as follows:

$$\begin{aligned} {\mathsf{FS}}_i = \left\{ \begin{array}{ll} \emptyset &{}\quad \text { if }\,cl(i)\in \{0,1\},\\ \bigcup \nolimits _{\ell =0}^{cl(i)-2}cl^R_{\ell } &{}\quad \text { if }\,cl(i)\ge 2. \end{array}\right. \end{aligned}$$

The set of variable strategies available to player $i\in P$ is

$$\begin{aligned} {{\mathcal {VS}}}_i=\{S\subseteq R\ |\ \exists S'\in {{{\mathcal {S}}}}_i:S=S'\setminus {\mathsf{FS}}_i\}. \end{aligned}$$

Notice that additional resources belonging to no non-dominated strategy can be present both in the fixed strategy ${\mathsf{FS}}_i$ (in particular the ones whose class is at most $cl(i)-2$) and in a variable strategy ${\mathsf{VS}}_i \in {{\mathcal {VS}}}_i$ of player i (the ones whose class is grater than $cl(i)-2$). We denote with ${\mathsf{VS}}^*_i=\text {argmin}_{S\in {{\mathcal {VS}}}_i}\{c(S)\}$ the minimum cost variable strategy for player i. For the sake of brevity, when given a strategy profile ${{\varvec{\sigma }}}$ with $\sigma _i={\mathsf{FS}}_i\cup {\mathsf{VS}}_i$ for each player $i\in P$ (with ${\mathsf{VS}}_i \in \mathcal{VS}_i$), we denote with $cost_i^{var}({{{\varvec{\sigma }}}})=\sum _{j \in \sigma _i \setminus {\mathsf{FS}}_i} \frac{c_j}{p_j({{\varvec{\sigma }}})^{\beta }}$ the cost experienced by player i in ${{\varvec{\sigma }}}$ due to resources belonging to her variable strategy only.

The following theorem bounds the performance of Algorithm 1 as a function of ${{\mathcal {G}}}$, $\rho$, t and $\gamma$.

Theorem 1

For each $\gamma \in \left( 1,\frac{rp}{\rho }\right)$, Algorithm 1 returns a $\gamma (p^{-1}+\rho )$-approximate Nash equilibrium in time $t\cdot (rp)^{O\left( \frac{{\beta }\log p}{\log \gamma }\right) }$.

Proof

For a strategy profile ${{\varvec{\sigma }}}$ and a player $i\in P$, denote with ${\mathsf{VS}}_i(\sigma ) \in \mathcal{VS}_i$ the variable strategy adopted by player i in ${{\varvec{\sigma }}}$. We start by proving some useful facts. The first one says that, during the execution of the algorithm, a resource of class $\ell$ may belong to the variable strategies of players of class $\ell -1$, $\ell$ or $\ell +1$ only.

Fact 1

Fix a resource $j\in cl^R_{\ell }$ and a strategy profile ${{{\varvec{\sigma }}}}^h$ generated during the execution of Algorithm 1. Then, for any player i such that $j\in {\mathsf{VS}}_i({{{\varvec{\sigma }}}}^h)$, $cl(i)\in \{\ell -1,\ell ,\ell +1\}$.

Proof

For a fixed resource $j\in cl^R_{\ell }$, let us assume, by way of contradiction, that there exist a strategy profile ${{{\varvec{\sigma }}}}^h$ generated during the execution of Algorithm 1 and a player i such that $j\in {\mathsf{VS}}_i({{{\varvec{\sigma }}}}^h)$, for which $cl(i)\notin \{\ell -1,\ell ,\ell +1\}$.

Consider first the case in which $cl(i)>\ell +1$. This implies that $cl^R_{\ell }\subseteq {\mathsf{FS}}_i$ which contradicts the hypothesis that $j\in {\mathsf{VS}}_i({{{\varvec{\sigma }}}}^h)$.

Then consider the case in which $cl(i)<\ell -1$. This implies that $c({\mathsf{S}}^*_i)\le \varDelta ^{\ell -2}$ so that, by construction of ${{{\varvec{\sigma }}}}^0$ and because resource j of class $\ell$ has a cost greater than $\varDelta ^{\ell -1}$, it has to be $h>0$. Moreover, since j can be shared by at most p (i.e., all) players, $cost_i^{var}({{\varvec{\sigma }}}^h) > \frac{\varDelta ^{\ell -1}}{p^{\beta }}$. On the one hand, by line 7 of the algorithm, we have $j\in \widetilde{br_i}({{{\varvec{\sigma }}}}^{h-1})$; on the other hand, since $\gamma <\frac{rp}{\rho }$, $cost_i(\sigma ^{h-1}_{-i} \diamond \widetilde{br_i}({{{\varvec{\sigma }}}}^{h-1}))\ge cost^{var}_i({{{\varvec{\sigma }}}}^{h})>\frac{\varDelta ^{\ell -1}}{p^{\beta }}>\rho \varDelta ^{\ell -2}\ge \rho \cdot c({\mathsf{S}}^*_i)$, thus contradicting the fact that $\widetilde{br_i}({{{\varvec{\sigma }}}}^{h-1})$ is a $\rho$-approximate best-response for player i. $\square$

The second fact says that, during the execution of the algorithm, a resource belonging to any variable strategy of a player of class $\ell$ may belong to the variable strategies of players of class $\ell -2$, $\ell -1$, $\ell$, $\ell +1$ or $\ell +2$ only.

Fact 2

Fix a strategy profile ${{{\varvec{\sigma }}}}^h$ generated during the execution of Algorithm 1, a player $i\in cl^P_{\ell }$ and a resource $j\in {\mathsf{VS}}_i({{{\varvec{\sigma }}}}^h)$. Then, for any player $i'$ such that $j\in {\mathsf{VS}}_{i'}({{{\varvec{\sigma }}}}^h)$, $cl(i')\in \{\ell -2,\ell -1,\ell ,\ell +1,\ell +2\}$.

Proof

By applying twice Fact 1, we first obtain that $cl(j)\in \{\ell -1,\ell ,\ell +1\}$ and then that $cl(i')\in \{\ell -2,\ell -1,\ell ,\ell +1,\ell +2\}$.$\square$

We now partition the set of player classes into two subsets: light and heavy classes. Both of them will be proved to have different properties that can be suitably exploited in order to show the correctness and the running time of our algorithm.

Definition 3

A player class $cl^P_{\ell }$ is light if ${\overline{p}}_{\ell }\ge \frac{{\overline{p}}_{\ell }+P_{\ell }}{\gamma ^{1/{\beta }}}$, otherwise it is heavy.

The good property of a light class $cl^P_\ell$ is that the ${\overline{p}}_{\ell }$ players (whose fixed strategies contain all the resources that may belong to the variable strategy of any player $i\in cl^P_{\ell }$) are enough to guarantee that during the execution of the algorithm no player $i\in cl^P_{\ell }$ ever performs a deviation; so that $\sigma ^h_i={\mathsf{FS}}_i\cup {\mathsf{VS}}^*_i$ for each strategy profile ${{{\varvec{\sigma }}}}^h$ generated during the execution of the algorithm. Let us denote with ${\widetilde{P}}$ the set of players who are selected at least once at step 5 of Algorithm 1 for updating their strategy.

Fact 3

For each player $i\in {\widetilde{P}}$, player class $cl^P_{cl(i)}$ is heavy.

Proof

Assume, for the sake of contradiction, that there exists a player $i\in {\widetilde{P}}$ such that $cl^P_{cl(i)}$ is light. Let ${{{\varvec{\sigma }}}}^h$ be strategy profile at which i performs her first deviation from strategy ${\mathsf{FS}}_i \cup {\mathsf{VS}}^*_i$. By line 5 of the algorithm, it must be

$$\begin{aligned} cost_i^{var}({{{\varvec{\sigma }}}}^h)>\gamma \cdot cost^{var}_i({{{\varvec{\sigma }}}}^h_{-i}\diamond (\widetilde{br_i}({{{\varvec{\sigma }}}}^h) \cup {\mathsf{FS}}_i)). \end{aligned}$$

(1)

By $\sigma ^h_i={\mathsf{FS}}_i \cup {\mathsf{VS}}^*_i$, we have

$$\begin{aligned} cost_i^{var}({{{\varvec{\sigma }}}}^h)\le \frac{c({\mathsf{VS}}^*_i)}{{\overline{p}}_{cl(i)}^{\beta }}, \end{aligned}$$

(2)

while, by the minimality of ${\mathsf{VS}}^*_i$ and Fact 2, we get

$$\begin{aligned}&cost^{var}_i({{{\varvec{\sigma }}}}^h_{-i}\diamond (\widetilde{br_i}({{{\varvec{\sigma }}}}^h)\cup {\mathsf{FS}}_i))\nonumber \\&\quad \ge \frac{c({\mathsf{VS}}^*_i)}{({\overline{p}}_{cl(i)}+P_{cl(i)})^{\beta }}. \end{aligned}$$

(3)

By using (2) and (3) in (1), we obtain

$$\begin{aligned} \frac{c({\mathsf{VS}}^*_i)}{{\overline{p}}_{cl(i)}^{\beta }}>\frac{\gamma c({\mathsf{VS}}^*_i)}{({\overline{p}}_{cl(i)}+P_{cl(i)})^{\beta }}, \end{aligned}$$

which, after rearranging, yields $\gamma {\overline{p}}_{cl(i)}^{\beta }<({\overline{p}}_{cl(i)}+P_{cl(i)})^{\beta }$ thus contradicting the assumption that $cl^P_{cl(i)}$ is light.$\square$

By Fact 3, we know that only players belonging to heavy classes are involved in the dynamics generated by lines 5–9 of Algorithm 1. Our next task is to bound the number of deviations in this dynamics. To this aim, we first bound the number of heavy classes. The peculiar property of a heavy class $cl^P_{\ell }$ is that $P_{\ell }$, that is the number of players belonging to classes going from $cl^P_{\ell -2}$ to $cl^P_{\ell +2}$, is a significant fraction of the ${\overline{p}}_{\ell +3}$ players belonging to the classes of index at least $\ell +3$, so that the total number of heavy classes remains bounded as a function of p, $\gamma$ and ${\beta }$ as follows.

Lemma 1

The number of heavy classes is at most $5 \left\lceil \frac{{\beta }\log p}{\log \gamma }\right\rceil$.

Proof

A pseudo-sequence of heavy classes is an ordered sequence $\langle cl^P_{\ell _1},\ldots ,cl^P_{\ell _k}\rangle$ of heavy classes whose mutual distance is at least five, that is, such that $\ell _{i+1}-\ell _{i}\ge 5$ for each $1\le i<k$. Clearly, denoted with $k^*$ the length of the longest pseudo-sequence of heavy classes, it immediately follows that the total numer of heavy classes is at most $5k^*$. Thus, in the remaining of the proof, we show that $k^*\le \left\lceil \frac{{\beta }\log p}{\log \gamma }\right\rceil$. Before bounding $k^*$, we need to introduce some useful facts.

Fact 4

Fix a pseudo-sequence of heavy classes $\langle cl^P_{\ell _1},\ldots ,cl^P_{\ell _k}\rangle$. For each $1\le i<k$, ${\overline{p}}_{\ell _i}+P_{\ell _i}\le {\overline{p}}_{\ell _{i-1}}$.

Proof

By definition, we have ${\overline{p}}_{\ell _{i-1}}=\sum _{j=\ell _{i-1}+3}^L cl^P_j$ and

$$\begin{aligned} {\overline{p}}_{\ell _i}+P_{\ell _i}=\sum _{j=\ell _i+3}^L cl^P_j+\sum _{j=\ell _i-2}^{\ell _i+2}cl^P_j=\sum _{j=\ell _i-2}^L cl^P_j. \end{aligned}$$

The claim then follows since $\ell _i-\ell _{i-1}\ge 5$ implies that $\ell _{i-1}+3\le \ell _i-2$. $\square$

Fact 5

Fix a pseudo-sequence of heavy classes $\langle cl^P_{\ell _1},\ldots ,cl^P_{\ell _k}\rangle$. For each $1\le i\le k$, ${\overline{p}}_{\ell _i} < \frac{p}{\gamma ^{i/{\beta }}}$.

Proof

The proof is by induction on i. As a base case, we have ${\overline{p}}_{\ell _1} < \frac{{\overline{p}}_{\ell _1}+P_{\ell _1}}{\gamma ^{1/{\beta }}}\le \frac{p}{\gamma ^{1/{\beta }}}$, where the first inequality follows from the definition of heavy classes. For $i>1$, we have ${\overline{p}}_{\ell _i}< \frac{{\overline{p}}_{\ell _i}+P_{\ell _i}}{\gamma ^{1/{\beta }}}<\frac{{\overline{p}}_{\ell _{i-1}}}{\gamma ^{1/{\beta }}}< \frac{p}{\gamma ^{i/{\beta }}}$, where the first inequality follows from the definition of heavy classes, the second one follows from Fact 4 and the last one follows from the inductive hypothesis. $\square$

We can now conclude the proof of the lemma. Because of Fact 5, we have that ${\overline{p}}_{\ell _{k^*}} < \frac{p}{\gamma ^{k^*/{\beta }}}$. Assume that $k^* > \lceil \log _{\root {\beta } \of {\gamma }}p \rceil$. Since $k^*$ is an integer, we get ${\overline{p}}_{\ell _{k^*-1}}<1$, i.e., ${\overline{p}}_{\ell _{k^*-1}}=0$. This means that all player classes with index at least $\ell _{k^*-1}+3$ are empty. Since $\ell _{k^*} \ge \ell _{k^*-1}+5$, it holds that $P_{\ell _{k^*}}=0$ and therefore, by Definition 3, class $\ell _{k^*}$ is light, thus rising a contradiction. Hence it must be $k^*\le \lceil \log _{\root {\beta } \of {\gamma }}p\rceil =\left\lceil \frac{{\beta }\log p}{\log \gamma }\right\rceil$. $\square$

We now proceed by grouping heavy and light classes into zones according to the following definition.

Definition 4

A zone z is a maximal set of contiguous player classes, starting and ending with a heavy class and such that no two contiguous classes are both light.

By Lemma 1 and the definition of zones, we have that there exist at most $5 \left\lceil \frac{{\beta }\log p}{\log \gamma }\right\rceil$ zones (because each zone has to contain at least a heavy class) and that each zone contains at most $10 \left\lceil \frac{{\beta }\log p}{\log \gamma }\right\rceil$ classes (because in the worst-case heavy and light classes are interleaved in a zone, given that two light classes cannot be contiguous). Moreover, again by the definition of zones and by Fact 2, it follows that, for any two players i and $i'$ such that $cl^P_{cl(i)}$ and $cl^P_{cl(i')}$ are two heavy classes belonging to two different zones, $S\cap S'=\emptyset$ for each $S\in \mathcal{VS}_i$ and $S'\in \mathcal{VS}_{i'}$, that is, the congestion of the resources belonging to the variable strategies of the players in a certain zone are not influenced by the choices of the players outside the zone, so that the Nash dynamics inside each zone, generated by Algorithm 1, is an independent process.

Consider a zone z starting at class $\ell$ and containing x classes (from class $\ell$ to class $\ell + x-1$). After line 3 of Algorithm 1, the total contribution to the potential $\varPhi ({{\varvec{\sigma }}}^0)$ of the resources that may be involved in the dynamics of the players belonging to classes in z is $r \varDelta ^{\ell +x} p$, because, by Fact 1, any variable strategy of a player of class $\ell + x-1$ can contain resources of classes $\ell + x-2$, $\ell + x-1$ and $\ell + x$. Since each deviation decreases the potential by at least $\frac{\varDelta ^\ell }{p^{\beta }} \left( 1- \frac{1}{\gamma }\right)$, at most $\frac{ r \varDelta ^{\ell +x} p}{\frac{\varDelta ^\ell }{p^{\beta }} \left( 1- \frac{1}{\gamma }\right) }= \frac{r \gamma \varDelta ^x p^{1+{\beta }}}{\gamma -1}$ deviations can be performed by the players belonging to classes in z. Thus, since $x \le 10 \left\lceil \frac{{\beta }\log p}{\log \gamma }\right\rceil$, $\gamma \in \left( 1,\frac{rp}{\rho }\right)$ and each deviation requires time at most t, we have that Algorithm 1 terminates in time $t\cdot (rp)^{O\left( \frac{{\beta }\log p}{\log \gamma }\right) }$.

It remains to show that it returns a $\gamma (p^{-1}+\rho )$-approximate Nash equilibrium. By the condition at line 5, we know that, with respect to the variable strategies, all players are in $\gamma \rho$-equilibrium in the strategy profile ${{\varvec{\sigma }}}$ returned by Algorithm 1. Moreover, for any player i of class $\ell$, the cost due to the resources in ${\mathsf{FS}}_i$ can be upper bounded by $r \varDelta ^{\ell -2}$. Since a best response for player i has to cost at least $\frac{\varDelta ^{\ell -1}}{p^{\beta }}$ (in the most optimistic case the minimum cost strategy ${\mathsf{S}}^*_i$ is shared by all players), by recalling the definition of $\varDelta$, we have that

$$\begin{aligned} r \varDelta ^{\ell -2} \le \frac{\gamma }{p}\cdot \frac{\varDelta ^{\ell -1}}{p^{\beta }}. \end{aligned}$$

(4)

Therefore,

$$\begin{aligned} cost_i({{\varvec{\sigma }}})= & {} \sum _{j \in \sigma _i \cap {\mathsf{FS}}_i} \frac{c_j}{p_j({{\varvec{\sigma }}})^{\beta }} + \sum _{j \in \sigma _i \setminus {\mathsf{FS}}_i} \frac{c_j}{p_j({{\varvec{\sigma }}})^{\beta }}\nonumber \\\le & {} r \varDelta ^{\ell -2} + \sum _{j \in \sigma _i \setminus {\mathsf{FS}}_i} \frac{c_j}{p_j({{\varvec{\sigma }}})^{\beta }} \nonumber \\\le & {} \frac{\gamma }{p}\cdot \frac{\varDelta ^{\ell -1}}{p^{\beta }} \\&+\, \gamma \rho \cdot cost_i^{var}({{{\varvec{\sigma }}}}_{-i}\diamond (br_i({{{\varvec{\sigma }}}}) \cup {\mathsf{FS}}_i))\nonumber \\\le & {} \frac{\gamma }{p}\cdot cost_i({{{\varvec{\sigma }}}}_{-i}\diamond br_i({{{\varvec{\sigma }}}}) ) \nonumber \\&+ \gamma \rho \cdot cost_i({{{\varvec{\sigma }}}}_{-i}\diamond br_i({{{\varvec{\sigma }}}}) )\nonumber \\= & {} \gamma (p^{-1}+\rho ) cost_i({{{\varvec{\sigma }}}}_{-i}\diamond br_i({{{\varvec{\sigma }}}})),\nonumber \end{aligned}$$

(5)

where (5) follows from (4) and from line 5 of Algorithm 1. $\square$

4 Applications to network congestion games

In this section, we discuss the application of our approximation algorithm to network congestion games with polynomially decreasing latency functions. We recall that for these games no positive results have been achieved so far in the literature, except the ones provided by Albers and Lenzner [2] for some Shapley games on undirected graphs. In particular, they show that, for multicast games, a minimum cost network is a $H_p$-approximate Nash equilibrium. Here, a minimum cost network coincides with a minimum Steiner tree, whose computation is an NP-hard problem and the authors do not discuss whether an approximation of the minimum cost network can still provide an approximate Nash equilibrium with provably good performance guarantee. Thus, if we drift apart from merely existential results to focus on practical (i.e., efficiently computable) ones, we have that an $H_p$-approximate Nash equilibrium can be computed only in the case of broadcast Shapley games on undirected graphs.

First of all, notice that, when a player aims at connecting three or more nodes, the computation of a best response corresponds to the one of a minimum Steiner tree, that is an NP-hard problem. We observe that, given a network congestion game ${{\mathcal {G}}}$ defined over a graph G, if there exists an algorithm computing a $\rho (G)$-approximate Nash equilibrium for ${{\mathcal {G}}}$ within time t(G), then the same algorithm can be used to approximate $\varPi _{br}({{{\mathcal {G}}}})$ within a factor of $\rho (G)$ with the same running time. To this aim, fix a graph G and a problem $\varPi$ on G and define ${{\mathcal {G}}}$ in such a way that there is a unique player whose set of strategies is given by all the feasible solutions of problem $\varPi$. Clearly, a $\rho (G)$-approximate Nash equilibrium for ${{\mathcal {G}}}$ computed in time at most t(G) provides also a $\rho (G)$-approximate solution to $\varPi$ in time at most t(G). Moreover, it is worth noticing that a similar result can be obtained for games with an arbitrary number p of players, by simply adding $p-1$ dummy players whose available strategies have all cost zero and involve edges not belonging to E(G): such players cannot share any edge with the first player in any ${\alpha }$-approximate Nash equilibrium. It follows that, if we denote by $\rho ^t_{LB}(\varPi )$ and $\rho ^t_{KN}(\varPi )$ the lower bound on the approximability of problem $\varPi$ and the performance guarantee of the best-known approximation algorithm for $\varPi$, respectively, when considering a time constraint t, each algorithm having a time complexity at most t cannot compute an approximate Nash equilibrium for game ${{\mathcal {G}}}$ with performance guarantee better than $\rho ^t_{LB}(\varPi _{br}(\mathcal G))$ and that, given the current state-of-the-art, it is unlikely to design an algorithm of time complexity at most t computing an approximate Nash equilibrium for game ${{\mathcal {G}}}$ with performance guarantee better than $\rho ^t_{KN}(\varPi _{br}({{\mathcal {G}}}))$.

As an example, consider the family of games $\mathcal{FG}$ in which each player wants to connect a subset of nodes of a directed graph G. Since an easy reduction from the set cover problem shows that it is hard to approximate the directed Steiner tree within a factor better than $O(\log n)$ [13], we obtain that, unless $NP \subseteq DTIME[n^{\log \log n}]$, it is hard to compute an $O(\log n)$-approximate Nash equilibrium for each $\mathcal{G}\in \mathcal{FG}$. Moreover, since the best-known approximation guarantee for the directed Steiner tree problem is $O(\log ^2 n)$ in quasi-polynomial time and $O(n^\epsilon )$, for any given $\epsilon >0$, in polynomial time [8], an algorithm computing an approximate Nash equilibrium for each ${{{\mathcal {G}}}}\in \mathcal{FG}$ achieving the same asymptotical performance guarantees within the same time constraints have to be considered fully satisfactory.

Now consider the application of our algorithm to a network congestion game ${{\mathcal {G}}}$. If we want an equilibrium with considerably good performance guarantee, we can run Algorithm 1 with $\gamma =1+\epsilon '$, for an arbitrarily small $\epsilon '>0$, to obtain a $(1+\epsilon '+o(1))\rho ^t_{KN}(\varPi _{br}({{\mathcal {G}}}))$-approximate Nash equilibrium in quasi-polynomial time (provided that also t is a quasi-polynomial function). For instance, if we consider a game ${{{\mathcal {G}}}}\in \mathcal{FG}$, we achieve an $O(\log ^2 n)$-approximate Nash equilibrium. Conversely, if one wants efficiently computable solutions, by setting $\gamma = p^{\epsilon ''}$, for any constant $\epsilon ''>0$, it is possible to obtain an $O(p^{\epsilon ''}) \rho ^t_{KN}(\varPi _{br}({{\mathcal {G}}}))$-approximate Nash equilibrium in polynomial time (provided that also t is a polynomial function). Again, for any game ${{{\mathcal {G}}}}\in \mathcal{FG}$, we achieve an $O(p^{\epsilon ''} n^{\epsilon })$-approximate Nash equilibrium. If n and p are polynomially related, by properly setting $\epsilon$ and $\epsilon ''$, our algorithm provides an $O(p^{\epsilon ''} n^{\epsilon })=O(n^{\epsilon '''})$-approximate Nash equilibrium for any $\epsilon '''>0$, meaning that in polynomial time it is possible to match the performance of the best known approximation algorithm for the directed Steiner tree problem.

With similar arguments, it is possible to show that, if $\rho ^t_{KN}(\varPi _{br}({{{\mathcal {G}}}}))=O(n^c)$ where $c>0$ is a constant and t is a polynomial function, our algorithm computes an $O(n^{c + \epsilon ''})$-approximate Nash equilibrium in polynomial time and, by the above discussion, this means that we are almost optimal (with respect to the best-known approximation ratio). For instance, this situation happens when considering games ${{\mathcal {G}}}$ such that $\varPi _{br}({{{\mathcal {G}}}})$ coincides with the problem of computing the minimum directed steiner forest [14], or the maximum clique.

4.1 Ring networks

In this section, we consider the network multi-source congestion game defined on an undirected ring (i.e., a graph with n nodes $v_1, \ldots , v_{n}$ and n edges $\{v_1,v_2\}, \ldots , \{v_{n-1},v_n\}, \{v_n,v_1\}$). In this setting, as usual in the literature (see [9, 12]), we assume that each player aims at connecting two nodes of the ring network.

In fact, for this topology, we are able to prove a stronger result on the computation of approximate Nash equilibria, even not exploiting the monotonicity property of the game.

Theorem 2

In the class of multi-source Shapley games played on an undirected ring, every sequence of at most $\frac{p^{O({\beta })}}{{\alpha }-1}$ ${\alpha }$-approximate best responses leads to an ${\alpha }$-Nash equilibrium.

Proof

Consider a ring network (V, E, c) with $V=v_1, \ldots , v_{n}$ and $E=\{v_1,v_2\}, \ldots , \{v_{n-1},v_n\}, \{v_n,v_1\}$. Recall that $R=E$, and let $W=c(R)=\sum _{j \in R} c_j$ the total cost of the ring. Every player $i \in P$, aiming at connecting two nodes of V, has two strategies (whose union is R): the minimum cost strategy ${\mathsf{S}}^*_i$ of cost $c({\mathsf{S}}^*_i)$ and the opposite strategy of cost $W-c({\mathsf{S}}^*_i)$.

For every player $i \in P$ such that

$$\begin{aligned} c({\mathsf{S}}^*_i) \le \frac{W-c({\mathsf{S}}^*_i)}{p^{\beta }} , \end{aligned}$$

player i performs at most one ${\alpha }$-approximate best response because she will never deviate from strategy ${\mathsf{S}}^*_i$, for any ${\alpha }\ge 1$ (even if she shares the cost of the opposite strategy with all players, her cost does not decrease).

Therefore, we can focus on the number of ${\alpha }$-approximate best responses performed by players $i \in P' \subseteq P$ such that $c({\mathsf{S}}^*_i) > \frac{W}{p^{\beta }+1}$.

The maximum value that Rosenthal’s potential can reach is $W \cdot H_p$ (where $H_p$ is the p-th harmonic number), and every ${\alpha }$-approximate best response of a player in $i \in P'$ decreases the potential by at least

$$\begin{aligned} \frac{c({\mathsf{S}}^*_i) }{p^{\beta }} \left( 1 - \frac{1}{{\alpha }} \right) > \frac{W ({\alpha }-1)}{{\alpha } p^{\beta }(p^{\beta }+1)}. \end{aligned}$$

Thus, since $H_p < 1 + \ln p$ for any $p\ge 1$, the number of ${\alpha }$-approximate best responses that players in $P'$ can perform is at most

$$\begin{aligned} \frac{ W H_p }{ \frac{W ({\alpha }-1)}{{\alpha } p^{\beta }(p^{\beta }+1)} } < \frac{ {\alpha } p^{\beta }(p^{\beta }+1 ) (1+\ln p) }{ {\alpha }-1 } \le \frac{p^{O({\beta })}}{{\alpha }-1}. \end{aligned}$$

$\square$

5 Hardness of computing a Nash equilibrium in multi-source shapley games on undirected graphs

The existence of a potential function for congestion games allows us to cast searching for a Nash equilibrium as a local search problem. The states, that is the strategy profiles of the players, are the feasible solutions, and the neighborhood of a state consists of all authorized changes in the strategy of a single player. Then local optima correspond to states where no player can improve individually her cost, that is exactly to Nash equilibria. The potential of a state can be evaluated in polynomial time, and similarly a neighboring state of lower potential can be exhibited, provided that there exists one. This means that the problem of computing a Nash equilibrium in a congestion game belongs to the complexity class PLS (Polynomial Local Search) defined in [16, 23].

Syrgkanis [26] proved that computing a Nash equilibrium in multi-source Shapley games played on directed graphs is a PLS-complete problem. Syrgkanis’s proof works as follows: starting from an instance $G=(V,E,w)$ of the MAX CUT problem under the flip neighborhood, he constructs a (non-network) Shapley game ${{\mathcal {G}}}$ with $n=|V|$ players and exactly two strategies, namely $s^A_i$ and $s^B_i$, for each player $i\in [n]$ such that, given a Nash equilibrium for ${{\mathcal {G}}}$, it is possible to construct in polynomial time a local maximum for the MAX CUT problem defined by G. Then, starting from ${{\mathcal {G}}}$, a multi-source Shapley game $\hat{{{\mathcal {G}}}}$ played by n players on a directed network is constructed with the property that the set of strategies that each player $i\in [n]$ can eventually adopt in any Nash equilibrium (i.e., non-dominated strategies) is restricted to at most two strategies that simulate strategies $s^A_i$ and $s^B_i$ in ${{\mathcal {G}}}$, so that there is a natural one-to-one correspondence between Nash equilibria of $\hat{{{\mathcal {G}}}}$ and Nash equilibria of ${{\mathcal {G}}}$.

Syrgkanis also shows how to suitably extend $\hat{{{\mathcal {G}}}}$ to a multi-source game $\widetilde{{{\mathcal {G}}}}$ played on an undirected network guaranteeing again a one-to-one correspondence between Nash equilibria of $\widetilde{{{\mathcal {G}}}}$ and Nash equilibria of $\hat{{{\mathcal {G}}}}$. Anyway, in order to achieve this last step, he needs to impose latency functions of the form $\frac{c_e(x)}{x}$ (where $c_e(x)$ is a non-decreasing concave function) on some edges of the graph defining $\widetilde{{{\mathcal {G}}}}$, so that his reduction does not apply to the Shapley cost sharing method.

We show that the problem of computing a Nash equilibrium in multi-source Shapley games played on undirected graphs (and, in particular even on sparse graphs) remains PLS-complete by elaborating on Syrgkanis’s proof as follows: starting from ${{\mathcal {G}}}$, we directly construct a multi-source Shapley game $\widetilde{{{\mathcal {G}}}}$ played on an undirected sparse graph, where we add a significant number of dummy players (but still polynomial in the size of the MAX CUT instance G) allowing us to restrict the choice of each of the non-dummy players $i\in [n]$ at any Nash equilibrium to only at most two strategies, so as to simulate again strategies $s^A_i$ and $s^B_i$ in ${{\mathcal {G}}}$.

Theorem 3

The problem of computing a Nash equilibrium in the class of multi-source Shapley games played on undirected sparse graph is PLS-complete.

Proof

Consider an instance of the MAX CUT problem defined by the weighted graph $G=(V,E,w)$ with $|V|=n\ge 2$ and assume that $\{i,j\}\notin E\Rightarrow w_{ij}=0$. Moreover, denote $W=\max _{i,j\in [n]:i<j}\{w_{ij}\}$. An example of an instance with $n=4$ nodes is depicted in Fig. 1.

Fig. 1

An instance of the MAX CUT problem defined by a weighted graph G with $n=4$ nodes

Define the Shapley game ${\mathcal {G}}=([n],R,({{{\mathcal {S}}}}_i)_{i\in [n]},(c_r)_{r\in R})$ such that

• there is a player $i\in [n]$ for each node $i\in V(G)$,

• there are two resources $r^0_{ij},r^1_{ij}\in R$ for each $i,j\in [n]$, with $i<j$, such that $c_{r^k_{ij}}=2w_{ij}$ for each $k\in \{0,1\}$,

• each player $i\in [n]$ has two strategies

  $$\begin{aligned} s_i^A=\{r^1_{ji}:j\in [i-1]\}\cup \{r^0_{ij}:j\in [n]\setminus [i]\} \end{aligned}$$

  and

  $$\begin{aligned} s_i^B=\{r^0_{ji}:j\in [i-1]\}\cup \{r^1_{ij}:j\in [n]\setminus [i]\}, \end{aligned}$$

  so that each strategy consists of exactly $n-1$ resources.

The Shapley game defined by the MAX CUT problem depicted in Fig. 1 is shown in Fig. 2.

Fig. 2

A Shapley game induced by a MAX CUT problem defined on a four-node graph

Syrgkanis shows [26] (Theorem 5) that, given a pure Nash equilibrium ${{\varvec{\sigma }}}$ for ${{\mathcal {G}}}$, one can construct in polynomial time a local maximum of the MAX CUT problem on instance G. We repeat the argument here for the sake of completeness. A strategy profile ${{\varvec{\sigma }}}$ for ${{\mathcal {G}}}$ is mapped to a cut $(A({{{\varvec{\sigma }}}}),B({{{\varvec{\sigma }}}})=V\setminus A({{{\varvec{\sigma }}}}))$ for G as follows: $i\in A({{{\varvec{\sigma }}}})$ if and only if $\sigma _i=s_i^A$. Clearly, $(A({{{\varvec{\sigma }}}}),B({{{\varvec{\sigma }}}}))$ can be computed in polynomial time. From the definition of the players’ strategies, it follows that two players $i,j\in [n]$, with $i<j$, share a resource $r^k_{ij}$ in ${{\varvec{\sigma }}}$ if and only if i and j choose opposite strategies (i.e., either $\sigma _i=s_i^A$ and $\sigma _j=s_j^B$ in which case they share $r_{ij}^0$ or $\sigma _i=s_i^B$ and $\sigma _j=s_j^A$ in which case they share $r_{ij}^1$). Thus, it follows that

$$\begin{aligned}&cost_i\left( {{{\varvec{\sigma }}}}_{-i}\diamond s_i^A\right) \\&\quad = \sum _{j<i:\sigma _j=s_j^A}2w_{ji}+\sum _{j<i:\sigma _j=s_j^B}w_{ji}\\&\qquad +\sum _{j>i:\sigma _j=s_j^A}2w_{ij}+\sum _{j>i:\sigma _j=s_j^B}w_{ij}\\&\quad = \sum _{j<i}w_{ji}+\sum _{j>i}w_{ij}+\sum _{j<i:j\in A({{{\varvec{\sigma }}}})}w_{ji}+\sum _{j>i:j\in A({{{\varvec{\sigma }}}})}w_{ij} \end{aligned}$$

and

$$\begin{aligned}&cost_i\left( {{{\varvec{\sigma }}}}_{-i}\diamond s_i^B\right) \\&\quad = \sum _{j<i:\sigma _j=s_j^B}2w_{ji}+\sum _{j<i:\sigma _j=s_j^A}w_{ji}\\&\qquad +\sum _{j>i:\sigma _j=s_j^B}2w_{ij}+\sum _{j>i:\sigma _j=s_j^A}w_{ij}\\&\quad = \sum _{j<i}w_{ji}+\sum _{j>i}w_{ij}+\sum _{j<i:j\in B({{{\varvec{\sigma }}}})}w_{ji}+\sum _{j>i:j\in B({{{\varvec{\sigma }}}})}w_{ij}. \end{aligned}$$

Now, assume that ${{\varvec{\sigma }}}$ is a pure Nash equilibrium for ${{\mathcal {G}}}$. If $\sigma _i=s_i^A$ which yields $i\in A({{{\varvec{\sigma }}}})$, then it must be $cost_i({{{\varvec{\sigma }}}}_{-i}\diamond s_i^A)\le cost_i({{{\varvec{\sigma }}}}_{-i}\diamond s_i^B)$ which yields $\sum _{j<i:j\in A({{{\varvec{\sigma }}}})}w_{ji}+\sum _{j>i:j\in A({{{\varvec{\sigma }}}})}w_{ij}\le \sum _{j<i:j\in B({{{\varvec{\sigma }}}})}w_{ji}+\sum _{j>i:j\in B({{{\varvec{\sigma }}}})}w_{ij}$. So, switching i from $A({{{\varvec{\sigma }}}})$ to $B({{{\varvec{\sigma }}}})$ does not increase the weight of the cut. A symmetric argument holds for the case of $\sigma _i=s_i^B$ and this shows that ${{\varvec{\sigma }}}$ yields a local maximum cut for G.

Throughout this proof, we call heavy-path a path made up of $n^4$ edges, each having weight equal to $Wn^4$, so that the total weight of a heavy-path is equal to $Wn^8$. Let us now consider the multi-source Shapley game $\widetilde{{{\mathcal {G}}}}$ played on an undirected network and constructed from ${{\mathcal {G}}}$ as follows. Let ${\widetilde{G}}=({\widetilde{V}},{\widetilde{E}})$ be the graph such that

• for each $i,j\in [n]$, with $i<j$, and $k\in \{0,1\}$, there is a pair of nodes in ${\widetilde{V}}$, labeled as ${\widetilde{u}}^k_{ij}$ and ${\widetilde{v}}^k_{ij}$; moreover, for each $i\in [n]$, ${\widetilde{V}}$ contains other n pairs of nodes, labeled as $s_i$ and $t_i$;

• node $s_1$ is connected to nodes ${\widetilde{u}}_{12}^0$ and ${\widetilde{u}}_{12}^1$, while, for each $i\in [n]\setminus \{1\}$, node $s_i$ is connected to nodes ${\widetilde{u}}_{1i}^0$ and ${\widetilde{u}}_{1i}^1$. Similarly, node $t_n$ is connected to nodes ${\widetilde{v}}_{(n-1)n}^0$ and ${\widetilde{v}}_{(n-1)n}^1$, while, for each $i\in [n-1]$, node $t_i$ is connected to nodes ${\widetilde{v}}_{in}^0$ and ${\widetilde{u}}_{in}^1$. All of the connections defined in this step are by means of a heavy-path;

• for each $i,j\in [n]$ with $i<j$ and for each $k\in \{0,1\}$, node ${\widetilde{u}}_{ij}^k$ is connected to node ${\widetilde{v}}_{ij}^k$ with an edge of weight $2w_{ij}$. We shall see later on that edge $\{{\widetilde{u}}_{ij}^k,{\widetilde{v}}_{ij}^k\}$ simulates resource $r_{ij}^k\in R({{{\mathcal {G}}}})$;

• for each $i\in [n-2]$, $1<j<n$ and $k\in \{0,1\}$, node ${\widetilde{v}}_{ij}^k$ is connected to node ${\widetilde{u}}_{i(j+1)}^k$ through a heavy-path;

• for each $i\in [n-2]$, $j\in [n-1]$ and $k\in \{0,1\}$, node ${\widetilde{v}}_{ij}^k$ is connected, through a heavy-path, to node ${\widetilde{u}}_{(i+1)j}^k$ if $j-i\ge 2$ and to node ${\widetilde{u}}_{(i+1)(j+1)}^{{\overline{k}}}$ otherwise, where ${\overline{k}}$ denotes the boolean negation of k.

Note that, by construction, the number of heavy-paths in ${\widetilde{G}}$ is $O(n^2)$. This implies that $|{\widetilde{V}}|=O(n^6)$ and $|{\widetilde{E}}|=O(n^6)$, so that ${\widetilde{G}}$ is a sparse graph whose size remains polynomial in that of G. We also observe that all edges in ${\widetilde{E}}$ have two possible weights, namely, $Wn^4$ and $2w_{ij}\le 2W$ for some $i,n\in [n]$. We call light edges the ones having weight at most 2W. The multi-source Shapley game induced by the Shapley game depicted in Fig. 2 is shown in Fig. 3.

Fig. 3

An example of graph ${{\widetilde{G}}}$ when $n=4$. Heavy paths are represented by thick lines

Game $\widetilde{{{\mathcal {G}}}}$ is obtained by considering a set [n] of n players such that each player $i\in [n]$ wants to connect the source-destination pair $(s_i,t_i)$. Moreover, for each non-light edge $e\in {\widetilde{E}}$, there are $n^3$ dummy players that want to connect the source-destination pair defined by its two endpoints. For each dummy player d associated with edge e, we say that e is the canonical strategy of d. Observe that the number of dummy players is $O(n^9)$ and so is also the total number of players in $\widetilde{{{\mathcal {G}}}}$. Hence, the size of $\widetilde{{{\mathcal {G}}}}$ remains polynomial in that of G.

We show the theorem by exploiting a sequence of lemmas stressing some suitable properties that need to be satisfied by any Nash equilibrium for $\widetilde{{{\mathcal {G}}}}$.

Lemma 2

In any Nash equilibrium for $\widetilde{{{\mathcal {G}}}}$, each dummy player adopts her canonical strategy.

Proof

Fix a Nash equilibrium $\widetilde{{{\varvec{\sigma }}}}$ for $\widetilde{{{\mathcal {G}}}}$ and assume, by way of contradiction, that there exists a dummy player d not using her canonical strategy e. Assume that e belongs to a heavy-path $\pi$. Let $\varDelta$ be the set of dummy players other than the ones associated with e, who are adopting a non-canonical strategy containing at least one edge of $\pi$. Observe that, by construction of graph ${\widetilde{G}}$ and the fact that $\widetilde{{{\varvec{\sigma }}}}$ is a Nash equilibrium for $\widetilde{{{\mathcal {G}}}}$, each player in $\varDelta$ has to use edge e also.

Thus, we obtain $cost_d(\widetilde{{{{\varvec{\sigma }}}}})\ge \frac{Wn^8-Wn^4}{2n^3+n+|\varDelta |}$, where the numerator comes from the fact that any non-canonical strategy for d has to cross the heavy-path $\pi$ except for edge e, and the denominator comes from the fact that the maximum number of players that may share their strategy with d is given by the n non-dummy players, the $|\varDelta |$ dummy players defined by set $\varDelta$, the $n^3$ dummy players associated with edge e and the $n^3$ dummy players associated with each edge of $\pi$ other than e when they are using their canonical strategy. On the other hand, we have $cost_d(\widetilde{{{{\varvec{\sigma }}}}}_{-d},x)\le \frac{Wn^4}{|\varDelta |+1}$.

By comparing $cost_d(\widetilde{{{{\varvec{\sigma }}}}})$ with $cost_d(\widetilde{{{{\varvec{\sigma }}}}}_{-d},x)$, we obtain

$$\begin{aligned}&\frac{Wn^8-Wn^4}{2n^3+n+|\varDelta |}-\frac{Wn^4}{|\varDelta |+1} \\&\quad = Wn^4\left( \frac{n^4-1}{2n^3+n+|\varDelta |}-\frac{1}{|\varDelta |+1}\right) \\&\quad = Wn^4\left( \frac{n^4(|\varDelta |+1)-2n^3-n-2|\varDelta |-1}{(2n^3+n+|\varDelta |) (|\varDelta |+1)}\right) \\&\quad > 0, \end{aligned}$$

which shows that player d lowers her cost by switching to her canonical strategy, thus contradicting the fact that $\widetilde{{{\varvec{\sigma }}}}$ is a Nash equilibrium for $\widetilde{{{\mathcal {G}}}}$.$\square$

Fig. 4

The canonical A-strategy of player i, denoted as ${\widetilde{s}}^A_i$

Now, we turn our attention to the non-dummy players. For each $i\in [n]$, the canonical A-strategy of player i, denoted as ${\widetilde{s}}^A_i$, is defined as shown in Fig. 4. Similarly, by replacing each superscript 0 with 1 and viceversa, one obtains the definition of the canonical B-strategy of each player $i\in [n]$.

Lemma 3

In any Nash equilibrium for $\widetilde{{{\mathcal {G}}}}$, each player $i\in [n]$ adopts one of her two canonical strategies.

Proof

Fix a Nash equilibrium $\widetilde{{{\varvec{\sigma }}}}$ for $\widetilde{{{\mathcal {G}}}}$ and assume, by way of contradiction, that there exists a player $i\in [n]$ such that ${\widetilde{\sigma }}_i\notin \{{\widetilde{s}}^A_i,{\widetilde{s}}^B_i\}$. Observe that any canonical strategy crosses exactly n heavy-paths and $n-1$ light edges, whereas any non-canonical strategy has to cross at least $n+1$ heavy-paths.

Thus, we obtain $cost_i(\widetilde{{{\varvec{\sigma }}}})\ge \frac{Wn^8(n+1)}{n^3+n}$, where the numerator comes from the fact that strategy ${\widetilde{\sigma }}_i$ has to cross at least $n+1$ heavy-paths and the denominator comes from the fact that any edge of a heavy-path is used by exactly $n^3$ dummy players (because of Lemma 2) and by at most all of the n non-dummy players. On the other hand, for each $s_i\in \{{\widetilde{s}}^A_i,{\widetilde{s}}^B_i\}$, we have $cost_i(\widetilde{{{\varvec{\sigma }}}}_{-i},s_i)\le \frac{Wn^9}{n^3+1}+2W(n-1)$, where the upper bound comes from the fact that any canonical strategy crosses exactly n heavy-paths and $n-1$ light edges together with Lemma 2 and the definition of W.

By comparing $cost_i(\widetilde{{{{\varvec{\sigma }}}}})$ with $cost_i(\widetilde{{{{\varvec{\sigma }}}}}_{-i},s_i)$, we obtain

$$\begin{aligned}&\frac{Wn^8(n+1)}{n^3+n}-\frac{Wn^9}{n^3+1}-2W(n-1)\\&\quad = W\left( \frac{n^8(n+1)}{n^3+n}-\frac{n^9}{n^3+1}-2n+2\right) \\&\quad = W\left( \frac{n^{10}-n^{9}+n^8+n^7-2n^6}{(n^2+1)(n^3+1)}\right. \\&\qquad +\,\left. \frac{2n^5-2n^4+2n^2-2n+2}{(n^2+1)(n^3+1)}\right) \\&\quad > 0, \end{aligned}$$

which shows that player i lowers her cost by switching to any of her two canonical strategies, thus contradicting the fact that $\widetilde{{{\varvec{\sigma }}}}$ is a Nash equilibrium for $\widetilde{\mathcal{G}}$.$\square$

We now conclude the proof of the theorem by showing that, given a Nash equilibrium $\widetilde{{{\varvec{\sigma }}}}$ for $\widetilde{{{\mathcal {G}}}}$, we can construct in polynomial time a Nash equilibrium ${{\varvec{\sigma }}}$ for ${{\mathcal {G}}}$. To this aim, for each $i\in [n]$, define the function $g_i$ such that

$$\begin{aligned} g_i(s) = \left\{ \begin{array}{ll} s_i^A &{}\quad \text { if }\,s ={\widetilde{s}}_i^A,\\ s_i^B &{}\quad \text { if }\,s ={\widetilde{s}}_i^B. \end{array}\right. \end{aligned}$$

Let $\widetilde{{{\varvec{\sigma }}}}=({\widetilde{\sigma }}_1,\ldots ,{\widetilde{\sigma }}_n)$ be a strategy profile for $\widetilde{{{\mathcal {G}}}}$ in which each player plays one of her two canonical strategies and consider the function g such that $g(\widetilde{{{\varvec{\sigma }}}})=(g_1({\widetilde{\sigma }}_1),\ldots ,g_n({\widetilde{\sigma }}_n))$. Function g naturally defines a bijection between the set of strategy profiles for $\widetilde{{{\mathcal {G}}}}$ in which each player plays one of her two canonical strategies and the set of strategy profiles for ${{\mathcal {G}}}$. Moreover, the careful construction of game $\widetilde{{{\mathcal {G}}}}$, guarantees that

$$\begin{aligned} cost_i(\widetilde{{{\varvec{\sigma }}}})=cost_i(g(\widetilde{{{\varvec{\sigma }}}}))+\frac{Wn^9}{n^3+1} \end{aligned}$$

(6)

for each $i\in [n]$. For instance, with respect to the games depicted in Figs. 2 and 3, consider the strategy profile $\widetilde{{{\varvec{\sigma }}}}=(s_1^A,s_2^B,s_3^B,s_4^A)$ for $\widetilde{{{\mathcal {G}}}}$. From the one hand, we have $cost_1(\widetilde{{{\varvec{\sigma }}}})=w_{12}+w_{13}+2w_{14}+\frac{W4^9}{4^3+1}$, $cost_2(\widetilde{{{\varvec{\sigma }}}})=w_{12}+2w_{23}+w_{24}+\frac{W4^9}{4^3+1}$, $cost_3(\widetilde{{{\varvec{\sigma }}}})=w_{13}+2w_{23}+w_{34}+\frac{W4^9}{4^3+1}$ and $cost_4(\widetilde{{{\varvec{\sigma }}}})=2w_{14}+w_{24}+w_{34}+\frac{W4^9}{4^3+1}$. On the other hand, we have $cost_1(g(\widetilde{{{\varvec{\sigma }}}}))=w_{12}+w_{13}+2w_{14}$, $cost_2(g(\widetilde{{{\varvec{\sigma }}}}))=w_{12}+2w_{23}+w_{24}$, $cost_3(g(\widetilde{{{\varvec{\sigma }}}}))=w_{13}+2w_{23}+w_{34}$ and $cost_4(g(\widetilde{{{\varvec{\sigma }}}}))=2w_{14}+w_{24}+w_{34}$ as claimed.

Since, by Lemma 3, we have that in a Nash equilibrium for $\widetilde{{{\mathcal {G}}}}$ each player plays one of her two canonical strategies, it follows that any Nash equilibrium $\widetilde{{{\varvec{\sigma }}}}$ for $\widetilde{{{\mathcal {G}}}}$ gets mapped to the strategy profile $g(\widetilde{{{\varvec{\sigma }}}})$ for ${{\mathcal {G}}}$. It remains to show that $g(\widetilde{{{\varvec{\sigma }}}})$ is a Nash equilibrium for ${{\mathcal {G}}}$.

Assume, by way of contradiction, that this is not the case and let i be a player who can lower her cost by deviating to strategy t, so that $cost_i(g(\widetilde{{{\varvec{\sigma }}}})_{-i},t)<cost_i(g(\widetilde{{{\varvec{\sigma }}}}))$. We obtain

$$\begin{aligned} cost_i(\widetilde{{{\varvec{\sigma }}}}_{-i},g^{-1}(t))= & {} cost_i(g(\widetilde{{{\varvec{\sigma }}}})_{-i},t)+\frac{Wn^9}{n^3+1}\\< & {} cost_i(g(\widetilde{{{\varvec{\sigma }}}}))+\frac{Wn^9}{n^3+1}\\= & {} cost_i(\widetilde{{{\varvec{\sigma }}}}), \end{aligned}$$

where the first equality follows from (6) together with the fact that $g(\widetilde{{{\varvec{\sigma }}}}_{-i},g^{-1}(t))=(g(\widetilde{{{\varvec{\sigma }}}})_{-i},t)$, the inequality follows from the assumption that $g(\widetilde{{{\varvec{\sigma }}}})$ is not a Nash equilibrium for ${{\mathcal {G}}}$, and the last equality follows again from (6). As the above derivation contradicts the assumption that $\widetilde{{{\varvec{\sigma }}}}$ is a Nash equilibrium for $\widetilde{{{\mathcal {G}}}}$, $g(\widetilde{{{\varvec{\sigma }}}})$ has to be a Nash equilibrium for ${{\mathcal {G}}}$ and this concludes the proof. $\square$

6 Conclusions

In this paper, we considered the problem of computing (approximate) Nash equilibria in monotone congestion games with polynomially decreasing cost functions.

Dealing with the case of games that are not monotone remains an intriguing open problem. For instance, in our algorithm we consider a particular dynamics exploiting the monotonicity of the game and involving approximated best responses. With respect to (pure or approximated) best response dynamics, an interesting open problem consists in understanding the relation between the time of convergence and the quality in terms of approximation of the reached equilibria.

While we showed that our results for monotone games are nearly optimal for directed networks, it is worth understanding whether or not better results can be proved for undirected networks.

Moreover, when the graph is an undirected ring, we showed how to compute in polynomial time ${\alpha }$-Nash equilibria, for any ${\alpha } >1$. It would be nice to understand whether the problem of finding a pure Nash equilibrium is efficiently solvable.

Finally, we believe that providing stronger results for other specific graph topologies, as for instance planar graphs, is another interesting and important issue.