Congestion games with mixed objectives

Abstract

We study a new class of games which generalizes congestion games and its bottleneck variant. We introduce congestion games with mixed objectives to model network scenarios in which players seek to optimize for latency and bandwidths alike. We characterize the (non-)existence of pure Nash equilibria (PNE), the convergence of improvement dynamics, the quality of equilibria and show the complexity of the decision problem. For games that do not possess PNE we give bounds on the approximation ratio of approximate pure Nash equilibria.

1 Introduction

Resource allocation problems in large-scale scenarios such as networks often cannot be solved as a single optimization problem. The size of the problem, the distributed nature of information, or control preclude a centralized approach. As a consequence, decisions are delegated to local actors or players. This gives rise to strategic behavior as these players often have economic interests. Game theory has studied the effect of such strategic interaction in various models of resource allocation and scheduling. One of the most prominent ones is the class of atomic congestion games (Rosenthal 1973), in which players choose sets of resources. The cost of a resource depends on the number of players allocating it. The cost of a player is the sum of the costs of her allocated resources. The appeal of this model stems not only from its applicability to prominent problems like scheduling, routing and load balancing, but also from desirable game theoretic properties. Congestion games always possess pure Nash equilibria and the natural improvement dynamics converge to a pure Nash equilibrium since these games are potential games. In fact, the class of congestion games is isomorphic to the class of potential games (Monderer and Shapley 1996), which shows their expressiveness. When modeling network routing with congestion games and most of its variants like weighted (Fotakis et al. 2005) or player-specific congestion games (Milchtaich 1996) one faces deficiency due to the nature of the players’ cost functions. As a player’s cost is determined by the sum of the resource costs, congestion games are not well suited to model effects like bandwidth allocation, as here the cost of a player is determined only by the bottleneck resource. Hence, Banner and Orda (2007) introduced bottleneck congestion games where the cost of a player is the maximum cost of her chosen resources. Again, due to the nature of the cost functions, this class of games and most of its variants (Harks et al. 2009, 2016) only model the bottleneck effects and are unable to describe latency effects. It is not difficult to envision scenarios in which both effects, latency and bandwidth, are relevant to decision makers - especially in today’s IT infrastructures where we find techniques with shared resources, for example in the context of cloud computing or in software-defined networking. Many users with lots of different applications and therefore different objectives interact in one network and compete for the same resources. Consider, for example, on the one hand media streaming and on the other hand video gaming. In one application, bandwidth is the most important property, in the other it is latency.

1.1 Our contribution

We study a game theoretic model in which players may have heterogeneous objectives. We introduce the model of congestion games with mixed objectives. In this model, resources have two types of costs, latency cost and bottleneck cost, where the latter corresponds to the inverse of bandwidth. The players’ costs may depend on both types of cost, where we allow different players to have different preferences regarding the two cost types. The convex combination of the two cost functions as the new objective is the simplest extension which contains both standard games and introduces new degrees of freedom to model more complex scenarios.

Table 1 Existence of pure Nash equilibria for different restricted classes

We give an almost complete characterization of the model of congestion games with mixed objectives. For different restrictions on the strategy sets (singleton, matroid and unrestricted games) and on the new properties of our model regarding the preferences values and the dependence of the two cost functions, we show the (non-)existence of pure Nash equilibria (see Table 1). We show that pure Nash equilibria exist and can be computed in polynomial time in singleton games and in some matroid games. However, we show that the matroid property alone is not sufficient for the existence. Additionally, it is necessary that either the players are only interested in latency or bottleneck cost, or that the cost functions have a monotone dependence. For the latter case, we show convergence of best-response dynamics while the remaining cases are only weakly acyclic. For matroid and unrestricted games that do not satisfy one of the additional properties, we show that pure equilibria might not exist and it is even NP-hard to decide whether one exists. This yields even for $\alpha$-uniform games, in which all players use the same constant in the linear combination of their costs. Additionally, we characterize the quality of the equilibria using the Price of Anarchy and the Price of Stability.

To overcome these non-existence results, we consider approximate pure Nash equilibria. For the general case we show that the existence is not guaranteed for approximation factors $\beta \le 3$ and we show that the decision problem whether they exist is NP-hard. On the positive side, we can show for several classes of games that there exist $\beta$-approximate pure Nash equilibria where $\beta$ depends on the size of the largest strategy (see Table 2). In the table, $\ell _r$ and $e_r$ represent both types of cost functions (latency respectively bottleneck costs) and g is the maximal degree of all cots functions.

Table 2 Approximation factors $\beta$ for different restricted classes depending on the size of the largest strategy d

1.2 Related work

Milchtaich (1996) studies the concept of player-specific congestion games and shows that in the singleton case these games always admit pure Nash equilibria. Ackermann et al. (2009) generalize these results to matroid strategy spaces and show that the result also holds for weighted congestion games. Furthermore, they point out that in a natural sense the matroid property is maximal for the guaranteed existence of pure Nash equilibria in player-specific and weighted congestion games. Moreover, Milchtaich (1996) examines congestion games in which players are both weighted and have player-specific cost functions. By constructing a game with three players, he shows that these games do not necessarily possess pure Nash equilibria, even in the case of singleton strategies.

Mavronicolas et al. (2007) study a special case of these games in which cost functions are not entirely player-specific. Instead, the player-specific resource costs are derived by combining the general resource cost function and a player-specific constant via a specified operation (e. g. addition or multiplication). They show that this restriction is sufficient to guarantee the existence of pure Nash equilibria in games with three players. Dunkel and Schulz (2008) show that the decision problem of whether a weighted network congestion game possesses a pure Nash equilibrium is NP-hard. The equivalent result is achieved for player-specific congestion games by Ackermann and Skopalik (2008).

Banner and Orda (2007) study the applicability of game-theoretic concepts in network routing scenarios. In particular, they derive bounds on the price of anarchy in network bottleneck congestion games with restricted cost functions and show that a pure Nash equilibrium which is socially optimal always exists. Cole et al. (2012) further investigate the non-atomic case, they especially consider the impacts of variable traffic rates. In contrast,  Harks et al. (2009) concentrate on the atomic case and study the lexicographical improvement property, which guarantees the existence of pure Nash equilibria through a potential function argument. They show that bottleneck congestion games fulfill this property and, hence, they are potential games. Harks et al. (2013) consider the complexity of computing pure Nash equilibria and strong equilibria in bottleneck congestion games. Moreover, they show this property in matroid bottleneck congestion games.

Chien and Sinclair (2011) study the convergence towards approximate pure Nash equilibria in symmetric congestion games. Skopalik and Vöcking (2008) show inapproximability in asymmetric congestion games, which is complemented by approximation algorithms for linear and polynomial delay functions (Caragiannis et al. 2011; Feldotto et al. 2014), even for weighted games (Caragiannis et al. 2015). Hansknecht et al. (2014) use the concept of approximate potential functions to examine of approximate pure Nash equilibria in weighted congestion games under different restrictions on the cost functions.

1.3 Preliminaries

A congestion game with mixed objectives is defined by a tuple $\Gamma = \left( N,R,\right.$ $\left. \left( \Sigma _i\right) _{i\in N}, \left( \alpha _i\right) _{i\in N},\left( \ell _r\right) _{r\in R}, \left( e_r\right) _{r\in R}\right)$, where $N=\left\{ 1,\dots , n\right\}$ denotes the set of players and R denotes the set of resources. For each player i let $\Sigma _i \subseteq 2^R$ denote the strategy space of player i and $\alpha _i\in \left[ 0,1\right]$ the preference value of player i. For each resource r let $\ell _r : N \rightarrow \mathbb {R}$ denote the non-decreasing latency cost function associated to resource r, and let $e_r : N \rightarrow \mathbb {R}$ denote the non-decreasing bottleneck cost function associated to resource r. For a state $S=\left( S_1,\dots , S_n\right) \in \mathbf {S} = \Sigma _1 \times \ldots \times \Sigma _n$, we define for each resource $r\in R$ by $n_r(S)=\left| \left\{ i\in N~|~r\in S_i\right\} \right|$ the congestion of r. The latency cost of r in state S is given by $\ell _r(S)=\ell _r(n_r(S))$, and the bottleneck cost by $e_r(S)=e_r(n_r(S))$. The total cost of player i in state S depends on $\alpha _i$ and is defined as $c_i(S)=\alpha _i\cdot \sum _{r\in S_i}\ell _r(S)+(1-\alpha _i)\cdot \max _{r\in S_i}e_r(S)$. The social cost of a state is given by $C(S) = \sum _{i \in N} c_i(S)$.

For a state $S=(S_1,...,S_i,..., S_n)$, we denote by $\left( S_{i}',S_{-i}\right)$ the state that is reached if player i plays strategy $S_i'$ while all other strategies remain unchanged. A state $S=\left( S_1,\dots , S_n\right)$ is called a pure Nash equilibrium (PNE) if for all $i\in N$ and all $S'_i\in \Sigma _i$ it holds that $c_i(S)\le c_i(S'_i,S_{-i})$ and a $\beta$ -approximate pure Nash equilibrium for a $\beta \ge 1$, if for all $i\in N$ and all $S'_i\in \Sigma _i$ it holds that $c_i(S)\le \beta \cdot c_i(S'_i,S_{-i})$. For a given game $\Gamma$, let $PNE \subseteq \mathbf {S}$ denote the set of all pure Nash equilibria of $\Gamma$. The Price of Anarchy is defined as the ratio between the social costs at the worst equilibria and the social optimum of the game, formally $PoA = \max _{S \in PNE} C(S) /\min _{\hat{S} \in \mathbf {P}} C(S)$, while the Price of Stability gives the ratio between the social costs at the best equilibria and the social optimum, formally $PoS = \min _{S \in PNE} C(S) /\min _{\hat{S} \in \mathbf {P}} C(S)$.

A singleton congestion game with mixed objectives is a congestion game with mixed objectives $\Gamma$ with the additional restriction that all strategies are singletons, i. e., for all $i\in N$ and all $S_i\in \Sigma _i$ we have that $|S_i|=1$. A matroid congestion game with mixed objectives is a congestion game with mixed objectives in which the strategy spaces of all players form the bases of a matroid on the set of resources. A network congestion game with mixed objectives is a congestion game with mixed objectives in which the strategy space of a player i corresponds to the set of paths between a source $s_i$ and a destination $t_i$ in an underlying graph. We say that the cost functions of a congestion game with mixed objectives have a monotone dependence if there is a monotone non-decreasing function $f:\mathbb {R}\rightarrow \mathbb {R}$, such that $e_r(x)=f(\ell _r(x))$ for all $r\in R$. We call the players $\alpha$ -uniform if there is an $\alpha \in [0,1]$ such that $\alpha _i=\alpha$ for all players $i\in N$. We say the players have pure preferences if $\alpha _i \in \{0,1\}$ for all players $i\in N$. Furthermore, we assume non-negative coefficients in the cost functions in the whole paper to not compromise the monotonicity and convexity of the functions.

2 Existence of pure Nash equilibria

Congestion games with mixed objectives are more expressive than standard or bottleneck congestion games. Consequently, the existence of pure Nash equilibria is guaranteed only for special cases. Unlike, e. g., player-specific congestion games, the matroid property is not sufficient for the existence of PNE. We show that we have the existence of PNE in singleton games or for matroid games with players that have pure preferences or cost functions that have a monotone dependence.

Theorem 1

A congestion game with mixed objectives $\Gamma$ contains a pure Nash equilibrium if $\Gamma$ is a

• 1. singleton congestion game, or

• 2. matroid congestion game and the players have pure preferences, or

• 3. matroid congestion game and the cost functions have a monotone dependence.

A pure Nash equilibrium of $\Gamma$ can be computed in polynomial time if one of the above three conditions is satisfied.

Proof

We prove the theorem by reducing the existence problem of a pure Nash equilibrium in a congestion game with mixed objectives to the existence problem of a PNE in a congestion game with player-specific cost functions. The existence of PNE is guaranteed in singleton (Milchtaich 1996) and matroid (Ackermann et al. 2009) player-specific congestion games and polynomial time complexity immediately follows (Ackermann et  al. 2008; Ackermann et al. 2009).

We will utilize the following lemma which states that an optimal basis with respect to sum costs is also optimal w. r. t. maximum costs. $\square$

Lemma 1

Let M be a matroid, and let $B=\{b_1,\dots ,b_m\}$ be a basis of M which minimizes the sum of the element costs. Then for any other basis $B'=\{b_1',\dots ,b_m'\}$ it holds that $\max _{1\le i \le m}b_i \le \max _{1\le i \le m}b_i'$.

Proof of Lemma

Let $B=\{b_1,\dots ,b_m\}$ be an optimal basis, and assume by contradiction that there is a different basis $B'=\{b_1',\dots ,b_m'\}$ with $b_m'<b_m$ (w. l. o. g. assume that $b_m$ and $b_m'$ are the most expensive resources in B and $B'$, respectively). Since B and $B'$ are both bases and $b_m\notin B'$, there is an element $b_i'\in B'$ such that $B''=B\setminus \{b_m\}\cup \{b_i'\}$ is a basis of M. By assumption we have $b_i'\le b_m'<b_m$, which implies that $B''$ has a smaller total cost than B. Therefore, B cannot be optimal, which gives a contradiction. $\square$

We now proceed to prove Theorem 1 and consider the three different cases:

• 1. The cost of player i in a state S with $S_i=\{r\}$ is $c_i(S)=\alpha _i\cdot \ell _r(S)+\left( 1-\alpha _i\right) \cdot e_r(S)$. By defining the player-specific cost functions $c_r^i(x)= \alpha _i\cdot \ell _r(x)+\left( 1-\alpha _i\right) \cdot e_r(x)$ for every $i\in N$ and $r\in R$, we obtain an equivalent singleton player-specific congestion game.

• 2. Using Lemma 1, we can treat all the players who strive to minimize their bottleneck costs as if they were striving to minimize the sum of the bottleneck costs of their resources. Hence, we can construct a player-specific congestion game in which the player-specific cost functions correspond to the latency functions for those players with preference value 1, and to the bottleneck cost functions for those players with preference value 0.

• 3. A player i who chooses the resources $\{r_1,\dots ,r_k\}$, where w. l. o. g. $r_k$ is the most expensive one, in a state S, incurs a total cost of $c_i(S)=\alpha _i\cdot \sum _{j=1}^k \ell _{r_j}(S)+\left( 1-\alpha _i\right) \cdot e_{r_k}(S)\, .$ Due to Lemma 1, we know that $\ell _{r_k}(S)$ is minimized if $\sum _{j=1}^k \ell _{r_j}(S)$ is minimized. The monotonicity of f with $e_r(x)=f(\ell _r(x))$ implies that $e_{r_k}$ is also minimized. Observe that monotonicity also ensures that $r_k$ is the bottleneck resource. Hence, a PNE of a congestion game with cost functions $\ell _r$ for every $r\in R$ is a PNE of $\Gamma$. $\square$

We show that the matroid property is not sufficient for the existence of PNE. Even for linear cost functions and uniform players, there are games without PNE.

Theorem 2

There is a matroid congestion game with mixed objectives $\Gamma$ with linear cost functions and $\alpha$-uniform players which does not possess a pure Nash equilibrium.

Proof

We construct a two-player game with linear cost functions and $\alpha _i=0.5$ for both players. The set of resources is $R=\left\{ r_1,\dots ,r_7\right\}$. The strategies for player 1 are $\Sigma _1=\left\{ \left\{ r_i,r_j,r_k\right\} ~|~i,j,k\in \{1,\dots ,6\}\right\}$ and the strategies for player 2 are $\Sigma _2=\left\{ \left\{ r_i,r_j\right\} ~|~i,j\in \{4,\dots ,7\}\right\}$. The latency and bottleneck cost functions for the first three resources are $\ell _{r_1}(x)=\ell _{r_2}(x)=\ell _{r_3}(x)=0$ and $e_{r_1}(x)=e_{r_2}(x)=e_{r_3}(x)=200\cdot x$, respectively. For resource $r_4$ and $r_5$ the cost functions are $\ell _{r_4}(x)=\ell _{r_5}(x)=20\cdot x$ and $e_{r_4}(x)=e_{r_5}(x)=50\cdot x$. For resource $r_6$ the cost functions are $\ell _{r_6}(x)=8\cdot x$ and $e_{r_6}(x)=80\cdot x$. For resource $r_7$ the cost functions are $\ell _{r_7}(x)=0$ and $e_{r_7}(x)=160\cdot x$.

We note that for player 1 only the strategies $S_{1,1}:=\{r_1,r_2,r_3\}$ and $S_{1,2}$ $:=\{r_4,r_5,r_6\}$ can be best-response strategies in any state, since $\{r_1,r_2,r_3\}$ strictly dominates all remaining strategies. Hence, with respect to the existence of pure Nash equilibria, we can restrict player 1 to these two strategies. In the analogous way, we can restrict player 2 to the strategies $S_{2,1}:=\{r_4,r_5\}$ and $S_{2,2}:=\{r_6,r_7\}$. This yields a game with only four states and, as we can easily verify, a best-response improvement step sequence starting from any of these states runs in cycles:

$$\begin{aligned} \begin{pmatrix}100 &{}&{} 45\\ S_{1,1}&{}&{}S_{2,1}\end{pmatrix} \xrightarrow {1} \begin{pmatrix}94 &{}&{} 90\\ S_{1,2}&{}&{}S_{2,1}\end{pmatrix} \xrightarrow {2} \begin{pmatrix}108 &{}&{} 88\\ S_{1,2}&{}&{}S_{2,2}\end{pmatrix} \xrightarrow {1} \begin{pmatrix}100 &{}&{} 84\\ S_{1,1}&{}&{}S_{2,2}\end{pmatrix} \xrightarrow {2} \begin{pmatrix}100 &{}&{} 45\\ S_{1,1}&{}&{}S_{2,1}\end{pmatrix} \end{aligned}$$

The numbers above the strategies give the costs of the respective player in the described state, and the numbers on the arrows indicate which player changes her strategy from one state to the next one. $\square$

Note that the nature of the existence proofs of Theorem 1 implies that a PNE can be computed in polynomial time assuming the satisfaction of the condition of the theorem. However, if existence is not guaranteed, the decision problem whether a matroid game has a pure Nash equilibrium is NP-hard:

Theorem 3

It is NP-hard to decide whether a matroid congestion game with mixed objectives possesses at least one pure Nash equilibrium even if the players are $\alpha$-uniform.

Proof

We reduce from Independent Set (IS), which is known to be NP-complete (Garey and Johnson 1979). Let the graph $G=(V,E)$ and $k\in \mathbb {N}$ be an instance of IS. We construct a matroid congestion game $\Gamma$ that has a pure Nash equilibrium if and only if G has an independent set of size at least k.

We begin by describing the structure of $\Gamma$. The game contains the following groups of players:

• For each node $v\in V$, there is one player who can choose all edges incident with v, but has a profitable deviation to a special strategy if and only if a player of a neighboring node chooses one of the incident edges.

• There are two players who play a game that is equivalent to the game in the proof of Theorem 2 if an additional player chooses a certain resource $r_7$, but possesses a PNE otherwise.

• Finally, there is one connection player for whom it is profitable to choose $r_7$ if and only if at least $n-k+1$ of the node players deviate from their “edge strategy”.

Clearly, if we can achieve this dynamic, the existence of a PNE in $\Gamma$ is equivalent to the existence of an independent set in G. Let $V=\{v_1,\dots ,v_n\}$, and for every $v_i\in V$ we denote by $E_{v_i}=\{e\in E~|~v_i\in e\}$ the set of edges incident to $v_i$, and by $d(v_i)=|E_{v_i}|$ the degree of $v_i$ in G. Let $\Delta =\max _{v\in V} d(v)$ be the maximum degree in G. We can assume that $\Delta \ge 2$.

We now give a formal definition of $\Gamma =(N,R,\left( \Sigma _i\right) _{i\in N},\left( \alpha _i\right) _{i\in N}, \left( \ell _r\right) _{r\in R}, \left( e_r\right) _{r\in R})$. The set of players is $N=\left\{ v_1,\dots ,v_n,c,1,2\right\}$ and the set of resources is $R=\{r_e~|~e\in E\} \cup \{r_i^j \mid i \in \{1,\ldots ,n\}, j \in \{1,\ldots ,d(v_i)-1\}\}\cup \{r_c,r_1,\dots ,r_7\}$. The strategies for the node players $v_i$ are all subsets of size $d(v_i)$ from a set consisting of the incident edge resources, some alternative resources, and resource $r_c$: $\Sigma _{v_i}=\left\{ \{X~|~ X\subseteq \left( \{r_e~|~e\in E_{v_i}\} \cup \{q_i^1,\dots ,q_i^{d(v_i)-1},\right. \right.$ $\left. \left. r_c\}\right) \text { and } |X|=d(v_i)\right\}$.

Our choice of cost functions will ensure that in an equilibrium every node player $v_i$ either chooses all resources $r_e$ that belong to her incident edges $e \in E_{v_i}$ or the resources $q_i$ and $r_c$. The two strategies of the connection player are $\Sigma _c=\{\{r_c\},\{r_7\}\}$. Finally, there are the players 1 and 2 with strategies $\Sigma _1=\left\{ \left\{ r_i,r_j,r_k\right\} \mid i,j,k\in \{1,\dots ,6\}\right\}$ and$, \Sigma _2=\left\{ \left\{ r_i,r_j\right\} ~|~i,j\in \{4,\dots ,7\}\right\}$, respectively.

The cost functions for the edge resources are $\ell _{r_e}(x)=1000 \cdot x$ and $e_{r_e}(x)=0$ for all $e\in E$, for the alternative resources $\ell _{q_i^j}(x)=0$ and $e_{q_i^j}(x)= 1000 \cdot d(v_i) + 1$ for all $1\le i \le n$ and $1 \le j \le \Delta$, and for the connection resource $\ell _{r_c}(x)=0$ and $e_{r_c}(x)=0$ for $x \le n-k+1$, $e_{r_c}(x)=1000$ for $x >n-k +1$. The cost functions of the resources $r_1,\dots ,r_7$ are $\ell _{r_1}(x)=\ell _{r_2}(x)=\ell _{r_3}(x)=0, e_{r_1}(x)=e_{r_2}(x)=e_{r_3}(x)=200\cdot x, \ell _{r_4}(x)=\ell _{r_5}(x)=20\cdot x,\ e_{r_4}(x)=e_{r_5}(x)=50\cdot x, \ell _{r_6}(x)=8\cdot x,\ e_{r_6}(x)=80\cdot x,\ \ell _{r_7}(x)=0,\ e_{r_7}(x)=80\cdot x$. We choose the value $\alpha _i=0.5$ for all players.

It remains to show that this game has a pure Nash equilibrium if and only if G has an independent set of size k. If there is an independent set, we can construct an equilibrium as follows: Each node player that corresponds to a node in the independent set chooses the strategy that contains all her edge resources. Each remaining node player chooses a strategy that contains only her q-resources and the resource $r_c$. The connection player chooses resource $r_c$. Player 1 chooses $\{r_1,r_2,r_3\}$ and player 2 chooses $\{r_6,r_7\}$. It is easy to verify that this is indeed a pure Nash equilibrium.

If there is no independent set of size at least k, we argue that in an equilibrium there are more than $n-k$ of the node players on resource $r_c$. Observe that for a node player that chooses at least one of the q-resources it is the best response to choose the remaining q-resources and the resource $r_c$ for no additional cost. Furthermore, if two node players choose the same edge resource, their best response is to choose the q-resources and $r_c$. Hence, the best response of the connection player is $\{r_7\}$ and players 1 and 2 will play the subgame defined in Theorem 2 that does not have a pure Nash equilibrium. $\square$

In Theorem 1 we investigated restrictions on the preference values and cost functions that guarantee the existence of PNE in congestion games with mixed objectives, when combined with the matroid property of strategy spaces. The following theorem shows that the matroid property is necessary even if we impose the additional constraint that bottleneck and latency cost functions are identical and linear and consider only small games with two players.

Theorem 4

There exists a congestion game with mixed objectives with linear cost functions $\ell _r=e_r$ for all resources $r\in R$, and either

• 1. pure preferences, or

• 2. $\alpha$-uniform players

which does not possess a pure Nash equilibrium.

Proof

We show the correctness of the statement by constructing two games which fulfill the preconditions stated in the two cases of the theorem and which do not have a pure Nash equilibrium.

• 1. We define the game with two players with $\alpha _1=0$ and $\alpha _2=1$. The game has six resources $R=\{r_1,r_2,\dots ,r_6\}$. Each player has two strategies, thus $\Sigma _1=\left\{ \{r_1\},\{r_2,r_3,r_4,r_5\}\right\}$ and $\Sigma _2=\left\{ \{r_2,r_3,r_4\},\{r_5,r_6\}\right\}$. The latency and bottleneck costs are given by $\ell _{r_1}(x)=6\cdot x$, $\ell _{r_2}(x)=\ell _{r_3}(x)=\ell _{r_4}(x)=2\cdot x$, $\ell _{r_5}(x)=4\cdot x$, $\ell _{r_6}(x)=3\cdot x$ with $e_r(x)=\ell _r(x)$ for all $r\in R$ We utilize the fact that bottleneck players prefer to choose many cheap resources, while players who are interested in latency are more willing to share a single expensive resource. Let $S_{1,1}$ and $S_{1,2}$ denote the strategies of player 1, and $S_{2,1}$ and $S_{2,2}$ the strategies of player 2. Then we have the following cycle of improvement steps which visits all four states:

  $$\begin{aligned} \begin{pmatrix}6 &{} 6\\ S_{1,1}&{}S_{2,1}\end{pmatrix} \xrightarrow {1} \begin{pmatrix}4 &{} 12\\ S_{1,2}&{}S_{2,1}\end{pmatrix} \xrightarrow {2} \begin{pmatrix}8 &{} 11\\ S_{1,2}&{}S_{2,2}\end{pmatrix} \xrightarrow {1} \begin{pmatrix}6 &{} 7\\ S_{1,1}&{}S_{2,2}\end{pmatrix} \xrightarrow {2} \quad \begin{pmatrix}6 &{} 6\\ S_{1,1}&{}S_{2,1}\end{pmatrix} \end{aligned}$$

  The numbers above the strategies give the cost of the respective player in the associated state, and the numbers on the arrows indicate which player has to change her strategy in order to get to the next state. As we see, every change in strategy decreases the cost of the player performing it. Hence, none of the four states is a pure Nash equilibrium.

• 2. We prove the theorem for the example $\alpha =0.5$. However, it is easily generalizable to arbitrary values between 0 and 1. The idea is to construct a game with two players in which one player always chooses an expensive resource. In addition to this, both players choose two resources and share exactly one of these resources. In detail we have the resources $R=\{r_1,r_2,\dots ,r_5\}$ and the strategy sets $\Sigma _1=\left\{ \{r_1,r_2,r_4\},\{r_1,r_3,r_5\}\right\}$ and $\Sigma _2=\left\{ \{r_2,r_5\},\{r_3,r_4\}\right\}$. The latency and bottleneck costs are given by $\ell _{r_1}(x)=32\cdot x$, $\ell _{r_2}(x)=\ell _{r_3}(x)=14\cdot x$ and $\ell _{r_4}(x)=\ell _{r_5}(x)=12\cdot x+8$ with $e_r(x)=\ell _r(x)$ for all $r\in R$. Depending on which resource is shared, the players choose either two resources with medium costs or one cheap and one expensive resource, where the sum of the two resource costs is slightly smaller in the latter case. The second player prefers the first alternative, since she has to pay an additional price for her most expensive resource. On the other hand, the first player always chooses an expensive resource, hence she incurs no additional costs when choosing a cheap and an expensive resource. The strategy spaces are constructed in such a way that in every state the players share exactly one of the resources $\{r_2,\dots ,r_5\}$. Let $S_1$ denote a state in which $r_2$ or $r_3$ is shared, and $S_2$ a state in which $r_4$ or $r_5$ is shared. Then the players incur the following costs: $c_1(S_1)=56, c_2(S_1)=38, c_1(S_2)=55, c_2(S_2)=39$. As we see, player 1 prefers the state $S_2$, while player 2 prefers $S_1$. Since both players always have the possibility to deviate to the other state, there is no state in which none of the players can decrease her costs, and hence $\Gamma$ possesses no pure Nash equilibrium. $\square$

Also here, if existence is not guaranteed, we can show that it is NP-hard to decide whether a pure Nash equilibrium exists.

Theorem 5

It is NP-hard to decide whether a congestion game with mixed objectives with linear cost functions $\ell _r=e_r$ for all resources $r\in R$ possesses at least one pure Nash equilibrium even with either

• 1. pure preferences, or

• 2. $\alpha$-uniform players.

Proof

We reduce from Independent Set (IS), which is known to be NP-complete (Garey and Johnson 1979). Let the graph $G=(V,E)$ and $k\in \mathbb {N}$ be an instance of IS. Let $V=\{v_1,\dots ,v_n\}$, and for every $v_i\in V$ we denote by $E_{v_i}=\{e\in E~|~v_i\in e\}$ the set of edges incident to $v_i$. For both cases, we construct a congestion game $\Gamma$ that has a pure Nash equilibrium if and only if G has an independent set of size at least k. For the construction we use the games defined in the proof of Theorem 4.

• 1. We define $\Gamma$ with the set of players $N=\left\{ 1, \ldots , k,c,k+1,k+2\right\}$ and the set of resources $R=\{r_e~|~e\in E\} \cup \{r_c,r_1,\dots ,r_6\}$. The strategies for the k node players $1, \ldots , k$ are either all incident edges of a node v or the connection resource $r_c$: $\Sigma _i = \left\{ \left\{ r_e \mid e \in E_v\right\} \mid v \in V\right\} \cup \left\{ \left\{ r_c\right\} \right\}$ for $1\le i\le k$. The two strategies of the connection player are $\Sigma _c=\{\{r_c\},\{r_1\}\}$. Finally, there are the players $k+1$ and $k+2$ with strategies $\Sigma _{k+1}=\left\{ \left\{ r_1\right\} , \left\{ r_2,r_3,r_4,r_5\right\} \right\}$ and$, \Sigma _{k+2}=\left\{ \left\{ r_2,r_3,r_4\right\} ,\left\{ r_5,r_6\right\} \right\}$, respectively. The cost functions for the edge resources are $\ell _{r_e}(x)=e_{r_e}(x)=6 \cdot x$ for all $e\in E$ and for the connection resource $\ell _{r_c}(x)=e_{r_c}(x)=5 \cdot x$. The cost functions of the other resources are given by $\ell _{r_1}(x)=3x,\ell _{r_2}(x)=\ell _{r_3}(x)=\ell _{r_4}(x)=2x,\ell _{r_5}(x)=4x,\ell _{r_6}(x)=3x$ with $e_r(x)=\ell _r(x)$ for all $r \in \left\{ r_1,\dots ,r_6\right\}$. We choose the values $\alpha _1 = \dots = \alpha _k = \alpha _c = \alpha _{k+1}=0$ and $\alpha _{k+2}=1$ for the players. It remains to show that this game has a pure Nash equilibrium if and only if G has an independent set of size k. If there is an independent set, we can construct an equilibrium as follows: Each node player chooses the strategy that contains all the edge resources which are incident to the node in the independent set. The connection player chooses resource $r_c$. Player $k+1$ chooses $\{r_1\}$ and player $k+2$ chooses $\{r_2,r_3,r_4\}$. It is easy to verify that this is indeed a pure Nash equilibrium. If there is no independent set of size at least k, then at least one edge resource has to be used by more than one node player if all node players only use their edge resources. Therefore, there exists at least one node players who could improve by choosing the strategy that contains the connection resource. Hence, in an equilibrium at least one of the node players chooses this strategy. However, the best response of the connection player is $\{r_1\}$ and players $k+1$ and $k+2$ will play the sub game defined in Theorem 4 that does not have a pure Nash equilibrium.

• 2. We again define the game $\Gamma$ with the set of players $N=\left\{ 1, \ldots , k,c,k+1,\right. \left. k+2\right\}$. The set of resources is given by $R=\{r_e~|~e\in E\} \cup \{r_v~|~v\in V\} \cup \{r_c,r_1,\dots ,r_5\}$. The strategies for the k node players are defined by $\Sigma _i = \left\{ \left\{ r_e \mid e \in E_v\right\} \cup \left\{ r_v\right\} \mid v \in V\right\} \cup \left\{ \left\{ r_c\right\} \right\}$ for $1\le i\le k$. The two strategies of the connection player are $\Sigma _c=\{\{r_c\},\{r_1\}\}$. Finally, there are the players $k+1$ and $k+2$ with strategies $\Sigma _{k+1}=\left\{ \left\{ r_1, r_2, r_4\right\} , \left\{ r_1,r_3,r_5\right\} \right\}$ and$, \Sigma _{k+2}=\left\{ \left\{ r_2,r_5\right\} ,\left\{ r_3,r_4\right\} \right\}$, respectively. Let the maximum degree of the nodes be $\Delta =\max _{u\in V}|E_u|$. The cost functions for the edge resources are $\ell _{r_e}(x)=e_{r_e}(x)=\frac{1}{\Delta } \cdot 20 \cdot x$ for all $e\in E$, $\ell _{r_v}(x)=e_{r_v}(x)=\frac{1}{\Delta } \cdot 20 \cdot \left( \Delta - |E_v|\right)$ for all $v\in V$ and for the connection resource $\ell _{r_c}(x)=e_{r_c}(x)=18 \cdot x$. The cost functions of the other resources are given by $\ell _{r_1}(x)=16x,\ell _{r_2}(x)=\ell _{r_3}(x)=14x,\ell _{r_4}(x)=\ell _{r_5}(x)=12x+8$ with $e_r(x)=\ell _r(x)$ for all $r \in \left\{ r_1,\dots ,r_5\right\}$. We choose the values $\alpha _i = 0.5$ for all players $i \in N$. The rest of the proof follows with the same arguments as in the first case and using properties of the second game of in the proof of Theorem 4. $\square$

If we limit our game class to network congestion games, we can even prove the NP-hardness for network congestion games with only two players.

Theorem 6

It is NP-hard to decide whether a network congestion game with mixed objectives possesses at least one pure Nash equilibrium even if there are only two players with pure preferences.

Proof

We prove the theorem for the case of asymmetric network games in directed graphs. We reduce from the two edge-disjoint paths problem. This problem consists in deciding, given a graph G and two node pairs $(s_1,t_1)$ and $(s_2,t_2)$, whether there exist paths from $s_1$ to $t_1$ and $s_2$ to $t_2$ without a common edge. It is known to be NP-complete for directed graphs (Fortune et al. 1980). Given a directed graph $G=(V,E)$ and two source-sink pairs $(s_1,t_1)$ and $(s_2,t_2)$, we construct a congestion game with mixed objectives $\Gamma$ as follows:

• For every edge $(u,v)\in E$ we create a gadget of six nodes and eight edges as shown in Figure 1, yielding the graph $G'=(V',E')$. The edges correspond to the eight resources $r_1, \ldots r_8$.

• There are two players with $\alpha _1=1$ and $\alpha _2=0$. The strategy set $\Sigma _i$ of player i corresponds to all cycle-free paths from $s_i$ to $t_i$ in $G'$, for $i\in \{1,2\}$.

• For every gadget of eight resources, we define the following cost functions:

  $$\begin{aligned} \ell _{r_1}(x)= & {} \ell _{r_2}(x)=\ell _{r_5}(x)=\ell _{r_6}(x)=e_{r_3}(x)=e_{r_4}(x)=e_{r_7}(x)=e_{r_8}(x)=0\\ e_{r_1}(x)= & {} e_{r_2}(x)=\ell _{r_7}(x)=\ell _{r_8}(x)= {\left\{ \begin{array}{ll} 0, x \le 1\\ 1, x > 1\end{array}\right. }\\ \ell _{r_3}(x)= & {} \ell _{r_4}(x)=e_{r_5}(x)=e_{r_6}(x)=|E|+1 \end{aligned}$$

Fig. 1

Gadget for one edge (u, v)

Only the bottleneck costs of the two edges from u and the latency costs of the edges leading to v change when they are used by both players. The cost functions of the four middle edges are constructed in such a way that player 1 cannot use the resources $r_3$ and $r_4$, and player 2 cannot use $r_5$ and $r_6$ without incurring very high costs. Hence, player 1 has the two possible strategies $\{r_1,r_5,r_7\}$ and $\{r_2,r_6,r_8\}$, while player 2 has the strategies $\{r_1,r_3,r_8\}$ and $\{r_2,r_4,r_7\}$ for each gadget. As we see, for every gadget used by both players they have to share exactly one resource. This implies that one of them has a cost of 0 and the other one a cost of 1 on this gadget. On the other hand, if the players do not share any gadget at all, both have a cost of 0.

Summarizing this, we get three different types of states $S=(S_1,S_2)$ (ignoring the irrelevant states in which at least one of the players has a cost of $|E|+1$):

• If $c_i(S)=0$ for $i\in \{1,2\}$, it must hold that $S_1$ and $S_2$ correspond to disjoint paths from $s_1$ to $t_1$ and $s_2$ to $t_2$ in G.

• If $c_1(S)>0$, then player 1 can decrease her cost on at least one gadget from 1 to 0 by switching the strategy. Hence, S can not be a PNE.

• If $c_1(S)=0$ and $c_2(S)=1$, both players share at least one gadget and player 2 incurs a cost of 1 on all shared gadgets (since player 1 has a cost of 0). Then player 2 can decrease her cost to 0 by deviating to the other strategy on all shared gadgets. Hence, S can not be a PNE.

We get that $\Gamma$ possesses a pure Nash equilibrium if and only if there exist two disjoint $(s_1,t_1)$ and $(s_2,t_2)$-paths in G. Since it is NP-hard to decide whether these paths exist, it is also NP-hard to decide whether $\Gamma$ contains a pure Nash equilibrium. $\square$

3 Convergence and quality of equilibria

In this section we investigate in which games convergence of best-response improvement sequences to a pure Nash equilibrium can be guaranteed and how good the equilibria are. Perhaps surprisingly, there are singleton games in which best-response improvement sequences may run in cycles. This is even true for games with pure preferences.

Theorem 7

There are singleton congestion games with mixed objectives and pure preferences in which best-response improvement sequences may run in cycles.

Proof

We prove the theorem by constructing a singleton game with three players and showing that there exists a cyclic best-response improvement sequence in certain states. The game consists of three resources $R=\{r_1,r_2,r_3\}$ and the players have the strategy sets $\Sigma _1=\left\{ \{r_1\},\{r_2\}\right\}$, $\Sigma _2=\left\{ \{r_1\},\{r_3\}\right\}$ and $\Sigma _3=\left\{ \{r_2\},\{r_3\}\right\}$. Two players prefer the latency costs $\alpha _1=\alpha _2=1$, one the bottleneck costs $\alpha _3=0$. The latency and bottleneck costs are given by $\ell _{r_1}=(2,5)$, $\ell _{r_2}=(3,4)$, $\ell _{r_3}=(1,6)$ and $e_{r_2}=(1,4)$, $e_{r_3}=(2,3)$. The first number in the cost functions gives the cost if the resource is used by one player, the second number gives the cost if two players use it. The bottleneck cost function of $r_1$ is irrelevant since it is only used by players 1 and 2.

In this game, the following cycling best-response improvement sequence can occur (set braces omitted for better readability):

$$\begin{aligned}&\begin{pmatrix}5 &{} 5 &{} 1\\ r_1 &{} r_1 &{} r_2 \end{pmatrix} \xrightarrow {1} \begin{pmatrix}4 &{} 2 &{} 4\\ r_2 &{} r_1 &{} r_2 \end{pmatrix} \xrightarrow {2} \begin{pmatrix}4 &{} 1 &{} 4\\ r_2 &{} r_3 &{} r_2 \end{pmatrix} \xrightarrow {3} \begin{pmatrix}3 &{} 6 &{} 3\\ r_2 &{} r_3 &{} r_3\end{pmatrix} \xrightarrow {1} \begin{pmatrix}2 &{} 6 &{} 3\\ r_1 &{} r_3 &{} r_3 \end{pmatrix} \\&\quad \xrightarrow {2} \begin{pmatrix}5 &{} 5 &{} 2\\ r_1 &{} r_1 &{} r_3 \end{pmatrix} \xrightarrow {3} \begin{pmatrix}5 &{} 5 &{} 1\\ r_1 &{} r_1 &{} r_2 \end{pmatrix} \end{aligned}$$

The numbers on the arrows indicate which player has to change her strategy in order to reach the next state. The variable $r_i$ denotes the resource which is used by the corresponding player and the number on top gives the cost value for this player. We can verify that each change in strategy is beneficial for the player performing it (since every player has only two strategies, every improving strategy is a best-response strategy).

Hence, we have a cycle of six states that are visited during this best-response improvement sequence. The pure Nash equilibria $(r_1,r_3,r_2)$ and $(r_2,$ $r_1, r_3)$ are never reached. $\square$

Note that due to our reduction in the proof of Theorem 1, we know that there exists a sequence of best-response moves that leads to an equilibrium (Ackermann et al. 2009).

Corollary 1

• 1. Singleton congestion games with mixed objectives are weakly acyclic.

• 2. Matroid congestion games with mixed objectives that have pure preferences are weakly acyclic.

We now turn to matroid games with a monotone dependence and show that they converge quickly to a PNE if the players perform lazy best-response moves. That is, if players perform a best response move, they choose the best-response strategy that has as many resources in common with the previous strategy as possible.

Theorem 8

Let $\Gamma$ be a matroid congestion game with mixed objectives with cost functions that have a monotone dependence. Then any sequence of lazy best-response improvement steps starting from an arbitrary state in $\Gamma$ converges to a pure Nash equilibrium after a polynomial number of steps.

Proof

The proof idea is based on the proof by Ackermann et  al. (2008) which shows that matroid congestion games guarantee polynomial convergence to PNE.

We consider an increasingly ordered enumeration of all latency values that can occur in $\Gamma$ (an enumeration of the values $\{\ell _r(x)~|~r\in R,x\in N\}$). Let $\ell '_r(x)$ denote the position of the respective cost value in the enumeration.

We define the following variant of Rosenthal’s potential function: $\Phi (S)=\sum _{r\in R}\sum _{i=1}^{n_r(S)}\ell '_r(i)$. If $n=|N|$ denotes the number of players, and $m=|R|$ the number of resources in $\Gamma$, then there are at most $n\cdot m$ different cost values in the game. Hence, the value of $\Phi$ is upper bounded by $n^2\cdot m^2$. Thus, it suffices to show that every lazy best-response improvement step decreases the value of $\Phi$ by at least 1.

If a player replaces a single resource r by another resource $r'$ in a lazy best-response with $\alpha _i \cdot \ell _{r'}(S') +(1-\alpha _i) \cdot e_{r'}(S') <\alpha _i \cdot \ell _{r}(S) +(1-\alpha _i) \cdot e_{r}(S)$, then due to the monotone dependence, we have $\ell _{r'}(S') < \ell _r(S)$. Hence $\ell _{r'}(S')$ must occur before $\ell _r(S)$ in the increasingly ordered enumeration of the cost values and we have $\ell '_{r'}(S') < \ell '_r(S)$. Thus, every sequence of lazy best-response improvement steps in $\Gamma$ terminates after a polynomial number of steps.$\square$

We remark that the only reason to restrict the players to lazy instead of arbitrary best-response strategies is that the players may have a preference value of exactly 0. If a player’s cost is determined solely by her most expensive resource, she might be playing a best-response strategy by replacing her most expensive resource by a cheaper one and additionally replace another resource by a more expensive one. This additional exchange does not necessarily increase her costs, but it could lead to an increase in the value of the potential function. However, if all players have preference values different from 0, the theorem holds for arbitrary best-response improvement steps.

We now study the quality of equilibria compared to optimal states.

Proposition 1

Let $\Gamma$ be a congestion game with mixed objectives with linear cost functions without negative coefficients which contains at least one pure Nash equilibrium. Then the Price of Anarchy in $\Gamma$ is at most n.

Proof

Assume by contradiction that $\Gamma$ contains a pure Nash equilibrium $S=(S_1,\dots ,S_n)$, and that there is a different state $S^*=(S_1^*,\dots ,S_n^*)$ such that $n\cdot \sum _{i\in N}c_i(S^*)<\sum _{i\in N}c_i(S)$. This implies that there is at least one player j s.t. $c_j(S)>n\cdot c_j(S^*)$. Since all cost functions are linear without negative coefficients, the cost of strategy $S_j^*$ in any state can be at most $n\cdot c_j(S^*)<c_j(S)$. Thus, we get that $c_j(S_j^*,S_{-j})<c_j(S)$, which implies that j has a profitable deviation from strategy $S_j$ in state S. Hence, S can not be a pure Nash equilibrium, which establishes a contradiction. $\square$

We remark that the proposition makes a statement about the properties of pure Nash equilibria which are not guaranteed to exist. There are congestion games with mixed objectives with linear cost functions that do not possess a PNE, but if a PNE exists, the price of anarchy is guaranteed to be bounded by n. The result that the price of anarchy is bounded by n seems almost trivial. However, we can show that this bound is tight by constructing a game in which the price of anarchy is exactly n.

Theorem 9

For every $n\in \mathbb {N}$ with $n\ge 2$, there is a singleton congestion game with mixed objectives with linear cost functions without negative coefficients, which has n players and a Price of Anarchy of n.

Proof

We prove the statement by constructing the following game for an arbitrary n: Let $\Gamma$ be a singleton game with n players and two resources $r_1$ and $r_2$. the strategy for player 1 is $\Sigma _1=\{\{r_1\}\}$ and the strategies for every player $i \ge 2$ are $\Sigma _i=\{\{r_1\},\{r_2\}\}$. Player 1 has a preference value of $\alpha _1=1$, all other players $i\ge 2$ have $\alpha _i=0$. The latency function for the first resource is $\ell _{r_1}(x)= x$ and the other latency and bottleneck functions are $\ell _{r_2}(x) = e_{r_1}(x)=e_{r_2}(x) = 0$.

Consider the state $S^*=\left( \{r_1\},\{r_2\},\dots ,\{r_2\}\right)$. In this state, player 1 has a cost of 1 since only she chooses resource $r_1$, all other players have a cost of 0. Hence, the sum of all costs in state $S^*$ is exactly 1. Now consider the state $S=\left( \{r_1\},\{r_1\},\dots ,\{r_1\}\right)$. In this state, player 1 has a cost of n, all other players have a cost of 0. Since player 1 cannot change her strategy, this state is a pure Nash equilibrium. Hence, we get as price of anarchy

$$\begin{aligned} \frac{\sum _{i\in N}c_i(S)}{\sum _{i\in N}c_i(S^*)}=\frac{n}{1}=n. \end{aligned}$$

$\square$

We note that the game constructed in the proof is a “dummy game”, since the cost of each player is independent of her strategy choice. However, by slightly modifying the cost functions (setting $e_{r_1}(x)=\epsilon \cdot x$ for some $\epsilon >0$) we achieve that the described worst case equilibrium is the only PNE of the game. Then the price of anarchy (and price of stability) of the game is given by

$$\begin{aligned} \frac{\sum _{i\in N}c_i(S)}{\sum _{i\in N}c_i(S^*)}=\frac{n}{1+n\cdot n\cdot \epsilon }. \end{aligned}$$

Since we can chose $\epsilon$ arbitrarily small, there is no constant $\delta <1$ such that the price of stability is smaller than $\delta \cdot n$. Hence, we get the following corollary:

Corollary 2

For every $n\in \mathbb {N}$ with $n\ge 2$, and every $\epsilon >0$ there is a singleton congestion game with mixed objectives with linear cost functions without negative coefficients, which has n players and a Price of Stability of at least $(1-\epsilon )\cdot n$.

4 Approximate pure Nash equilibria

As PNE do not exist in general, we study the existence of approximate equilibria. However, in general we cannot achieve an approximation factor better than 3.

Theorem 10

There is a congestion game with mixed objectives, in which all cost functions are linear, that does not contain a 3-approximate pure Nash equilibrium.

Proof

We show the theorem by constructing a game with 10 players, in which in every state there is at least one player who can decrease her costs by a factor of 3. A formal definition of the game is given by:

$$\begin{aligned} \Gamma&=(N,R,\left( \Sigma _i\right) _{i\in N},\left( \alpha _i\right) _{i\in N}, \left( \ell _r\right) _{r\in R},\left( e_r\right) _{r\in R})\quad \hbox {with}\\ N&=\{1,\dots ,10\}, R=\left\{ r^i_1,r^i_2~|~i\in N\setminus \{5,6\}\right\} \cup \\&\times \left\{ r^{i,j}_{1,1},r^{i,j}_{1,2},r^{i,j}_{2,1},r^{i,j}_{2,2}~|~i<j \text { and } \left( i,j\in \{1,2,3,4\}\text { or } i,j\in \{7,8,9,10\}\right) \right\} ,\\ \Sigma _i&=\left\{ \{r^i_1\} \cup \{r^{j,k}_{1,1},r^{j,k}_{2,1}~|~j=i\text { or } k=i\},\right. \\&\left. \{r^i_2\} \cup \{r^{j,k}_{1,2},r^{j,k}_{2,2}~|~j=i\text { or } k=i\}\right\} \text { for all }i\in N\setminus \{5,6\}\\ \Sigma _{5}&=\{\{r^1_1,\dots ,r^4_1,r^{7}_1,\dots ,r^{10}_1, r^{i,j}_{1,2}, r^{k,l}_{1,2}~|~i,j\in \{1,\dots ,4\},\ k,l\in \{7,\dots ,10\}\}\\&\cup \left\{ \left\{ r^1_2,\dots ,r^4_2,r^{7}_2,\dots ,r^{10}_2, r^{i,j}_{1,1}, r^{k,l}_{1,1}~|~i,j\in \{1,\dots ,4\},\ k,l\in \{7,\dots ,10\}\right\} \right. \\ \Sigma _{6}&=\left\{ \{r^1_1,\dots ,r^4_1,r^{7}_2,\dots ,r^{10}_2, r^{i,j}_{2,2}, r^{k,l}_{2,1}~|~i,j\in \{1,\dots ,4\},\ k,l\in \{7,\dots ,10\}\right\} \\ \cup&\left\{ \{r^1_2,\dots ,r^4_2,r^{7}_1,\dots ,r^{10}_1, r^{i,j}_{2,1}, r^{k,l}_{2,2}~|~i,j\in \{1,\dots ,4\},\ k,l\in \{7,\dots ,10\}\right\} \end{aligned}$$

• $\alpha _i=1$ for all $i\in N\setminus \{5,6\}$ and $\alpha _i=0$ for $i\in \{5,6\}$,

• $\ell _r(x)=x$ and $e_r(x)=0$ for all $r\in \left\{ r^i_j~|~i\in N\setminus \{5,6\},j\in \{1,2\}\right\}$,

• $\ell _r(x)=0$ and $e_r(x)=x$ for all $r\in \left\{ r^{i,j}_{k,l}~|~i,j\in N\setminus \{5,6\},\ k,l\in \{1,2\}\right\}$

The game contains three different groups of players and two different groups of resources. Players 1 to 4 and 7 to 10 each have two personal resources $r^i_1$ and $r^i_2$ among which they have to choose. These are the only resources on which they incur costs.

In addition to these resources, there are two times two resources corresponding to each set consisting of two players from the same group (either 1 to 4 or 7 to 10). The two resources represent the two strategies which are available to these players, and exist distinctly for both players 5 and 6. If player i plays her first strategy, then she also chooses all resources that correspond to sets in which i is contained and represent the first strategy.

In every state, the players 5 and 6 choose one of the personal resources $r^i_j$ for each player $i\in \{1,\dots ,4\}$ and $i\in \{7,\dots , 10\}$, where the j is the same for all players among a group. Additionally, for both groups they have to choose a resource that corresponds to one pair of players and represents the j that they are not using (e. g., if player 5 chooses resource $r^i_1$ for all players $i\in \{1,\dots ,4\}$, she must also choose a resource that corresponds to a pair of players from $\{1,\dots ,4\}$ and represents strategy 2, and an analogous resource for the players in $\{7,\dots ,10\}$).

These two additional resources are the ones on which players 5 and 6 incur costs. Since they are interested in their bottleneck costs, their costs are equal to the more expensive of the two.

We can analyze this game by considering an arbitrary state. The strategy sets of players 5 and 6 are constructed in such a way that in every state they choose the same personal resources of all players in $\{1,\dots ,4\}$ or $\{7,\dots ,10\}$.

W. l. o. g. assume that they both choose the resources $r^1_1,\dots ,r^4_1$. This implies that the players 1 to 4 have a cost of 3 if they use the first resource, and a cost of 1 if they choose their second resource. Hence, this state cannot be a 3-approximate PNE if any of them play their first strategy.

If, on the other hand, all these players play their second strategy, players 5 and 6 incur a cost of 3 on their resources $r^{i,j}_{1,2}$ and $r^{i,j}_{2,2}$, respectively, independent of which i and j they are using, since all players in $\{1,\dots ,4\}$ choose the resources corresponding to strategy 2. Both players 5 and 6 could decrease the cost of the resource corresponding to the first group to 1 by switching the strategy. However, we have to take the other group into account as well.

If player 5 switches her strategy, she chooses the resource $r^{k,l}_{1,1}$ for freely selectable k and l in $\{7,\dots , 10\}$, which yields a cost of 1 if at least two players from $\{7,\dots ,10\}$ play the second strategy. Analogously, player 6 incurs a cost of 1 on the resource corresponding to the second group if at least two players from this group play their first strategy. One of the two cases must hold, which implies that either player 5 or player 6 can decrease her cost from 3 to 1. Hence, in every state there is at least one player who can decrease her cost by a factor of 3, and there exists no 3-approximate pure Nash equilibrium. $\square$

Additionally, we can show that the decision problem whether a 3-approximate pure Nash equilibrium exists is NP-hard.

Theorem 11

It is NP-hard to decide whether a congestion game with mixed objectives with linear cost functions $\ell _r=e_r$ for all resources $r\in R$ possesses at least one 3-approximate pure Nash equilibrium.

Proof

We follow the same proof idea as in Theorem 5 in the first case and reduce from Independent Set (IS), which is known to be NP-complete (Garey and Johnson 1979). Let the graph $G=(V,E)$ and $k\in \mathbb {N}$ be an instance of IS. Let $V=\{v_1,\dots ,v_n\}$, and for every $v_i\in V$ we denote by $E_{v_i}=\{e\in E~|~v_i\in e\}$ the set of edges incident to $v_i$. For both cases, we construct a congestion game $\Gamma$ that has a $\beta$-approximate pure Nash equilibrium if and only if G has an independent set of size at least k. For the construction we reuse the game defined in the proof of Theorem 10.

We define $\Gamma$ with the set of players $N=\left\{ 1, \ldots , k,c,k+1,\ldots , k+10\right\}$ and the set of resources is $R=\{r_e~|~e\in E\} \cup \{r_c\} \cup \left\{ r^i_1,r^i_2~|~i\in \{k+1, \ldots , k+4,\right. \left. k+7,\ldots , k+10\}\right\} \cup \left\{ r^{i,j}_{1,1},r^{i,j}_{1,2},r^{i,j}_{2,1},r^{i,j}_{2,2}~|~i<j \text { and } \left( i,j\in \{k+1,\ldots ,k+4\}\right. \right. \left. \left. \text {or } i,j\in \{k+7,\ldots , k+10\}\right) \right\}$. The strategies for the k node players $1, \ldots , k$ are either all connected edges of a node v or the connection resource $r_c$: $\Sigma _i = \left\{ \left\{ r_e \mid e \in E_v\right\} \mid v \in V\right\} \cup \left\{ \left\{ r_c\right\} \right\}$ for $1\le i\le k$. The two strategies of the connection player are

$$\begin{aligned} \Sigma _c=\{\{r_c\},\{r^{k+1}_1,\dots ,r^{k+4}_1,r^{k+7}_1,\dots ,r^{k+10}_1, r^{k+1,k+2}_{1,2}, r^{k+7,k+8}_{1,2}\}\}. \end{aligned}$$

Finally, there are the players $k+1, \ldots , k+10$ with strategies

$$\begin{aligned} \Sigma _i=&\left\{ \{r^i_1\} \cup \{r^{j,k}_{1,1},r^{j,k}_{2,1}~|~j=i\text { or } k=i\}, \{r^i_2\} \cup \{r^{j,k}_{1,2},r^{j,k}_{2,2}~|~j=i\text { or } k=i\}\right\} \\&\text { for all }i\in \{k+1, \ldots , k+4, k+7,\ldots , k+10\} \end{aligned}$$

$$\begin{aligned} \Sigma _{k+5}=&\left\{ \{r^{k+1}_1,\dots ,r^{k+4}_1,r^{k+7}_1,\dots ,r^{k+10}_1, r^{i,j}_{1,2}, r^{k,l}_{1,2}~|~\right. \\&\left. i,j\in \{k+1,\dots ,k+4\},\ k,l\in \{k+7,\dots ,k+10\}\right\} \\ \cup&\left\{ \{r^{k+1}_2,\dots ,r^{k+4}_2,r^{k+7}_2,\dots ,r^{k+10}_2, r^{i,j}_{1,1}, r^{k,l}_{1,1}~|~\right. \\&\left. i,j\in \{k+1,\dots ,k+4\},\ k,l\in \{k+7,\dots ,k+10\}\right\} \\ \Sigma _{k+6}=&\left\{ \{r^{k+1}_1,\dots ,r^{k+4}_1,r^{k+7}_2,\dots ,r^{k+10}_2, r^{i,j}_{2,2}, r^{k,l}_{2,1}~|~\right. \\&\left. i,j\in \{k+1,\dots ,k+4\},\ k,l\in \{k+7,\dots ,k+10\}\right\} \\ \cup&\left\{ \{r^{k+1}_2,\dots ,r^{k+4}_2,r^{k+7}_1,\dots ,r^{k+10}_1, r^{i,j}_{2,1}, r^{k,l}_{2,2}~|~\right. \\&\left. i,j\in \{k+1,\dots ,k+4\},\ k,l\in \{k+7,\dots ,k+10\}\right\} \end{aligned}$$

The cost functions for the edge resources are $\ell _{r_e}(x)=e_{r_e}(x)=x+1$ for all $e\in E$ and for the connection resource $\ell _{r_c}(x)=e_{r_c}(x)=x$. The cost functions of the other resources are given by $\ell _r(x)=x$ and $e_r(x)=0$ for all $r\in \left\{ r^i_j~|~i\in \{k+1,\ldots , k+4, k+7, \ldots , k+10\},j\in \{1,2\}\right\}$, $\ell _r(x)=0$ for all $r\in \left\{ r^{i,j}_{k,l}~|~i,j\in \{k+1,\ldots , k+4, k+7, \ldots , k+10\}, k,l\in \{1,2\}\right\}$, $e_r(x)=x-1$ for $r^{k+1,k+2}_{1,2}$ and $r^{k+7,k+8}_{1,2}$ and $e_r(x)=x$ for all other $r\in \left\{ r^{i,j}_{k,l}~|~i,j\in \{k+1,\ldots , k+4, k+7, \ldots , k+10\}, k,l\in \{1,2\}\right\} \setminus \{r^{k+1,k+2}_{1,2}, r^{k+7,k+8}_{1,2}\}$. We choose the values $\alpha _i=1$ for all $i\in \{k+1,\ldots , k+4, k+7, \ldots , k+10\}$ and $\alpha _i=0$ for $i\in \{1, \ldots , k,c,k+5,k+6\}$.

It remains to show that this game has a 3-approximate pure Nash equilibrium if and only if G has an independent set of size k. If there is an independent set, we can construct an approximate equilibrium as follows: Each node player chooses the strategy that contains all the edge resources which are connected to the node in the independent set. The connection player chooses resource $r_c$. Player $k+5$ chooses $\{r^{k+1}_1,\dots ,r^{k+4}_1,r^{k+7}_1,\dots ,r^{k+10}_1, r^{k+1,k+2}_{1,2}, r^{k+7,k+8}_{1,2}\}$. It is easy to verify that this is indeed a 3-approximate pure Nash equilibrium. If there is no independent set of size at least k, then at least one edge resource has to be used by more than one node player (if all node players only use their edge resources). Therefore this node player changes her strategy to choose the connection resource because of the definition of the cost functions. Hence, the best response of the connection player is $\{r^{k+1}_1,\dots ,r^{k+4}_1,r^{k+7}_1,\dots ,r^{k+10}_1, r^{k+1,k+2}_{1,2}, r^{k+7,k+8}_{1,2}\}$ and players $k+1, \ldots k+10$ will play the sub game defined in Theorem 10 that does not have a 3-approximate pure Nash equilibrium. $\square$

On the positive side we can show small approximation factors for small strategy sets if we restrict the cost functions to linear and polynomial functions.

Proposition 2

Let $\Gamma$ be a congestion game with mixed objectives with linear cost functions without negative coefficients. Let $d=max_{i\in N,S_i\in \Sigma _i}|S_i|$ be the maximal number of resources a player can choose. Then $\Gamma$ contains an $e^d$-approximate pure Nash equilibrium and every sequence of $e^d$-improvement steps starting from an arbitrary state in $\Gamma$ reaches an $e^d$-approximate pure Nash equilibrium after a finite number of steps.

Proof

We will prove the statement by analyzing the effect of an additional player on the cost of a resource. In a game with linear cost functions without negative coefficients, the cost of a resource which is currently used by m players is increased at most by a factor of $\frac{m+1}{m}$. Using this, we can define the following approximate potential function $\Phi (S)$, which decreases in every $\beta$-improvement step:

$$\begin{aligned} \Phi (S)=\prod _{i\in N}c_i(S). \end{aligned}$$

(1)

Assume that a resource r is allocated by m players in state S, and is now allocated by one more player, yielding the state $S'$. Then the costs of all m players who used r before increase at most by a factor of $\frac{m+1}{m}$, and thus, the product of their costs by at most $\left( \frac{m+1}{m}\right) ^m$. We get

$$\begin{aligned} \prod _{i\in N~|~r\in S_i}c_i(S')\le \left( \frac{m+1}{m}\right) ^m\cdot \prod _{i\in N~|~r\in S_i}c_i(S)<e\cdot \prod _{i\in N~|~r\in S_i}c_i(S), \end{aligned}$$

since $\left( \frac{m+1}{m}\right) ^m$ converges to e from below for $m\rightarrow \infty$.

If a player i chooses d additional resources, then repeating this argument yields that the product of the costs of all players who use one of these resources increases by less than a factor of $e^d$. The costs of all other players do not increase. Hence, if i changes her strategy from state S to $S'$, choosing at most d new resources and improving her costs by at least a factor of $\beta \ge e^d$, we get:

$$\begin{aligned} \Phi (S')=\prod _{i\in N}c_i(S')<e^d\cdot \frac{1}{\beta }\prod _{i\in N}c_i(S)\le \prod _{i\in N}c_i(S)=\Phi (S). \end{aligned}$$

This implies that all $\beta$-improvement step sequences are finite. $\square$

We note that, though the approximation quality of $e^d$ is quite bad for large d, this result also shows that every circling best-response sequence in a singleton game, such as constructed in the proof of Theorem 7, must contain at least one step that decreases the cost of the performing player by less than a factor of e, if the applied cost functions are linear.

Linear functions are a special case of general polynomial functions. Our results can be extended to general polynomial cost functions of maximum degree g without negative coefficients. The cost of a resource increases at most by a factor of $\left( \frac{m+1}{m}\right) ^g$ if it is used by $m+1$ instead of m players. Using this, we can generalize Proposition 2 to $e^{d\cdot g}$-improvement steps:

Corollary 3

Let $\Gamma$ be a congestion game with mixed objectives with polynomial functions of degree at most g without negative coefficients. Let $d=max_{i\in N,S_i\in \Sigma _i}|S_i|$ be the maximal number of resources a player can choose. Then $\Gamma$ contains an $e^{d\cdot g}$-approximate pure Nash equilibrium and every sequence of $e^{d\cdot g}$-improvement steps from an arbitrary state in $\Gamma$ reaches an $e^{d\cdot g}$-approximate pure Nash equilibrium after a finite number of steps.

As last step we remove the limitations on the cost functions: Besides matroid games, we can show approximation factors which are independent of the structure of the strategy sets, but depend on either $\alpha$-uniform players or on equal cost functions:

Theorem 12

Let $\Gamma$ be a congestion game with mixed objectives. Let $d=\max _{i\in N, S_i\in \Sigma _i}|S_i|$ be the maximal number of resources a player can choose.

• 1. If $\Gamma$ is a matroid congestion game, then $\Gamma$ contains a d-approximate pure Nash equilibrium.

• 2. If the players are $\alpha$-uniform, then $\Gamma$ contains a d-approximate pure Nash equilibrium.

• 3. If $e_r=\ell _r$ for all resources $r\in R$, then $\Gamma$ contains a $\sqrt{d}$-approximate pure Nash equilibrium.

• 4. If the players are $\alpha$-uniform and $e_r=\ell _r$ for all resources $r\in R$, then $\Gamma$ contains a $\beta$-approximate pure Nash equilibrium for $\beta =\frac{d}{\alpha \cdot (d-1)+1}$.

Proof

• 1. The proof relies on the fact that PNE always exist in player-specific matroid congestion games (Ackermann et al. 2009). We define a player-specific congestion game $\Gamma '$ with the following cost functions: $c^i_r(S)=\alpha _i\cdot \ell _r(S)+(1-\alpha _i)\cdot e_r(S)$. We show that every PNE in $\Gamma '$ is a d-approximate pure Nash equilibrium in $\Gamma$. Since PNE always exist in matroid player-specific congestion games, the claim follows. We denote by $c_i(S)$ the costs of player i in state S in $\Gamma$, and by $c_i^p(S)$ the costs in $\Gamma '$. Let $S_i$ be a best-response strategy w. r. t. $S_{-i}$ in $\Gamma '$. Then we get for all strategies $S_i'\in \Sigma _i$:

  $$\begin{aligned} c_i(S_i',S_{-i})&=\alpha _i\cdot \sum _{r\in S_i'} \ell _r(S_i',S_{-i})+(1-\alpha _i)\cdot \max _{r\in S_i'}\ e_r(S_i',S_{-i})\\&\ge \alpha _i\cdot \sum _{r\in S_i'} \ell _r(S_i',S_{-i})+(1-\alpha _i)\cdot \frac{1}{d}\cdot \sum _{r\in S_i'}\ e_r(S_i',S_{-i})\\&\ge \frac{1}{d}\cdot c_i^p(S_i',S_{-i}) \ge \frac{1}{d}\cdot c_i^p(S_i,S_{-i})\ge \frac{1}{d}\cdot c_i(S_i,S_{-i}) \end{aligned}$$

• 2. We show that the function $\Phi (S)=\sum _{r\in R}\sum _{i=1}^{n_r(S)}\left( \alpha \cdot \ell _r(i)+(1-\alpha )\cdot e_r(i)\right)$ is a d-approximate potential function, i. e., its value decreases in every d-improvement step. Consider a state S and a player i who decreases her costs by a factor of more than d by deviating to the strategy $S_i'$:

  $$\begin{aligned}&\Phi (S'_i,S_{-i})-\Phi (S)\\&=\sum _{r\in R}\sum _{i=1}^{n_r(S')}\left( \alpha \cdot \ell _r(i)+(1-\alpha )\cdot e_r(i)\right) -\sum _{r\in R}\sum _{i=1}^{n_r(S)}\left( \alpha \cdot \ell _r(i)+(1-\alpha )\cdot e_r(i)\right) \\&\le \alpha \cdot \sum _{r\in S_i'}\ell _r(S')+(1-\alpha )\cdot \max _{r\in S_i'}e_r(S')+(1-\alpha )\\&\qquad \cdot \sum _{r\in S_i'}e_r(S')-(1-\alpha )\cdot \max _{r\in S_i'}e_r(S')\\&-\left( \alpha \cdot \sum _{r\in S_i}\ \ell _r(S)+(1-\alpha )\cdot \max _{r\in S_i}e_r(S)\right) \\&\le c_i(S')-c_i(S)+\sum _{r\in S_i'}(1-\alpha )\cdot e_r(S')-(1-\alpha )\cdot \max _{r\in S_i'}e_r(S')\\&\le c_i(S')-c_i(S)+(d-1)\cdot c_i(S')<c_i(S')-d\cdot c_i(S')+(d-1)\cdot c_i(S')=0 \end{aligned}$$

• 3. We show that $\Phi (S)=\sum _{r\in R}\sum _{i=1}^{n_r(S)}\ell _r(i)^2$ is a $\sqrt{d}$-approximate potential function. Consider a state S that is minimizing $\Phi$ and player i who deviates to the strategy $S_i'$. Note that $\Phi (S)-\Phi (S_i',S{-i})=\sum _{r\in S}\ell _r(S)^2-\sum _{r\in S'}\ell _r(S')^2.$ Hence, $\sum _{r\in S}\ell _r(S)^2\le \sum _{r\in S'}\ell _r(S')^2$.

  $$\begin{aligned} c_i(S_i',S{-i})&=\sum _{r\in S_i'}\alpha _i\cdot \ell _r(S')+(1-\alpha _i)\max _{r\in S_i'}\ell _r(S')\\&\ge \alpha _i\cdot \left( \sum _{r\in S_i'} \ell _r(S')^2\right) ^\frac{1}{2}+(1-\alpha _i)\cdot \left( \max _{r\in S_i'}\ell _r(S')^2\right) ^\frac{1}{2}\\&\ge \alpha _i\cdot \left( \frac{1}{\sqrt{d}}\cdot \sum _{r\in S_i}\ell _r(S)\right) +(1-\alpha _i)\cdot \left( \frac{1}{d}\cdot \left( \sum _{r\in S_i}\ell _r(S)^2\right) \right) ^\frac{1}{2}\\&\ge \frac{\alpha _i}{\sqrt{d}}\cdot \sum _{r\in S_i}\ell _r(S)+\frac{1-\alpha _i}{\sqrt{d}}\cdot \max _{r\in S_i}\ell _r(S)= \frac{1}{\sqrt{d}}\cdot c_i(S). \end{aligned}$$

• 4. We argue that $\Phi (S)= \sum _{r\in R}\sum _{i=1}^{n_r(S)}\ell _r(i)$ is an approximate potential function. If the latency and bottleneck cost functions are identical for each resource, we use the fact that the cost of the bottleneck resource is at least as high as the average latency cost, i. e., $\max _{r\in S_i}e_r(S)\ge \frac{1}{|S_i|}\sum _{r\in S_i}\ell _r(S)\ge \frac{1}{d}\sum _{r\in S_i}\ell _r(S),$ which implies $c_i(S)=\alpha \cdot \sum _{r\in S_i}\ell _r(S)+(1-\alpha )\cdot \max _{r\in S_i} \ell _r(S) \ge \left( \alpha +\frac{1-\alpha }{d}\right) \sum _{r\in S_i}\ell _r(S).$ Consider a state S and a player i who decreases her costs by a factor of more than $\beta =\frac{d}{\alpha \cdot (d-1)+1}$ by deviating to the strategy $S_i'$.

  $$\begin{aligned} \Phi (S_i',S_{-i})-\Phi (S)&\le c_i(S')-c_i(S)+\sum _{r\in S_i'}(1-\alpha )\cdot \ell _r(S')-(1-\alpha )\cdot \max _{r\in S_i'}\ell _r(S')\\&\le c_i(S')-c_i(S)+(1-\alpha )\cdot \left( 1-\frac{1}{d}\right) \cdot \sum _{r\in S_i'} \ell _r(S')\\&\le c_i(S')-c_i(S)+(1-\alpha )\cdot \left( 1-\frac{1}{d}\right) \cdot \frac{c_i(S')}{\alpha +\frac{1-\alpha }{d}}\\&=\left( 1+\frac{(1-\alpha )\cdot \frac{d-1}{d}}{\alpha +\frac{1-\alpha }{d}}\right) c_i(S')-c_i(S)\\&=\left( 1+\frac{d-1}{\alpha \cdot (d-1)+1}-1+\frac{1}{\alpha \cdot (d-1)+1}\right) c_i(S')-c_i(S)\\&=\frac{d}{\alpha \cdot (d-1)+1}c_i(S')-c_i(S)<0&\, \end{aligned}$$

  $\square$

We remark that the $\beta$ given in the fourth case of Theorem 12 is bounded from above by $\frac{1}{\alpha }$. However, if $\alpha$ is close to 0, the bound of $\sqrt{d}$ derived for general games with $\ell _r=e_r$ for all resources, but without restrictions on the preference values, may give a better approximation guarantee.

5 Conclusions

We studied a new class of games in which players seek to minimize the sum of latency costs, the maximum of bottleneck costs, or a combination thereof. The convex combination of the two existing and well-studied models was the first step to introduce a new more general model of congestion games. As a promising avenue for future work it would be interesting to consider other types of cost aggregation. This would be useful in scenarios with heterogeneous players with different interests in which the resources represent not only links in a network but also servers, routers, or any network functions in general.