Congestion Games with Capacitated Resources

The players of a congestion game interact by allocating bundles of resources from a common pool. This type of games leads to well studied models for analyzing strategic situations, including networks operated by uncoordinated selfish users. Congestion games constitute a subclass of potential games, meaning that a pure Nash equilibrium emerges from a myopic process where the players iteratively react by switching to a strategy that diminishes their individual cost. With the aim of covering more applications, for instance in communication networks, we extend congestion games to the setting where every resource is endowed with a capacity which possibly limits its number of users. From the negative side, we show that a pure Nash equilibrium is not guaranteed to exist in any case and we prove that deciding whether a game possesses a pure Nash equilibrium is NP-complete. Our positive results state that congestion games with capacities are potential games in the well studied singleton case. Polynomial algorithms that compute these equilibria are also provided.

1. Recall that a resource r is saturated if n _r (σ) ≥ κ _r .

We thank the anonymous referees for their comments which lead to significant improvements of the manuscript.

Authors and Affiliations

1. LAMSADE, CNRS UMR 7243, Université Paris Dauphine, Paris, France

   Laurent Gourvès, Jérôme Monnot & Stefano Moretti

2. IBISC, Université d’Evry Val d’Essonne, Évry, France

   Nguyen Kim Thang

Corresponding author

Correspondence to Laurent Gourvès.

This work is supported by French National Agency (ANR), project COCA ANR-09-JCJC-0066-01. A preliminary version of this work appeared in the proceedings of SAGT 2012 [19].

Appendix 1

Next discussion explains how the model introduced and studied in this article differs from player-specific congestion games [29].

Consider a congestion model with three players \({\mathcal {N}}=\{1,2,3\}\), two resources \(\mathcal {R}=\{r,s\}\), a symmetric strategic space \((\Sigma _{i}=\{\{r\},\{s\}\})_{i \in {\mathcal {N}}}\), and the delay of a resource equals the number of players using it. Consider the following player-specific congestion game with priorities. On both resources, players 2 and 3 have higher priority on player 1, precisely, π _r (2) = π _s (2) = π _r (3) = π _s (3) = 2 and π _r (1) = π _s (1) = 1. The corresponding congestion game with priorities is given in Table 2. Note that each triple (·,·,·) represents the costs of players where the costs of player 1, 2 and 3 correspond to the first, second and third element of the triple.

Now, on the same congestion model, consider all possible capacitated congestion games and the two strategy profiles σ = ({r},{r},{r}) and σ′=({r},{r},{s}). Whatever pos functions of resources r and s, if players’ costs in profile σ are (∞, 2, 2) then κ _r = 2. On the other hand, if players’ costs in profile σ′ are (∞, 1, 1), then it implies that κ _r = 1. Therefore it cannot be possible to obtain the outcomes corresponding to σ and σ′ of games shown in Table 2.

Besides, consider a congestion game with capacitated resources in which κ _r = 2, κ _s = 1 and pos _r (3) < pos _r (2) < pos _r (1), pos _s (3) < pos _s (2) < pos _s (1). We have that the costs of players in σ and σ′ are (∞, 2, 2) and (2, 2, 1), respectively. A congestion game with priorities in which players’ costs are (∞, 2, 2) necessarily gives the highest priority to both players 2 and 3. Therefore, the outcomes corresponding to σ′ is (∞, 1, 1). Hence, we have proved that neither of the two classes is included in the other.

However, a capacitated congestion game with two players and the same priorities over all resources can be seen as a player-specific congestion game [29]. Denote by i and j the two players of a capacitated congestion game with pos _r (i) < pos _r (j) and delay d _r for every resource r. It suffices to consider a player-specific congestion game with delay functions \({d^{i}_{r}}\) and \({d^{j}_{r}}\) such that \({d^{i}_{r}}=d_{r}\) for every resource r, \({d^{j}_{r}}=d_{r}\) for every resource r with capacity equal to 2, and \({d^{j}_{r}}(1)=d_{r}(1)\) and \({d^{j}_{r}}(2)=+\infty \) for every resource r with capacity equal to 1.

Appendix 2

No pure NE exists in the next example. Every resource’s delay is non-decreasing and all resources have the same priority order. Nevertheless the players have different strategy spaces.

There are two players (row and column) and three resources x, y and z. The strategy set of the row and column players are {{x},{y}} and {{x, y}, {z}}, respectively. Resource x has a capacity of 2, d _x (1) = 1 and d _x (2) = 3. Resource y has a capacity of 1 and d _y (1) = 0. Resource z has a capacity of 1 and d _z (1) = 2. Priority is always given to the column player.

Reprints and permissions