Keywords

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

Understanding the impact of selfish behavior on the performance of a system is an important question in algorithmic game theory. One of the cornerstones of the substantial literature on this topic is the famous result of Roughgarden and Tardos [27]. They considered the traffic model of Wardrop [30] in a network with affine flow-dependent congestion cost functions on the edges. Given a set of commodities, each specified by a source node, a target node, and a flow demand, a Wardrop equilibrium is a multicommodity flow with the property that every commodity uses only paths that minimize the cost. For this setting, Roughgarden and Tardos proved that the total cost of an equilibrium flow is not worse than 4/3 times that of a system optimum. This ratio was coined the price of anarchy by Koutsoupias and Papadimitriou [19] who introduced it as a measure of a system’s performance degradation due to selfish behavior. A surprising consequence of the result of Roughgarden and Tardos is that the worst case price of anarchy in congested networks is attained for very simple single-commodity networks already considered a century ago by Pigou [23]. Pigou-style networks consist of only two nodes connected by two parallel links. In fact, Roughgarden [26] proved that for any set of cost functions, the price of anarchy is independent of the network topology as it is always attained for such simple Pigou-style networks where a feasible strategy of each commodity is to choose exactly one out of the two links.

A model related to Wardrop’s model is that of a congestion game with unsplittable (i.e., atomic) players. In such a game, there is a finite set of players and a strategy of each player is to choose a set of resources allowable to her. Without any restrictions on the strategy spaces, the price of anarchy for affine cost functions is 5/2 as shown by Christodoulou and Koutsoupias [9] and Awerbuch et al. [5]. As a contrast, for simple Pigou-style instances with symmetric and singleton strategies, Lücking et al. [20] showed that the price of anarchy is only 4/3. These results imply that for atomic congestion games the price of anarchy does depend on the combinatorial structure of players’ strategies.

In this work, we shed new light on the impact of the combinatorial structure of strategy spaces on the inefficiency of equilibria in atomic congestion games. Specifically, we focus on the minimum combinatorial structure that one may think of, namely symmetric k-uniform congestion games where the strategy set of each player consists of all k-elementary subsets of resources. These games are a natural generalization of the singleton case, and we consider it interesting because it constitutes a first step into the direction where strategies are bases of a (general) matroid. As for potential applications, one may think of, e.g., load balancing games where each player controls the same amount of jobs; see also Abed et al. [1] for a related model in the context of coordination mechanisms.

Our Results. We prove that the price of anarchy in congestion games with affine cost functions is at most 28/13 when strategy spaces are symmetric and bases of a k-uniform matroid. The proof uses in its core several combinatorial arguments on the amount and cost of resources that are over- respectively under-demanded in any given Nash equilibrium as opposed to an optimal solution. It also exploits the affinity of the cost functions, along the lines of earlier arguments of Fotakis [12] for the singleton case. The main point of the technical side of the paper is the insight that the combinatorial structure of strategy spaces, here of the simplest possible form, allows to furnish combinatorial arguments that yield improved results on the price of anarchy. We are not aware of earlier attempts in this direction, and believe this opens new possibilities for our understanding of a “classical” showcase problem in algorithmic game theory. We also show that the price of anarchy for the k-uniform matroid case cannot be the same as for singleton congestion games, as we bound it away from 4/3: For affine cost functions, and k large enough, the price of anarchy is at least 1.343. For \(k=5\) it is at least \(47/35 \approx 1.3428\).

Related Work. Since the early works of Pigou [23], Beckman et al. [6], and Braess [7] it is well known that user equilibria in congested networks may be suboptimal for the overall performance of the system. In order to quantify this inefficiency, Koutsoupias and Papadimitriou [19] proposed to study the ratio of the total cost of an equilibrium and the total cost of an optimal solution. This ratio is now known as the price of anarchy. Roughgarden and Tardos [27] showed that the price of anarchy for non-atomic games with affine costs is 4/3. The worst case is attained for simple networks of two parallel links previously studied by Pigou [23]. Roughgarden [26] gave a closed form expression for the price of anarchy for arbitrary cost functions which is again attained for Pigou-style networks, e.g., for polynomials with positive coefficient and maximum degree d the price of anarchy is of order \(\varTheta (d/\ln (d))\).

Awerbuch et al. [5] and Christodoulou and Koutsoupias [9] considered the related model with atomic players that was introduced by Rosenthal [24]. They showed that for affine cost functions the price of anarchy is 5 / 2. Aland et al. [4] gave tight bounds on the price of anarchy for polynomial cost functions with maximum degree d which behaves asymptotically as \(\varTheta ((d/\ln d)^{d+1})\). It is interesting to note that these worst-case bounds are not attained for simple Pigou-style networks with symmetric and singleton strategies as in the non-atomic case. Based on previous work of Suri et al. [28], Caragiannis et al. [8] showed that for affine costs, the worst case is attained for asymmetric singleton strategies. For a similar result for polynomial costs, see Gairing and Schoppmann [15]. In fact, for singleton games with symmetric strategies, the price of anarchy is considerably better than in the general case. In fact, Fotakis [12] showed that the price of anarchy of symmetric singleton atomic games is equal to the price of anarchy of non-atomic games. This improves and generalizes previous bounds by Lücking et al. [20] and Gairing et al. [14].

The class of k-uniform games that we consider in this paper is also related to the class of integer-splittable congestion games introduced by Rosenthal [25] and the classes of k-splittable and integer k-splittable congestion games studied by Meyers [21]. In contrast to our model, the models above allow that a player uses a resource with multiple units of demand at the same time. It turns out that allowing for this kind of self-congestion has a severe impact on the existence of pure Nash equilibria [11, 25] but for networks of parallel links it is known that pure Nash equilibria are guaranteed to exist [17, 29].

The impact of combinatorial structure on the existence and computability of pure Nash equilibria has been studied for many variants of congestion games. Ackermann et al. [2] proved that for atomic games with unweighted players all sequences of best replies converge in polynomial time to a pure Nash equilibrium if the set of strategies of each player corresponds to the set of bases of a matroid. For weighted congestion games, the matroid property guarantees the existence of a pure Nash equilibrium [3] while without that property a pure Nash equilibrium may fail to exist [16]. Similarly, congestion games with player-specific costs and matroid strategies have a pure Nash equilibrium which can be computed efficiently [3] which is in contrast to the general case [22]. For similar results in the context of resource buying games, see also Harks and Peis [18].

To the best of our knowledge, the impact of matroid structures on the efficiency of Nash equilibria has not been considered before. The only result in this direction is a yet unpublished work of Fujishige et al. [13]. They showed that Braess’ paradox cannot occur in non-atomic games with matroid strategies, i.e., the quality of the user equilibrium cannot deteriorate when removing a resource. This result, however, has no consequences for the inefficiency of equilibria in non-atomic games since the worst case is attained for Pigou-style networks where the strategies are symmetric and 2-uniform matroids.

2 Preliminaries

Let \(N = \{1,\dots ,n\}\) be a finite set of players and let R be a finite set of resources. Each player i is associated with a set of subsets of resources \({ S}_i \subseteq 2^R\) allowable to her. A strategy of a player is to choose a subset \({ s}_i \in { S}_i\) from this set. A strategy vector \({ s} = ({ s}_i)_{i \in N}\) consists of n strategies, one for each player. Every resource r is endowed with a cost function \(c_r : \mathbb {N}\rightarrow \mathbb {R}\) that maps the total number of its users \(x_r = |\{i \in N : r \in s_i\}|\) to a cost value \(c_r(x_r)\). The cost functions \(c_r\) are called affine if \(c_r(x_r)=\alpha _r+\beta _rx_r\), for constants \(\alpha _r,\beta _r\ge 0\), \(r\in R\). The private cost of player i in strategy vector s is then defined as

$$\begin{aligned} \pi _i({ s})&= \sum _{r \in { s}_i} c_r(x_r). \end{aligned}$$

We use standard game theory notation; for a strategy vector \({ s} \in { S} = { S}_1 \times \dots \times { S}_n\), a player i and an alternative strategy \(s'_i \in { S}_i\), we denote by \((s'_i, { s}_{-i})\) the strategy vector in which all players play as in s except for i who plays \(s'_i\). A strategy vector s is a Nash equilibrium if,

$$\begin{aligned} \pi _i({ s})\le \pi _i(s'_i,{ s}_{-i}) \quad \text {for all}\,i \in N\,{\text {and}}\,s'_i \in { S}_i. \end{aligned}$$

Given an instance of a game \(I = (N,R,{ S},(c_r)_{r \in R})\), we denote the set of Nash equilibria of I by \( S^{\mathsf {NE}}(I)\).

We are interested in how restrictions on the set of strategies of each player influence the inefficiency of equilibria. We measure the efficiency of a strategy vector \({ s} \in { S}\) in terms of the social costs C( s) defined as

$$\begin{aligned} C({ s}) = \sum _{i \in N} \pi _i({ s}). \end{aligned}$$

We denote by \( S^{\mathsf {OPT}}(I)\) the set of strategy vectors s that minimize C(s). For an instance I of a game, the price of anarchy is defined as

$$\begin{aligned} \mathsf {PoA}(I) = \max \nolimits _{ s^{\mathsf {NE}}\in S^{\mathsf {NE}}(I)}\frac{C( s^{\mathsf {NE}})}{C( s^{\mathsf {OPT}})}, \end{aligned}$$

where \( s^{\mathsf {OPT}}\in S^{\mathsf {OPT}}(I)\) is a strategy vector minimizing C. For a class \(\mathcal {G}\) of games, the price of anarchy is defined as \(\mathsf {PoA}(\mathcal {G}) = \sup \nolimits _{I \in \mathcal {G}}\mathsf {PoA}(I)\). We drop \(\mathcal {G}\) whenever it is clear from context. We are specifically interested in singleton and k-uniform matroid strategy spaces. A game is said to be a singleton game, if \(|{ s}_i| = 1\) for all \({ s}_i \in { S}_i\) and \(i \in N\). A game is called k-uniform game if for each player, there is a subset \(R_i \subseteq R\) such that \({ S}_i = \{ { R'} \subseteq R_i : |{ R'}| = k \}\). A game is called symmetric, if \({ S}_i = { S}_j\) for all \(i,j \in N\).

3 Symmetric k-uniform Games

The main result of this paper is the following.

Theorem 1

The price of anarchy of symmetric k-uniform congestion games with affine cost functions is at most \(\frac{28}{13} \approx 2.15\).

For the proof of Theorem 1, we are going to prove that \(C( s^{\mathsf {NE}}) \le \frac{28}{13}\) \(C( s^{\mathsf {OPT}})\) for any given worst-case Nash equilibrium \( s^{\mathsf {NE}}\) and optimal solution \( s^{\mathsf {OPT}}\), of an arbitrary instance I of a symmetric k-uniform congestion game. For the remainder of this section, fix an instance I, a worst-case Nash equilibrium \( s^{\mathsf {NE}}\) and a system optimal solution \( s^{\mathsf {OPT}}\).

To gain some intuition on congestion games with k-uniform matroid strategies, let us first consider the following example of a k-uniform congestion game that will serve as a running example throughout this section. Even though it has only a moderate price of anarchy of 16/14, it showcases the crucial structures that we exploit later in this section when proving Theorem 1.

Fig. 1.
figure 1

A symmetric 4-uniform congestion game with seven resources. The height of the stack of each resource corresponds to its cost, e.g., resource 1 is used by players 1, 2 and 3 both in \( s^{\mathsf {NE}}\) and \( s^{\mathsf {OPT}}\) and the corresponding cost is 1; resource 3 is used by players 1 and 2 in \( s^{\mathsf {OPT}}\) and the corresponding cost is 2.

Full size image

Example 1

Consider the symmetric 4-uniform congestion game in Fig. 1. There are seven resources \(R = \{1,\dots ,7\}\). The first two resources have constant cost functions \(c_1(x) = c_2(x) = 1\) for all \(x \in \mathbb {N}\). The cost function of the other five resources is the identity, i.e., \(c_r(x) = x\) for all \(r \in \{3,\dots ,7\}\). There are three players whose strategy is to choose exactly 4 resources, i.e., \({ S}_i = \{{ R'} \subset R : |{ R'}| = 4\}\) for all \(i \in \{1,2,3\}\). In the system optimum, the two resources with constant costs are used by all players and each player chooses two of the remaining five resources, see the upper profile in Fig. 1. One of the resources with non-constant costs has to be used by two players leading to overall costs of 14. However, there is a Nash equilibrium, in which not all of the resources with constant costs are used by all players, see the lower profile in Fig. 1. This Nash equilibrium has a total cost of 16. The price of anarchy of this instance is \(16/14 \approx 1.14\).   \(\lhd \)

In order to derive bounds on the price of anarchy for the proof of Theorem 1, we bound the excess costs of the resources that are chosen by more players in the Nash equilibrium than in the system optimum in terms of the excess costs of the resources that are chosen by more players in the system optimum than in the Nash equilibrium. To this end, we denote by A the set of resources chosen by more players in \( s^{\mathsf {OPT}}\) than in \( s^{\mathsf {NE}}\), and by B the set of resources chosen by more players in \( s^{\mathsf {NE}}\) than in \( s^{\mathsf {OPT}}\), i.e.,

$$\begin{aligned} A&= \Bigl \{r \in R : x^{\mathsf {OPT}}_r > x^{\mathsf {NE}}_r\Bigr \}&\text { and }&B = \Bigl \{r \in R : x^{\mathsf {OPT}}_r < x^{\mathsf {NE}}_r\Bigr \}. \end{aligned}$$
(1)

Henceforth, we term the resources in A underloaded and the resources in B overloaded. For an illustration, see also Fig. 1 where the set of underloaded resources is \(A = \{2,3\}\) and the set of overloaded resources is \(B = \{4,5\}\).

As we show in the following lemma, it is sufficient to bound the excess costs of the resources in B in terms of the excess costs of the resources in A in order to bound the price of anarchy.

Lemma 1

For a symmetric k-uniform congestion game with affine cost functions and A and B as in (1), we have

$$\begin{aligned} \frac{3}{4}C( s^{\mathsf {NE}}) \le C( s^{\mathsf {OPT}})\!+\!\sum _{b\in B}\Bigl (x^{\mathsf {NE}}_b\!-\!x^{\mathsf {OPT}}_b\Bigr )c_b(x^{\mathsf {NE}}_b) \!-\!\sum _{a\in A}\Bigl (x^{\mathsf {OPT}}_a\!-\!x^{\mathsf {NE}}_a\Bigr )c_a(x^{\mathsf {NE}}_a\!+\!1). \end{aligned}$$
(2)

The proof is a rather straightforward generalization of a similar lemma due to Fotakis [12] for singleton games. It is contained in the full version of this paper [10].

In order to use Lemma 1 for the proof of Theorem 1, we are interested in bounding \(\sum _{b\in B}\bigl (x^{\mathsf {NE}}_b-x^{\mathsf {OPT}}_b\bigr )c_b(x^{\mathsf {NE}}_b) - \sum _{a\in A}\bigl (x^{\mathsf {OPT}}_a-x^{\mathsf {NE}}_a\bigr )c_a(x^{\mathsf {NE}}_a+1\bigr )\) in terms of \(C( s^{\mathsf {NE}})\). It is interesting to note that for symmetric singleton games, it holds that

$$\begin{aligned} c_r(x^{\mathsf {NE}}_r)&\le c_{r'}(x^{\mathsf {NE}}_{r'}+1) \end{aligned}$$
(3)

for all \(r,r' \in R\) by the Nash inequality. This implies in particular that

$$\begin{aligned} \sum _{b\in B}\bigl (x^{\mathsf {NE}}_b-x^{\mathsf {OPT}}_b\bigr )c_b(x^{\mathsf {NE}}_b) \le \sum _{a\in A}\bigl (x^{\mathsf {OPT}}_a-x^{\mathsf {NE}}_a\bigr )c_a(x^{\mathsf {NE}}_a+1\bigr ), \end{aligned}$$
(4)

which together with Lemma 1 implies an upper bound on the price of anarchy of 4/3. This is the road taken by Fotakis [12] in order to derive this bound.

However, neither inequality (3) nor inequality (4) hold in k-uniform congestion games due to the more complicated strategy spaces. E.g., for the Nash equilibrium \( s^{\mathsf {NE}}\) and system optimum \( s^{\mathsf {OPT}}\) in Fig. 1 we have

$$\begin{aligned} c_4(x^{\mathsf {NE}}_4) = 2&> c_2(x^{\mathsf {NE}}_2+1) =1, \end{aligned}$$

contradicting (3), as well as

$$\begin{aligned} c_4(x^{\mathsf {NE}}_4) + c_5(x^{\mathsf {NE}}_5) = 4&> 3 = c_2(x^{\mathsf {NE}}_2 + 1) + c_3(x^{\mathsf {NE}}_2+1), \end{aligned}$$

contradicting (4). More generally speaking, inequality (3) does not necessarily hold if all players choosing r in \( s^{\mathsf {NE}}\) also choose \(r'\). The main technical work in our proof of Theorem 1 is to derive an alternative upper bound for the right hand side in (2). Specifically, we will work towards showing that for k-uniform congestion games, we have

$$\begin{aligned} \sum _{b\in B}\bigl (x^{\mathsf {NE}}_b-x^{\mathsf {OPT}}_b\bigr )c_b(x^{\mathsf {NE}}_b) - \sum _{a\in A}\bigl (x^{\mathsf {OPT}}_a-x^{\mathsf {NE}}_a\bigr )c_a(x^{\mathsf {NE}}_a+1)\le \frac{2}{7} C( s^{\mathsf {NE}})\,. \end{aligned}$$
(5)

In order to show inequality (5), some further notation is necessary. A natural way of decomposing the cost of a strategy vector s is to consider the tuples (i, r) with the property that player i uses resource r in strategy s. One may think of such a tuple as a single unit of demand that player i places on resource r under strategy vector s. The cost of a unit of demand is equal to the cost of the corresponding resource under that strategy profile, and the cost of strategy profile is then equal to the sum of the costs of the units of demand. Let

$$\begin{aligned} P_A&\subseteq \bigl \{ (i,a) : a \in A, a \in s^{\mathsf {NE}}_i \bigr \} \end{aligned}$$

be a subset of the units of demand placed in \( s^{\mathsf {NE}}\) on the resources in A such that \(|\{(i,a) \in P_A\}| = x^{\mathsf {OPT}}_a - x^{\mathsf {NE}}_a\) for all \(a \in A\), i.e., for each resource \(a \in A\), \(P_A\) contains exactly as many units of demand as there are more on these resources in \( s^{\mathsf {OPT}}\) than in \( s^{\mathsf {NE}}\). Similarly, let

$$\begin{aligned} P_B&\subseteq \bigl \{ (i,b) : b \in B, b \in s^{\mathsf {OPT}}_i \bigr \} \end{aligned}$$

be such that \(|\{(i,b) \in P_B\}| = x^{\mathsf {NE}}_b - x^{\mathsf {OPT}}_b\) for all \(b \in B\).

Given these definitions, we want to bound the total costs of the units in \(P_B\) with respect to the total costs of the units in \(P_A\). We first identify a subset of these units, for which a simple bound can be obtained, i.e., we identify units of demand \((i,a) \in P_A\) and \((j,b) \in P_B\) such that \(c_b(x^{\mathsf {NE}}_b) \le c_a(x^{\mathsf {NE}}_a+1)\). For our purposes, it is sufficient to do this iteratively in a greedy way, see the greedy cancelling process in Algorithm 1.

figure a

Intuitively, this algorithm maps all units of demand in \(P_B\) whose cost are bounded by the cost of another unit in \(P_A\) and removes both units from the sets \(P_A\) and \(P_B\). In the following, we denote by \(P_A' \subseteq P_A\) and \(P_B' \subseteq P_B\) the set of units that survives this elimination. We denote by \(x'^{\mathsf {OPT}}_a\) and \(x'^{\mathsf {NE}}_b\) the number of units of demand that survive this elimination on each underloaded and overloaded resource respectively. Note that by definition of \(P_A\) and \(P_B\), we have that \(x'^{\mathsf {NE}}_b \ge x^{\mathsf {OPT}}_b\) for \(b\in B\), and \(x'^{\mathsf {OPT}}_a\ge x^{\mathsf {NE}}_a\) for \(a\in A\) after the cancelling.

Also note that during the course of the algorithm there may be different pairs \((i,a) \in P_A\) and \((j,b) \in P_B\) for which the condition in the if-loop is satisfied. For our following arguments it is irrelevant, which of these is removed from \(P_A\) and \(P_B\). Let

$$\begin{aligned} A'&= \{a \in A : \text { there is } (i,a) \in P_A' \text { for some } i \in N\}, \end{aligned}$$
(6a)
$$\begin{aligned} B'&= \{b \in B : \text { there is } (i,b) \in P_B' \text { for some } i \in N\} \end{aligned}$$
(6b)

be the resources that remain over- respectively underloaded in \( s^{\mathsf {NE}}\) as opposed to \( s^{\mathsf {OPT}}\) after the cancelling process. The following lemma then follows directly by definition of the above cancelling process and states that the cost of cancelled packets on B with respect to \(c_b(x^{\mathsf {NE}}_b)\) is bounded by the cost of the cancelled packets on A with respect to \(c_a(x^{\mathsf {NE}}_a+1)\).

Lemma 2

For a symmetric k-uniform congestion game with affine cost functions, A and B as in (1), and \(A'\) and \(B'\) as in (6), we have

$$ \sum _{b\in B} (x^{\mathsf {NE}}_b-x'^{\mathsf {NE}}_b)c_b(x^{\mathsf {NE}}_b) - \sum _{a\in A} (x^{\mathsf {OPT}}_a-x'^{\mathsf {OPT}}_a)c_a(x^{\mathsf {NE}}_a+1)\le 0\,. $$

For the following arguments, it may be helpful to consult Fig. 2 that shows the outcome of the cancelling process and the resulting sets \(A'\) and \(B'\) for the congestion game introduced in Example 1. Let us define

$$\begin{aligned} P = \{(i,r) : r \in R, r \in s^{\mathsf {NE}}_i\} \end{aligned}$$
(7)

as the set of all units of demand in \( s^{\mathsf {NE}}\). The next lemma is the first, crucial ingredient that allows us to obtain improved bounds on the price of anarchy. It states that for each “overloaded” unit of demand on a resource in \(P_B'\), there are “enough” other units on other resources. Subsequently, we also bound the cost of these other units. The proof of the lemma is deferred to the full version [10].

Lemma 3

For a symmetric k-uniform congestion game with affine cost functions, let P be as in (7) and let \((P_A',P_B')\) be the output of Algorithm 1. Then, \(|P \setminus P_B'| \ge 3|P_B'|\).

Fig. 2.
figure 2

Underloaded resources \(A = \{2,3\}\) and overloaded resources \(B = \{4,5\}\) for the game considered in Example 1. In the cancelling process one unit of demand of resource 4 cancelled out with a unit of demand of resource 3. After the cancelling process only resource 2 is underloaded and only resource 5 is overloaded, i.e., \(A'=\{2\}\) and \(B' = \{5\}\).

Full size image

Before we proceed, we provide two structural lemmas which restrict the space of instances with worst-case price of anarchy.

Lemma 4

The worst-case price of anarchy of symmetric k-uniform congestion games is attained on games that have the property that no resource is chosen by all players both in an optimal strategy vector and a worst-case Nash equilibrium.

The proof is by contradiction and can be found in the full version. The next lemma is a technical lemma specifically about the structure of worst-case instances with \(\mathsf {PoA}(I) \ge 4/3\). Again, the proof is given in the full version [10].

Lemma 5

For any instance I of a symmetric k-uniform congestion game with affine cost functions and \(\mathsf {PoA}(I) \ge 4/3\) and a resource \(r \in R\setminus B'\), chosen by all players in \( s^{\mathsf {NE}}\), there exists an instance \(\tilde{I}\), with resource r removed, such that \(\mathsf {PoA}(\tilde{I})\ge \mathsf {PoA}(I)\).

The restrictions on the structure of worst-case instances obtained in Lemma 5 will be used later in the proof of Theorem 1. Before we can do that, however, we proceed to bound the costs of the resources in \(A'\) with the following two lemmas.

Lemma 6

For a symmetric k-uniform congestion game with affine cost functions, we have \(c_r(x^{\mathsf {NE}}_r)\le 2 c_{r'}(x^{\mathsf {NE}}_{r'}+1)\) for any two resources \(r,r'\), where \(x^{\mathsf {NE}}_r\ge 1\) and \(x^{\mathsf {NE}}_{r'}<n\).

The proof is contained in the full version [10].

Lemma 7

For a symmetric k-uniform congestion game with affine cost functions, we have

$$ \sum _{b\in B'}(x'^{\mathsf {NE}}_b-x^{\mathsf {OPT}}_b)c_b(x^{\mathsf {NE}}_b)\le 2\sum _{a\in A'}(x'^{\mathsf {OPT}}_a-x^{\mathsf {NE}}_a)c_a(x^{\mathsf {NE}}_a+1)\,. $$

Proof

First recall that \(x^{\mathsf {NE}}_b\ge 1\) for all \(b\in B'\), and \(x^{\mathsf {NE}}_a<n\) for all \(a\in A'\) as resources in \(A'\subseteq A\) are chosen more often in \( s^{\mathsf {OPT}}\) than in \( s^{\mathsf {NE}}\). By Lemma 6, we can therefore conclude that \(c_b(x^{\mathsf {NE}}_b)\le 2c_{a}(x^{\mathsf {NE}}_{a}+1)\) for all resources \(b\in B'\) and \(a \in A'\). Summing over all units of demands in \(P_A'\) and \(P_B'\), respectively, yields the result. \(\square \)

We are now ready to prove our main result (Theorem 1).

Proof

(Proof of Theorem 1 ). By Lemma 3, for each unit of demand in \(P_B'\), there are three distinct units of demand in \( s^{\mathsf {NE}}\) on resources \(r\in R\setminus B'\). We bound the cost of each of these resource units from below by

$$\begin{aligned} c_r(x^{\mathsf {NE}}_r)\ge \frac{c_r(x^{\mathsf {NE}}_r+1)}{2} \ge \frac{c_b(x^{\mathsf {NE}}_b)}{4}\,, \end{aligned}$$
(8)

for any \(b\in B\). Here the first inequality follows directly from the fact that the cost functions are affine. The second inequality follows from Lemma 6 for resources r with \(x^{\mathsf {NE}}_r < n\). However, by Lemma 5, it is without loss of generality to assume that no resource \(r \in R \setminus B'\) is chosen by all players in \( s^{\mathsf {NE}}\), unless the price of anarchy is not larger than 4/3. Therefore, we finally get

$$\begin{aligned} \nonumber C( s^{\mathsf {NE}}) \ge&\sum _{b\in B'}(x'^{\mathsf {NE}}_b-x^{\mathsf {OPT}}_b)c_b(x^{\mathsf {NE}}_b) + \sum _{b\in B'} x^{\mathsf {OPT}}_b c_b(x^{\mathsf {NE}}_b) +\sum _{r\in R\setminus B'} x^{\mathsf {NE}}_r c_r(x^{\mathsf {NE}}_r)\\\nonumber \ge&\sum _{b\in B'}(x'^{\mathsf {NE}}_b-x^{\mathsf {OPT}}_b)c_b(x^{\mathsf {NE}}_b) +\sum _{r\in R\setminus B'} x^{\mathsf {NE}}_r c_r(x^{\mathsf {NE}}_r)\\ \ge&\frac{7}{4} \sum _{b\in B'}(x'^{\mathsf {NE}}_b-x^{\mathsf {OPT}}_b)c_b(x^{\mathsf {NE}}_b)\,. \end{aligned}$$
(9)

Here, the first inequality uses \(x'^{\mathsf {NE}}_b\le x^{\mathsf {NE}}_b\) for any resource \(b\in B\), which follows from the cancelling process. The last inequality uses that \(\sum _{b\in B'}(x'^{\mathsf {NE}}_b-x^{\mathsf {OPT}}_b)=|P_B'|\), and by Lemma 3, \(\sum _{r\in R\setminus B'} x^{\mathsf {NE}}_r \ge |P\setminus P_B'|\ge 3|P_B'|= 3\sum _{b\in B'}(x'^{\mathsf {NE}}_b-x^{\mathsf {OPT}}_b)\), and each of these resource units has cost at least \( c_b(x^{\mathsf {NE}}_b)/4\), for all \(b\in B\) by (8).

Combining (9) with Lemmas 2 and 7 yields

$$\begin{aligned}&\sum _{b\in B}(x^{\mathsf {NE}}_b-x^{\mathsf {OPT}}_b)c_b(x^{\mathsf {NE}}_b)-\sum _{a\in A}(x^{\mathsf {OPT}}_a-x^{\mathsf {NE}}_a)c_a(x^{\mathsf {NE}}_a+1)\\ \le&\sum _{b\in B'}(x'^{\mathsf {NE}}_b-x^{\mathsf {OPT}}_b)c_b(x^{\mathsf {NE}}_b)-\sum _{a\in A'}(x'^{\mathsf {OPT}}_a-x^{\mathsf {NE}}_a)c_a(x^{\mathsf {NE}}_a+1)\\ \le&\frac{1}{2}\sum _{b\in B'}(x'^{\mathsf {NE}}_b-x^{\mathsf {OPT}}_b)c_b(x^{\mathsf {NE}}_b) \ \le \ \frac{2}{7} C( s^{\mathsf {NE}})\,, \end{aligned}$$

where the first inequality is by Lemma 2, the second by Lemma 7, and the third by (9). Finally, plugging this into (2) proves Theorem 1.   \(\square \)

4 Lower Bound

We show that generalizing the strategy spaces from singletons to k-uniform matroids increases the price of anarchy of congestion games. The proof is by a parametric set of instances and contained in the full version [10].

Theorem 2

The price of anarchy of symmetric k-uniform congestion games with affine cost functions is at least \(7-4\sqrt{2}\approx 1.343\) for large enough k.

5 Conclusions

The most interesting open problem, next to improving lower and upper bounds for the k-uniform matroid case we study here, is to analyze the price of anarchy for the generalized problem with arbitrary matroid strategy spaces. We also note that larger lower bounds on the price of anarchy can be achieved for more general settings such as matroid strategy spaces, or non-affine cost functions. They are not included in this paper, however.