1 Introduction

This paper studies the quality of equilibria for games with two players that compete for a set of resources, when the cost (or congestion) on each resource is given by an affine function that depends on the total load of that resource. The games that we consider fall into a class of games known as weighted Rosenthal congestion games [20, 28]. As we address several variants of such games, before discussing our actual contribution, let us first define these different settings.

Problem Definition. There are two players denoted \(i=1,2\), and the possible actions of player i are given by admissible subsets \(\mathcal {A}_i \subseteq 2^R\) of a finite set of resources R. This includes so-called atomic network routing games, where the resources are edges E in a directed graph \(G=(V,E)\), and each player wants to establish a path between source and target vertices \(s_i,t_i\in V(G)\), so that the admissible actions of player i are the edge sets of the directed \((s_i,t_i)\)-paths. A congestion game is called symmetric if \(\mathcal {A}_1 = \mathcal {A}_2\). For network routing games, that means that all players have the same source and the same target.

We address two different game theoretic settings. In simultaneous games, both players choose their actions simultaneously, and the admissible actions \(\mathcal {A}_i\) of a player i are exactly the player’s strategies in the corresponding strategic form bimatrix game. We also consider sequential extensive form games where the players choose actions after each other, w.l.o.g. first player 1, then player 2. Here, the first player’s strategies are the actions \(\mathcal {A}_1\), and a strategy for the second player consists of one action from \(\mathcal {A}_2\) for each possible strategy (\(=\) action) of the first player. In both cases, the game results in an outcome where both players have chosen one action, denoted action profile \(A=(A_1,A_2)\), where \(A_i\in \mathcal {A}_i\).

The players have to pay for each resource \(r\in R\) that they choose, and the cost of a resource \(r\in R\) depends on its load, which again depends on the set of players using it. In the unweighted version of the problem, the load \(x_r\) of a resource r equals the number of players using it, and the game is a potential game [22, 28]. In the weighted version of the problem, each player i has a player-specific weight \(w_i\), and the load \(x_r\) of a resource \(r\in R\) equals the total weight of the players that have chosen it. So if \(A=(A_1,A_2)\) is an action profile, the load of a resource \(r\in R\) equals \(x_r(A)=\sum _{i| r\in A_i} w_i\). When \(w_1=w_2\), this corresponds to the unweighted version (possibly after scaling).

Throughout the paper, we assume that the cost function for each resource r is an affine function in its load \(x_r\), with non-negative coefficients. That is, for each resource \(r \in R\), there are non-negative reals \(\alpha _r \ge 0\) and \(\beta _r \ge 0\), and with \(x_r\) being the total load of resource r, the cost of resource r equals \(\alpha _r + \beta _r x_r\).

For weighted congestion games, two different cost functions appear in the literature, under different names. We here follow the nomenclature as used in [15]. The first class of cost functions is uniform costs [10, 11, 15, 16, 21, 26], where the cost of a resource can be thought of as a delay or latency (as, e.g., in traffic), which is the same for all players choosing that resource, so that each player pays the costs for the loads of all chosen resources. That means that an action profile \(A=(A_1,A_2)\) yields as cost for player i

$$\begin{aligned} C_i^{\text {uni}}(A) {:}{=}\sum _{r \in A_i} (\alpha _r + \beta _r \sum _{j:\, r \in A_j} w_j)\,. \end{aligned}$$
(1)

The second class of cost functions is proportional costs [13, 15], where the cost of a resource can be thought of as as per-unit cost, and each player pays proportionally to the load that the player imposes on a resource. Then, an action profile \(A=(A_1,A_2)\) yields as cost for player i

$$\begin{aligned} C_i^{\text {prop}}(A) {:}{=}w_i \sum \limits _{r \in A_i} (\alpha _r + \beta _r \sum \limits _{j :\, r \in A_j} w_j). \end{aligned}$$
(2)

In the following we also use \(C_i(\,\cdot \,)\) to denote either of the two cost functions. Note that the cost functions agree in the (unweighted) case when \(w_1 = w_2 = 1\).

Equilibria. For simultaneous games, a strategy profile \(({A_1^{\text {equi}}}, {A_2^{\text {equi}}})\) is a (pure) Nash equilibrium [23, 24] if none of the players can improve unilaterally, i.e.,

$$\begin{aligned} C_1({A_1^{\text {equi}}},{A_2^{\text {equi}}})&\le C_1(A_1,{A_2^{\text {equi}}}){} & {} \forall A_1 \in \mathcal {A}_1, \end{aligned}$$
(3a)
$$\begin{aligned} C_2({A_1^{\text {equi}}},{A_2^{\text {equi}}})&\le C_2({A_1^{\text {equi}}},A_2){} & {} \forall A_2 \in \mathcal {A}_2. \end{aligned}$$
(3b)

Since we assume that the cost functions per resource are affine, the existence of pure Nash equilibria is guaranteed [14].

For sequential games, let us assume w.l.o.g. that the players choose their actions in the order 1, and then 2. The first player then has strategy set \(\mathcal {A}_1\). A strategy of the second player can be written as a tuple of length \(|\mathcal {A}_1|\), specifying the response of player 2 to any possible strategy of player 1.

Since we consider full information games, in equilibrium both players can choose a (pure) strategy that minimizes the player’s cost. For player 2 that means, if \(A_1\) is chosen by player 1, to choose any \({A_2^{\text {equi}}}\) so that

$$ C_2(A_1,{A_2^{\text {equi}}}) \le C_2(A_1,A_2) \text { for all } A_2 \in \mathcal {A}_2. $$

If we denote by \({A_2^{\text {equi}}}(A_1)\), \(A_1\in \mathcal {A}_1\), such an equilibrium strategy for player 2, player 1 chooses any strategy \({A_1^{\text {equi}}}\) so as to minimize her cost, that is,

$$ C_1({A_1^{\text {equi}}},{A_2^{\text {equi}}}({A_1^{\text {equi}}})) \le C_1(A_1,{A_2^{\text {equi}}}(A_1)) \text { for all } A_1 \in \mathcal {A}_1. $$

All pairs of strategies \(({A_1^{\text {equi}}},{A_2^{\text {equi}}}({A_1^{\text {equi}}}))\) that fulfill both conditions are precisely the (pure) subgame-perfect equilibria [30] for the sequential, extensive form game. For the full information games considered here, (pure) subgame perfect strategies exist and can easily be computed by the “procedure” as sketched above, known as backward induction [27]. A subgame perfect equilibrium yields as outcome an action profile \(({A_1^{\text {equi}}}, {A_2^{\text {equi}}})\). It is well known that, even for network routing games, subgame perfect outcomes need not be a Nash equilibrium in the corresponding simultaneous game [8], which is one of the difficulties in analyzing subgame-perfect equilibria.

Price of Anarchy. It is well known that if players choose their actions \(A=(A_1,A_2)\) selfishly while only considering their own cost functions \(C_i(A)\), there may be outcomes that are stable with respect to either Nash or subgame-perfect equilibrium, but that solution need not minimize the cost of both players together \(C(A):=C_1(A)+C_2(A)\). The price of anarchy [18] measures these negative effects of selfish behaviour. It is defined as the maximum cost of an equilibrium outcome, relative to the cost of the so-called social optimum, which is an action profile that minimizes total cost. Formally, for a given instance I of a weighted congestion game, if we define \(\mathcal {A}^{\text {equi}}(I)\) as the set of action profiles that may result as outcome from some equilibrium, and \(A^{\text {opt}}(I)\) as a social optimum, so any profile that minimizes total costs \(C(\,\cdot \,)\), the price of anarchy is

$$\begin{aligned} PoA (I) {:}{=}\max _{A \in \mathcal {A}^{\text {equi}}(I)} \frac{C(A)}{C(A^{\text {opt}}(I))} . \end{aligned}$$

For sequential games, the maximum is also taken over all possible orders of the players. The price of anarchy for a class of games is the supremum of \(PoA (I)\) over all instances I of that class. For sequential games, the price of anarchy has also been called the sequential price of anarchy [25]; it has been analyzed in several settings [3, 9, 17, 25].

Table 1. Known results and improvements for lower bounds (lb) and upper bounds (ub) on the price of anarchy for weighted simultaneous congestion games with two players. The first columns indicate restriction ( ) to network or symmetric games or no restriction ( ), as well as the cost function. In the first column, “  ” indicates that the upper bound holds in general, while the lower bound is attained even for network routing games. Bounds are underlined if the gap between lower and upper bound is closed. Empty cells indicate that there was no old bound or that there is no new bound.
Full size table

Contribution and Known Results. This paper gives the exact price of anarchy results for several classes of weighted two-player congestion games with respect to Nash equilibria for simultaneous games, and subgame-perfect equilibria for sequential games. We further distinguish between arbitrary congestion games and network routing games, uniform and proportional cost functions, as well as symmetric and asymmetric games. This gives rise to 16 different classes of two-player games. An overview of previously known bounds as well as new ones presented in this paper can be found in Tables 1 and 2. The tables also contain the previously known results for the special case of unweighted congestion games (if known).

Table 2. Known results and improvements on the price of anarchy for weighted sequential congestion games with two players.
Full size table

We not only give the worst-case bounds, but also prove the exact price of anarchy bounds parametric in the weight ratio \(w_1/w_2\) of the two players, which provides additional insight. Figure 1 depicts these findings.

Fig. 1.
figure 1

Price of anarchy for different types of weighted affine two-player congestion games depending on the weight ratio \(w_1 / w_2\). No graphs are shown for sequential games with symmetric strategy spaces, as tight lower bound instances are not known.

Full size image

Our results close a gap in the existing literature on the analysis of equilibria for affine congestion games. Let us therefore briefly discuss what is known.

The price of anarchy for unweighted affine congestion games with an arbitrary number of players is known to be bounded from above by 5/2 [1, 7]. This bound is tight for \(n\ge 3\) players [7]. For unweighted two-player games, the tight bound is 2 [7]. The 5/2 upper bound improves to \((5n-2)/(2n+1)\) for symmetric games with n players [7], which is tight even in the class of network routing games [8]. For non-symmetric, unweighted and affine congestion games, the bound 5/2 is tight (for \(n\rightarrow \infty \)) even for singleton congestion games, where each player chooses a single resource only, i.e., \(|A_i|=1\) for all \(A_i\in \mathcal {A}_i\) [6]. For unweighted and affine singleton congestion games that are symmetric, so when each player can choose every single resource, the price of anarchy equals 4/3 [19]. This singleton model can also be interpreted as a network routing model with parallel source-sink arcs, and is also dubbed the parallel link model, see e.g. [29].

For weighted affine congestion games, the price of anarchy with an arbitrary number of players is slightly larger than 5/2; it equals \(1\,+\,\phi \) with \(\phi =(1+\sqrt{5})/2\approx 1.618\) being the golden ratio [1]. This is again tight for \(n\ge 3\) players [2]. Here, we are not aware of improved bounds for special cases or with two players.

For the sequential version of unweighted, affine congestion games, it is known that the (sequential) price of anarchy equals 1.5 for two players [17], it equals \(1039/488\approx 2.13\) for \(n=3\) players [17], and for \(n=4\) players it equals \(28679925/10823887 \approx 2.65\) [4]. Moreover, for symmetric network routing games and two players, it equals 1.4 [8], while it can be as large as \(\Omega (\sqrt{n})\) for an arbitrary number n of players [8].

The above summary suggests that the potential loss of efficiency caused by selfish players in affine congestion games is by now pretty well understood. Yet the two-player case is a fundamental base case, and it does not seem to be well understood when the two players are not identical, i.e., the weighted case. Our results exhibit how the attributes of the game, such as symmetry of strategies, proportionality of costs, or sequentiality, have effects on the price of anarchy, which we believe are interesting and not obvious. It is conceivable that comparable results can be expected for congestion games with more than two players. However, extending our approach to, say, the case with three players, although theoretically possible, seems to be tedious.

As to the technical approach and contribution of this paper, all our results take as starting point a compact linear programming based idea to compute the cost functions of worst-case instances that extends the one used for unweighted congestion games in [17]. The linear program computes the parameters of all resource cost functions for the finite worst case instance, which can be done because it can be proved that such finite worst-case instances must exist [9, 17]. However for weighted games this can only be done for any fixed pair of weights \(w_1,w_2\). Doing this for several weight ratios \(w_1/w_2\), however, one can produce “educated guesses” for the dependence of the cost parameters on the weights, and the same can be done for the corresponding optimal dual solution. The so derived expressions for primal and dual solutions can finally be turned into algebraic proofs for a matching upper bound on the price of anarchy. This primal-dual procedure is somewhat mechanical, yet non-trivial. Note that this approach is reminiscent of the primal-dual technique as suggested in [2], however here we work with a different linear programming formulation.

Outline. We present our results on the price of anarchy for simultaneous, symmetric simultaneous and sequential games in Sect. 2. Our methodology is explained in Sect. 3 and a few concluding remarks are made in Sect. 4.

2 Results

The main results of this paper are best summarized and illustrated in Fig. 1, which displays the exact price of anarchy bounds in dependence on the weight ratio \(w_1/w_2\) for six different cases. This section supports this illustration: The subsequent Theorems 1–7 give the exact price of anarchy bounds in dependence on the players’ weights \(w_1\) and \(w_2\). Corollaries are obtained by taking the supremum over all feasible weight pairs \(w_1,w_2\), where “weight ratios” refers to the ratios \(w_1/w_2\) or \(w_2/w_1\), respectively. Corresponding worst-case instances as well as proofs can be found in the full version of our paper [5].

Theorem 1

(uniform, simultaneous, specific weights). Let \(w_1, w_2 \ge 0\) with \(w_1 + w_2 > 0\). The price of anarchy for simultaneous uniformly weighted two-player congestion/network routing games with weights \(w_1, w_2\) is equal to

$$ 1 + \frac{ 2w_1w_2 + \max (w_1,w_2)^2 }{ w_1^2 + w_1w_2 + w_2^2 }. $$

Corollary 1

(uniform, simultaneous). The price of anarchy for simultaneous uniformly weighted two-player congestion/network routing games is equal to \(1 + 2/\sqrt{3} \approx 2.155\), which is attained for weight ratios equal to \(1 + \sqrt{3} \approx 2.732\).

Theorem 2

(proportional, simultaneous, specific weights). Let \(w_1, w_2 \ge 0\) with \(w_1 + w_2 > 0\). The price of anarchy for simultaneous proportionally weighted two-player congestion/network routing games with weights \(w_1, w_2\) is equal to

$$\begin{aligned} 1 + w_1w_2 \frac{ w_1 + w_2 + \max (w_1,w_2) }{ w_1^3 + w_2^3 + w_1w_2 \min (w_1, w_2) }. \end{aligned}$$

Corollary 2

(proportional, simultaneous). The price of anarchy for simultaneous proportionally weighted two-player congestion/network routing games is approximately 2.0411, which is attained for weight ratios \(\approx 1.2704\).

For the next case we have an irrational weight ratio at which the behavior changes. We denote it by \(\tau {:}{=}\frac{1}{3} (2 \root 3 \of { 62 - 3\sqrt{183} } + \root 3 \of { 62 + 3\sqrt{183} } ) \approx 3.1527\).

Theorem 3

(uniform, symmetric, simultaneous, specific weights). Let \(w_1, w_2 \ge 0\) with \(w_1 + w_2 > 0\). The price of anarchy for symmetric simultaneous uniformly weighted two-player congestion games with weights \(w_1, w_2\) is equal to

  1. (a)

    \(\frac{3w_1^3 + 9w_1^2w_2 + 9 w_1w_2^2 + 3w_2^2}{ 2w_1^3 + 5w_1^2w_2 + 5w_1w_2^2 + 2w_2^3 + w_1 w_2 \min (w_1,w_2) }\) if \(\frac{1}{2}w_2 \le w_1 \le 2w_2\),

  2. (b)

    \(\frac{2w_1^3 + 5w_1^2w_2 + 5w_1w_2^2 + 2w_2^3 + 3\max (w_1^2w_2 + w_1^3,w_1w_2^2 + w_2^3) }{2w_1^3 + 4w_1^2w_2 + 4w_1w_2^2 + 2w_2^3}\) if \(2w_2 \le w_1 \le \tau w_2\) or if \(\frac{1}{\tau } w_2 \le w_1 \le \frac{1}{2}w_2\).

  3. (c)

    \(\frac{2w_1^2 + 2w_1w_2 + 2w_2^2 }{ (w_1+w_2)^2 }\) if \(w_1 \ge \tau w_2\) or if \(w_1 \le \frac{1}{\tau } w_2\).

Corollary 3

(uniform, symmetric, simultaneous, congestion). The price of anarchy for symmetric simultaneous uniformly weighted two-player congestion games is equal to 2, attained for weight rations \(\rightarrow \infty \).

Our computed worst case instances for which the price of anarchy approaches its supremum are no network routing games. However, there is a family of network routing games for which the price of anarchy also approaches 2, although slower than that for congestion games.

Theorem 4

(uniform, symmetric simultaneous, network routing). The price of anarchy for symmetric simultaneous uniformly weighted two-player network routing games is equal to 2.

Also for proportional cost functions and symmetric games we have an irrational weight ratio at which the behavior changes. It is the unique real root \(\sigma \) of the polynomial \(x^4 - 3x^2 - 3x - 1\) and is approximately \(\sigma \approx 2.14790\).

Theorem 5

(proportional, symmetric, simultaneous, specific weights). Let \(w_1, w_2 \ge 0\) with \(w_1 + w_2 > 0\). The price of anarchy for symmetric simultaneous proportionally weighted two-player congestion/network routing games with weights \(w_1, w_2\) is equal to

  1. (a)

    \(\frac{ 2w_1^4 + 6w_1^3w_2 + 8w_1^2w_2^2 + 6w_1w_2^3 + 2w_2^4 }{ 2w_1^4 + 3w_1^3w_2 + 4w_1^2w_2^2 + 3w_1w_2^3 + 2w_2^4 + w_1w_2 \min (w_1^2,w_2^2) }\) if \(\frac{w_2}{\sigma } \le w_1 \le \sigma w_2\).

  2. (b)

    \(\frac{ 2w_1^3w_2 + 4w_1^2w_2^2 + 2w_1w_2^3 + 2\max (w_1^4+w_1^3w_2,w_1w_2^3+w_2^4) }{ w_1^3w_2 + 2w_1^2w_2^2 + 2w_1w_2^3 + w_2^4 + 2w_1w_2 \min (w_1^2,w_2^2) + \max (w_1^4,w_2^4) }\) if \(w_1 \ge \sigma w_2\) or \(w_1 \le \frac{w_2}{\sigma }\).

Corollary 4

(proportional, symmetric, simultaneous). The price of anarchy for symmetric simultaneous proportionally weighted two-player congestion/network routing games is \(\approx 1.6096\), attained for weight ratios \(\approx 1.1940\).

Theorem 6

(uniform, sequential, specific weights). Let \(w_1, w_2 \ge 0\) with \(w_1 + w_2 > 0\). The price of anarchy for sequential uniformly weighted two-player congestion/network routing games with weights \(w_1, w_2\) is equal to

  1. (a)

    \(1 + \frac{w_1}{w_1 + w_2}\) if \(w_2 \le w_1\),

  2. (b)

    \(1 + \frac{2w_1w_2}{2w_1^2 + w_1w_2 + w_2^2}\) if \(w_1 \le w_2 \le 2w_1\) and

  3. (c)

    \(1 + \frac{w_2}{2w_1+w_2}\) if \(w_2 \ge 2w_1\).

Note that the uniform, sequential case is the only case where the exact price of anarchy is not symmetric around the weight ratio 1.

Corollary 5

(uniform, sequential). The price of anarchy for sequential uniformly weighted two-player congestion games is equal to 2, attained for weight ratios \(\rightarrow \infty \).

Theorem 7

(proportional, sequential, specific weights). Let \(w_1, w_2 \ge 0\) with \(w_1 + w_2 > 0\). The price of anarchy for sequential proportionally weighted two-player congestion/network routing games with weights \(w_1, w_2\) is equal to

$$\begin{aligned} 1 + \frac{ w_1w_2 }{ w_1^2 + w_2^2 }. \end{aligned}$$

Corollary 6

(proportional, sequential). The price of anarchy for sequential proportionally weighted two-player congestion games is equal to 1.5, which is attained if and only if \(w_1 = w_2\) holds.

As symmetry cannot be handled by our approach for sequential games, a gap remains between the lower and upper bounds; see Table 2. We briefly discuss this issue in Sect. 3 preceding Theorem 8.

3 LP Based Proofs

First, observe that for fixed weights \(w_1\) and \(w_2\) the cost functions (1) and (2) are linear. The idea of computing the price of anarchy is greedy: we construct an LP for an instance of a game with a minimal set of actions \(\mathcal {A}\) that are required for a worst-case instance. The LP has as variables the cost parameters \(\alpha _r,\beta _r\) of the cost functions per resource \(r \in R\). This is finite, since as in [17] we can argue that by pigeonhole principle at most \(2^{|\mathcal {A}|}\) resources are needed for any such an instance: if two resources appear in precisely the same actions, then these could be combined into one (adding their costs), which yields an instance with fewer resources but the same price of anarchy. Given that the LP’s cost functions per resource are yet undetermined, one can w.l.o.g. “label” actions as social optimum and equilibrium, respectively. These labels are \(\mathcal {A}= \{ {A_1^{\text {opt}}}, {A_2^{\text {opt}}}, {A_1^{\text {equi}}}, {A_2^{\text {equi}}}\}\). For sequential games we extend \(\mathcal {A}\) by the label \({A_2^{\text {equi}'}}\) for an optimal action for player 2 after player 1 has played \({A_1^{\text {opt}}}\). The observation above justifies to view resources as subsets of labels, i.e., \(R = 2^{\mathcal {A}}\). Therefore, if \(r\in A\), we can also write \(A\in r\), as we view r as the set of all actions \(A\ni r\). In addition to the cost variables \(\alpha _r, \beta _r\) for each \(r \in R\) the LP has variables for the costs \(C_i(A_1,A_2)\) for \(i=1,2\) and for all labels \(A_j \in \mathcal {A}_j\) that are admissible for player \(j \in \{1,2\}\). We now introduce the constraints of the LP that ensure correctness of the labels and then prove that optimal solutions indeed correspond to worst-case instances. We start with the basic (but incomplete) LP:

$$\begin{aligned}&\text {max }&{ C_1({A_1^{\text {equi}}}, {A_2^{\text {equi}}}) + C_2({A_1^{\text {equi}}}, {A_2^{\text {equi}}}) } \end{aligned}$$
(4a)
$$\begin{aligned}&\text {s.t. }&C_1({A_1^{\text {opt}}},{A_2^{\text {opt}}}) + C_2({A_1^{\text {opt}}},{A_2^{\text {opt}}})&= 1 \end{aligned}$$
(4b)
$$\begin{aligned}{} & {} C_1(A_1,A_2) + C_2(A_1,A_2)&\ge 1&\qquad&\forall A_1 \in \mathcal {A}_1,~ \forall A_2 \in \mathcal {A}_2 \end{aligned}$$
(4c)
$$\begin{aligned}{} & {} \alpha _r,\beta _r&\ge 0{} & {} \forall r \in R \end{aligned}$$
(4d)

Note that the normalization of the social optimum to 1 via (4b) is without loss of generality since a value of 0 would also yield zero costs for each equilibrium. In case of uniform cost functions (1) we add

$$\begin{aligned} C_i(A_1,A_2)&= \sum _{ r \in R :\; A_i \in r} (\alpha _r + \beta _r \sum _{j : A_j \in r} w_j){} & {} \forall A_1 \in \mathcal {A}_1,~ \forall A_2 \in \mathcal {A}_2, ~i=1,2 \, , \end{aligned}$$
(5)

while in case of proportional cost functions (2) we add

$$\begin{aligned} C_i(A_1,A_2)&= w_i \sum _{ r \in R :\; A_i \in r} (\alpha _r + \beta _r \sum _{j : A_j \in r} w_j){} & {} \forall A_1 \in \mathcal {A}_1,~ \forall A_2 \in \mathcal {A}_2, ~i=1,2 \, . \end{aligned}$$
(6)

Simultaneous Games. For simultaneous games we need to add the Nash inequalities () to enforce that \({A_1^{\text {equi}}}\) and \({A_2^{\text {equi}}}\) form a Nash equilibrium. For general games we define \(\mathcal {A}_1{:}{=}\{ {A_1^{\text {opt}}}, {A_1^{\text {equi}}}\}\) and \(\mathcal {A}_2{:}{=}\{ {A_2^{\text {opt}}}, {A_2^{\text {equi}}}\}\), while for symmetric games we allow both players to use the union \(\mathcal {A}_1{:}{=}\mathcal {A}_2{:}{=}\{ {A_1^{\text {opt}}},{A_1^{\text {equi}}}, {A_2^{\text {opt}}}, {A_2^{\text {equi}}}\}\) of these actions.

Sequential Games. The following constraints model that \({A_2^{\text {equi}}}\) and \({A_2^{\text {equi}'}}\) are optimal actions for player 2 after player 1 has played \({A_1^{\text {equi}}}\) and \({A_1^{\text {opt}}}\), respectively, as well as the requirement that \({A_1^{\text {equi}}}\) is a subgame-perfect action for player 1:

$$\begin{aligned} C_2({A_1^{\text {equi}}},{A_2^{\text {equi}}})&\le C_2({A_1^{\text {equi}}},A_2){} & {} \forall A_2 \in \mathcal {A}_2, \end{aligned}$$
(7a)
$$\begin{aligned} C_2({A_1^{\text {opt}}},{A_2^{\text {equi}'}})&\le C_2({A_1^{\text {opt}}},A_2){} & {} \forall A_2 \in \mathcal {A}_2, \end{aligned}$$
(7b)
$$\begin{aligned} C_1({A_1^{\text {equi}}},{A_2^{\text {equi}}})&\le C_1({A_1^{\text {opt}}},{A_2^{\text {equi}'}}). \end{aligned}$$
(7c)

We thus define \(\mathcal {A}_1{:}{=}\{ {A_1^{\text {opt}}}, {A_1^{\text {equi}}}\}\) and \(\mathcal {A}_2{:}{=}\{ {A_2^{\text {opt}}}, {A_2^{\text {equi}}}, {A_2^{\text {equi}'}}\}\). Our approach does not work for symmetric sequential games. The reason is that if the actions from \(\mathcal {A}_2\) are available to player 1 as well, then for each of these actions we would need to introduce new actions for the subgame-perfect action of player 2 in such a case, which in turn would be available to player 1, and so on.

We now establish correctness of all variants of this LP.

Theorem 8

For fixed weights \(w_1,w_2 \ge 0\) with \(w_1 + w_2 > 0\) the LP () for the action sets \(\mathcal {A}_1,\mathcal {A}_2\) specified above, and extended by either (5) or (6) and by either () or () computes the price of anarchy for affine (sequential or simultaneous or symmetric simultaneous) congestion games with these specific weights.

Proof

Consider a class of games and an LP as defined in the theorem. It is straight forward to see that every primal solution of the LP actually represents a game and that the objective value is equal to its price of anarchy.

It remains to show that for every game there exists a primal solution of the LP such that its objective value is equal to the price of anarchy of that game. To this end, consider a game with resources \(\bar{R}\), actions \(\bar{\mathcal {A}_1},\bar{\mathcal {A}_2} \subseteq 2^{\bar{R}}\) for the two players as well as cost coefficients \(\bar{\alpha },\bar{\beta } \in \mathbb {R}^{\bar{R}}\). By scaling we can assume that the cost of the social optimum is equal to 1. We now create a mapping \(\pi \) from labels to the game’s actions. To this end, let \(\pi ({A_1^{\text {opt}}}) \in \bar{\mathcal {A}_1}\) and \(\pi ({A_2^{\text {opt}}}) \in \bar{\mathcal {A}_2}\) be actions that constitute a social optimum. Moreover, we consider an equilibrium (either Nash or subgame-perfect) for which the price of anarchy of this game is attained and let \(\pi ({A_1^{\text {equi}}}) \in \bar{\mathcal {A}_1}\) and \(\pi ({A_2^{\text {equi}}}) \in \bar{\mathcal {A}_2}\) constitute such an equilibrium. In the sequential case, let \(\pi ({A_2^{\text {equi}'}}) \in \bar{\mathcal {A}_2}\) be an action that is subgame-perfect for player 2 after player 1 has played \(\pi ({A_1^{\text {opt}}})\).

The mapping \(\pi \) of labels \(\mathcal {A}\) to actions \(\pi (\mathcal {A})\subseteq \bar{\mathcal {A}}\) identifies the “relevant” actions from \(\bar{\mathcal {A}}\). For any resource \(\bar{r}\in \bar{R}\), we can now associate with it the “incidence pattern” of the set of actions from \(\pi (\mathcal {A})\) in which \(\bar{r}\) is contained. This induces a reverse mapping \(\chi \) that maps each resource \(\bar{r} \in \bar{R}\) to the unique \(r \in R\) that has the same incidences. Formally, \(A \in \chi (\bar{r}) \iff \bar{r} \in \pi (A)\) must hold for all \(A \in \mathcal {A}\). This allows us to aggregate the resources \(\bar{R}\) accordingly via

$$\begin{aligned}{} & {} {}{} & {} \alpha _r&{:}{=}\sum _{\bar{r}\ :\ r= \chi (\bar{r})} \bar{\alpha }_{\bar{r}}&\text {and}{} & {} \beta _r&{:}{=}\sum _{\bar{r}\ :\ r= \chi (\bar{r})} \bar{\beta }_{\bar{r}} .{} & {} {}{} & {} \end{aligned}$$
(8)

By Eqs. (5) or (6), the values of the remaining variables are determined uniquely. Moreover, (8) ensures that for \(i=1,2\) and for any profile \((A_1,A_2) \in \mathcal {A}_1\times \mathcal {A}_2\), \(C_i(A_1,A_2)\) is equal to the cost of player i if actions \(\pi (A_1)\) and \(\pi (A_2)\) are played in the game. In particular, constraints (4b), (4c) as well as either () or () are satisfied. Consequently, the objective value corresponds to the price of anarchy of this game since the social optimum equals 1. Hence the value of the optimal LP solution equals the price of anarchy for the given class of games.    \(\square \)

Arbitrary Weights. In order to derive the price of anarchy for arbitrary weights, the LPs from Theorem 8 can be used as an auxiliary tool. First, an approximate version of Fig. 1 can be produced, from which we could guess intervals of weight ratios \(w_1/w_2\) for which the same LP basis is optimal. Second, for each such interval, several weight pairs are chosen and optimal primal and dual solutions are computed. Using the LP solver SoPlex, we computed exact rational solutions (see [12]), which helped to derive educated guesses for algebraic expressions.

Even though this procedure is the core of our contribution, due to space constraints we could not include it here. A concrete example of such a derivation can be found in the full version of our paper [5]. Here, we still mention two tricks that were important. First, cancellations in the expressions can be avoided by choosing prime numbers for the weights. Second, we observed that often several optimal solutions exist, which makes it hard to make an educated guess of the weight-dependent expression for each variable. We were able to circumvent this difficulty by forcing some of the cost variables to 0 while ensuring that optimality of the solution is maintained.

4 Concluding Remarks

One of the findings of our paper is the fact that the worst-cases for simultaneous games are attained for players’ weights that differ only slightly, and that sequential play reduces the price of anarchy irrespective of the players’ weights. While for simultaneous games the symmetry with respect to players implies that the prices of anarchy for weight ratios \(\lambda \) and \(1/\lambda \) are equal, no such implication holds for sequential games. Surprisingly, a different symmetry holds for sequential games with uniform costs, namely equality for weight ratios \(\lambda /2\) and \(1/\lambda \). As to methodology, the algebraic expressions for the price of anarchy are already quite complicated for two players, especially for symmetric simultaneous games. Hence, a similar analysis for the 3-player case seems to be out of reach.