Congestion game

Congestion games are a class of games in game theory first proposed by Rosenthal in 1973. In a Congestion game we define players and resources, where the payoff of each player depends on the resources it chooses and the number of players choosing the same resource. Congestion games are a special case of potential games. Rosenthal proved that any congestion game is a potential game and Monderer and Shapley (1996) proved the converse: for any potential game, there is a congestion game with the same potential function.

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 connection points A and B, where A is a little closer than B (i.e. A is more likely to be chosen by each player). However, both connection points 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. Good outcome in this game will be for the two players to "coordinate" and pass through different connection points. Can such outcome be achieved? And if so, what will the cost be for each player?

Discrete congestion games are games with the following components.

Let's consider the following directed graph where each player has two available strategies - going though A or going through B - leading to a total of four possibilities. The following matrix expresses the costs of the players in terms of delays depending on their choices:

Both (A,B) and (B,A) are pure Nash equilibria in this game, since any uni-lateral 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).

The existence of Nash equilibria 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 ${\displaystyle \textstyle \Phi =\sum _{e\in E}\sum _{k=1}^{x_{e}}d_{e}(k)}$. Note that this function is not the social welfare ${\displaystyle \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.

...
Wikipedia