Congestion game

Congestion games (CG) are a class of games in game theory. They represent situations which commonly occur in roads, communication networks, oligopoly markets and natural habitats. There is a set of resources (e.g. roads or communication links); there are several players who need resources (e.g. drivers or network users); each player chooses a subset of these resources (e.g. a path in the network); the delay in each resource is determined by the number of players choosing a subset that contains this resource. The cost of each player is the sum of delays among all resources he chooses. Naturally, each player wants to minimize his own delay; however, each player's choices impose a negative externality on the other players, which may lead to inefficient outcomes.

The research of congestion games was initiated by the American economist Robert W. Rosenthal in 1973. He proved that every congestion game has a Nash equilibrium in pure strategies. During the proof, he in fact proved that every congestion game is a potential game. Later research focused on questions such as:

• Does the existence of equilibrium extend to more general models of congestion games?
• What is the quantitative inefficiency of congesion games?
• What is the computational complexity of finding an equilibrium?

Example

The directed graph for a simple congestion game.

Consider a traffic net where two players originate at point $O$ and need to get to point $T$. Suppose that node $O$ is connected to node $T$ via two paths: $O$-$A$-$T$ and $O$-$B$-$T$, where $A$ is a little closer than $B$ (i.e. $A$ is more likely to be chosen by each player), as in the picture at the right.

The roads from both connection points to $T$ get easily congested, meaning the more players pass through a point, the greater the delay of each player becomes, so having both players go through the same connection point causes extra delay. Formally, the delay in each of $A$$T$ and $B$$T$ when $x$ players go there is $x^{2}$.

Good outcome in this game will be for the two players to "coordinate" and pass through different connection points. Can such outcome be achieved?

The following matrix expresses the costs of the players in terms of delays depending on their choices:

Cost Matrix

p2 p1	OAT	OBT
OAT	(5,5)	(2,3)
OBT	(3,2)	(6,6)

The pure Nash equilibria in this game are (OAT,OBT) and (OBT,OAT): any unilateral change by one of the players increases the cost of this player (note that the values in the table are costs, so players prefer them to be smaller). In this example, the Nash equilibrium is efficient - the players choose different lanes and the sum of costs is minimal.

In contrast, suppose the delay in each of $A$$T$ and $B$$T$ when $x$ players go there is $0.8x$. Then the cost matrix is:

Cost Matrix

p2 p1	OAT	OBT
OAT	(2.6,2.6)	(1.8,2.8)
OBT	(2.8,1.8)	(3.6,3.6)

Now, the only pure Nash equilibrium is (OAT,OAT): any player switching to OBT increases his cost from 2.6 to 2.8. An equilibrium still exists, but it is not effiicent: the sum of costs is 5.2, while the sum of cost in (OAT,OBT) and (OBT,OAT) is 4.6.

Basic result

Notation

The basic definition of a CG has the following components.

• A base set $E$ of congestible elements (also called resources or factors). In the above example, $E$ is the set of roads ($O$$A$, $A$$T$, $O$$B$ and $B$$T$).
• A set of $n$ players. In the above example $n=2$.
• A finite set of strategies $S_{i}$ for each player, where each strategy $P\in S_{i}$ is a subset of $E$.
  • In the above example, both players have the same set of strategies: $S_{1}=S_{2}=\{\{OA,AT\},\{OB,BT\}\}$. CGs in which all players have the same set of strategies are called symmetric.
  • In general, different players may have different sets, for example, if each player has a different source and/or a different target. Such CGs are called asymmetric.
• For each element $e\in E$ and a vector of strategies $(P_{1},P_{2},\ldots ,P_{n})$, the load is defined as $x_{e}=\#\{i:e\in P_{i}\}$.
• For each element $e\in E$ there is a delay function $d_{e}:\mathbb {N} \longrightarrow \mathbb {R}$. Given a vector of strategies, the delay on $e$ is $d_{e}(x_{e})$. Each $d_{e}$ is assumed to be positive and monotone increasing.
• Given a strategy $P_{i}$, player $i$ experiences delay $\textstyle \sum _{e\in P_{i}}d_{e}(x_{e})$; each player wants to minimize his delay.
• A Nash equilibrium is a vector of strategies $(P_{1},P_{2},\ldots ,P_{n})$ such that, for each player $i$, replacing $P_{i}$ with a different strategy $Q_{i}$ would not decrease the delay experienced by $i$.

Existence of Nash equilibria

Every CG has a Nash equilibrium in pure strategies. This can be shown by constructing a potential function that assigns a value to each outcome. Moreover, this construction will also show that iterated best response finds a Nash equilibrium. Define $\textstyle \Phi =\sum _{e\in E}\sum _{k=1}^{x_{e}}d_{e}(k)$. Note that this function is not the social welfare $\textstyle \sum _{e\in E}x_{e}d_{e}(x_{e})$, but rather a discrete integral of sorts. The critical property of a potential function for a congestion game is that if one player switches strategy, the change in his delay is equal to the change in the potential function.

Consider the case when player $i$ switches from $P_{i}$ to $Q_{i}$. Elements that are in both of the strategies remain unaffected, elements that the player leaves (i.e. $e\in P_{i}-Q_{i}$) decrease the potential by $d_{e}(x_{e})$, and the elements the player joins (i.e. $e\in Q_{i}-P_{i}$) increase the potential by $d_{e}(x_{e}+1)$. This change in potential is precisely the change in delay for player $i$, so $\Phi$ is in fact a potential function.

Now observe that any minimum of $\Phi$ is a pure Nash equilibrium. Fixing all but one player, any improvement in strategy by that player corresponds to decreasing $\Phi$, which cannot happen at a minimum. Now since there are a finite number of configurations and each $d_{e}$ is monotone, there exists an equilibrium.

The existence of a potential function has an additional implication, called the finite improvement property (FIP). If we start with any strategy-vector, pick a player arbitrarily, and let him change his strategy to a better strategy for him, and repeat, then the sequence of improvements must be finite (that is, the sequence will not cycle). This is because each such improvement strictly increases the potential.

Extensions

Below we present various extensions and variations on the basic CG model.

Nonatomic congestion games

A nonatomic (aka continuous) CG is the limit of a standard CG with n players, as $n\rightarrow \infty$. There is a continuum of players, the players are considered "infinitesimally small", and each individual player has a negligible effect on the congestion. Nonatomic CGs were studied by Milchtaich, Friedman and Blonsky.

• We keep $E$ a finite set of congestible elements.
• Instead of recognizing $n$ players, as in the discrete case, we have $n$ types of players, where each type $i$ is associated with a number $r_{i}$, representing the rate of traffic for that type.
• Each agent in type i picks a strategy from the strategy set $S_{i}$.
• As before, the delay functions $d_{e}$ are monotone and positive, but we now add the assumption that they are continuous as well.
• We allow players in a type to distribute fractionally over their strategy set. That is, for every strategy $P\in S_{i}$, let $f_{P}$ denote the fraction of players in type $i$ using strategy $P$. By definition, $\textstyle \sum _{P\in S_{i}}f_{P}=r_{i}$.
• For each element $e\in E$, the load is defined as the sum of fractions of players using e, that is, $x_{e}=\sum _{P\ni e}f_{P}$.

Existence of equilibria in nonatomic CGs

Strategies are now collections of strategy profiles $f_{P}$. For a strategy set $S_{i}$ of size $n$, the collection of all valid profiles is a compact subset of $[0,r_{i}]^{n}$. We now define the potential function as $\textstyle \Phi =\sum _{e\in E}\int _{0}^{x_{e}}d_{e}(z)\,dz$, replacing the discrete integral with the standard one.

As a function of the strategy, $\Phi$ is continuous: $d_{e}$ is continuous by assumption, and $x_{e}$ is a continuous function of the strategy. Then by the extreme value theorem, $\Phi$ attains its global minimum.

The final step is to show that a minimum of $\Phi$ is indeed a Nash equilibrium. Assume for contradiction that there exists a collection of $f_{P}$ that minimize $\Phi$ but are not a Nash equilibrium. Then for some type $i$, there exists some improvement $Q\in S_{i}$ over the current choice $P$. That is, $\textstyle \sum _{e\in Q}d_{e}(x_{e})<\sum _{e\in P}d_{e}(x_{e})$. The idea now is to take a small amount $\delta <f_{P}$ of players using strategy $P$ and move them to strategy $Q$. Now for any $x_{e}\in Q$, we have increased its load by $\delta$, so its term in $\Phi$ is now $\textstyle \int _{0}^{x_{e}+\delta }d_{e}(z)dz$. Differentiating the integral, this change is approximately $\delta \cdot d_{e}(x_{e})$, with error $\delta ^{2}$. The equivalent analysis of the change holds when we look at edges in $P$.

Therefore, the change in potential is approximately $\textstyle \delta (\sum _{e\in Q}d_{e}(x_{e})-\sum _{e\in P}d_{e}(x_{e}))$, which is less than zero. This is a contradiction, as then $\Phi$ was not minimized. Therefore, a minimum of $\Phi$ must be a Nash equilibrium.

Splittable congestion games

In a splittable CG, as in an atomic CG, there are finitely many players, each of whom has a certain load to transfer. As in nonatomic CGs, each player can split his load into fractional loads going through different paths, like a transportation company choosing a set of paths for mass transportation. In contrast to nonatomic CGs, each player has a non-negligible effect on the congestion.

Splittable CGs were first analyzed by Ariel Orda, Raphael Rom and Nachum Shimkin in 1993, in the context of communication networks. They show that, for a simple network with two nodes and multiple parallel links, the Nash equilibrium is unique under reasonable convexity conditions, and has some interesting monotonicity properties. For general network topologies, more complex conditions are required to guarantee the uniqueness of Nash equilibrium.

Congestion games with player-specific delay functions

The basic CG model can be extended by allowing the delay function of each resource to depend on the player. So for each resource e and player i, there is a delay function $d_{i,e}$. Given a strategy $P_{i}$, player $i$ experiences delay $\textstyle \sum _{e\in P_{i}}d_{i,e}(x_{e})$.

Milchtaich introduced and studied CGs with player-specific delays in the following special case:

• Each player chooses a single resource (that is, each strategy is a singleton);
• All players have the same set of strategies.

In this special case, given a strategy $P_{i}=\{e\}$, player $i$ experiences delay $d_{i,e}(x_{e})$. If the player switches to a different strategy $f$, his delay would be $d_{i,f}(x_{f}+1)$; hence, a strategy vector is a Nash equilibrium iff for every player i, $d_{i,e}(x_{e})\leq d_{i,f}(x_{f}+1)$ for all e,f.

In general, CGs with player-specific delays might not admit a potential function. For example, suppose there are three resources x,y,z and two players A and B with the following delay functions:

• $d_{A,x}(1)<d_{A,y}(0)<d_{A,y}(2)<d_{A,z}(0)<d_{A,z}(2)<d_{A,x}(2)$
• $d_{B,y}(1)<d_{B,x}(0)<d_{B,x}(2)<d_{B,z}(0)<d_{B,z}(2)<d_{B,y}(2)$

The following is a cyclic improvement path: $(z,y)\to (y,y)\to (y,z)\to (x,z)\to (x,x)\to (z,x)\to (z,y)$. This shows that the finite-improvement property does not hold, so the game cannot have a potential function (not even a generalized-ordinal-potential function). However:

• When there are only two resources, the finite improvement property holds.
• When there are only two players, every best-response improvement path is finite (this is called the finite best-response property).

When there are three or more players, even best-response paths might be cyclic. However, every CG still has a Nash equilibrium. The proof is constructive and shows an algorithm that finds a Nash equilibrium in at most ${n+1 \choose 2}$ steps. Moreover, every CG is weakly acyclic: for any initial strategy-vector, at least one best-response path starting at this vector has a length of at most $r{n+1 \choose 2}$, which terminates at an equilibrium.

Weighted congestion games

In a weighted CG, different players may have different effects on the congestion. For example, in a road network, a truck adds congestion much more than a motorcycle. Formally, each player i has a weight w_i, and the load in resource e is defined as the sum of weights of agents choosing this resource: $x_{e}=\sum _{i:e\in P_{i}}w_{i}$.

In the special case in which each strategy is a singleton, and all players have the same strategy set, the following is known for weighted CGs:

• If all players have the same delay functions, then the game has the finite-improvement property (and thus has a Nash equilibrium).
• If there are only two strategies (and arbitrarily many players with possibly different delay functions), then the game has the finite-improvement property (and thus has a Nash equilibrium).
• If there are only two players (with possibly different delay functions), then the game has the finite-best-response property (and thus has a Nash equilibrium).
• If there are three or more strategies and three or more players with different delay functions, a Nash equilibrium might not exist.

There are many other papers about weighted congestion games.

Summary of congestion game classifications

In summary, CGs can be classified according to various parameters:

• Number and splittability of players: atomic, splittable or nonatomic;
• Weight of players: unweighted or weighted;
• Delay functions: resource-specific or resource-and-player-specific.
• Number of resources chosen by each player: singleton or general.
• Strategy sets of different players: different or identical

Congestion games in nature

Milinsky describes an experiment in which a natural CG converges into a Nash equilibrium. In his experiment, he fed six sticklebacks from two ends of a tank. The fish distribution between the two ends was, on average, similar to the ratio of the food supply rates, so that no individual fish could increase his feeding rate by moving to the other side.

Mlichtaich presents a more general treatment of CGs in interspecific competition.

See also

• Since there exist Nash equilibria in continuous congestion games, the next natural topic is to analyze their quality. This is done through the concept of Price of anarchy in congestion games.
• Congestion games are a special case of potential games. Rosenthal proved that any congestion game is a potential game. Monderer and Shapley proved the converse: for any potential game, there is a congestion game with the same potential function.
• ּResource allocation games are somewhat related to congestion games.

External links

• Lecture notes of Yishay Mansour about Potential and congestion games
• Lecture notes of Michal Feldman and Noam Nisan about Potential and congestion games
• Vazirani, Vijay V.; Nisan, Noam; Roughgarden, Tim; Tardos, Éva (2007). Algorithmic Game Theory (PDF). Cambridge, UK: Cambridge University Press. ISBN 0-521-87282-0.