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.

Motivation

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?

Definition

Let N denote the set of players and E denote the set of resources. $S_{i}\subseteq 2^E\setminus \emptyset$ denotes the strategy set of player $i\in N$, where each $s_{i}\in S_{i}$ is a non-empty subset of resources. Each resource ${e\in E}$ has a load-dependent cost function c_e(x_e) that indicates the cost of the resource e when x_e players are using it. The cost function for each player is defined by: $c_i(s_{i})=\sum_{e\in s_{i}}c_e(x_e)$.

Example

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:

Cost Matrix

p1/p2	A	B
A	(5,5)	(2,3)
B	(3,2)	(6,6)

References

• Noam Nisan, Tim Roughgarden, Eva Tardos, Vijay V.Vazirani :"Algorithmic Game Theory" p.28,p.62 p.519.
• Lecture notes of Michal Feldman and Noam Nisan about Potential and congestion games

• Rosenthal, R.W., 1973. "A class of games possessing pure-strategy Nash equilibria," International Journal of Game Theory, Volume 2, Number 1, pp. 65–67.

External links

• Lecture notes of Yishay Mansour about Potential and congestion games

Retrieved from "http://en.wikipedia.org/wiki/Congestion_game"