Congestion games are a class of games in game theory

Game theory

Game theory is a mathematical method for analyzing calculated circumstances, such as in games, where a person’s success is based upon the choices of others...

 first proposed by Rosenthal

Robert W. Rosenthal

Robert W. Rosenthal was an American economist, most known for his contributions to game theory.He obtained a B.A. in political economy from Johns Hopkins University ,M.S. and...

 in 1973. In a Congestion game we define players and resources, where the payoff

Payoff

Payoff may refer to:* Bribery* A payoff dominant equilibrium in game theory* Payoff matrix or payoff function in a normal form game in game theory* Payoff set in set theory* Payoff, a 1991 TV film starring Keith Carradine...

 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 game

Potential game

A game in game theory is considered a potential game if the incentive of all players to change their strategy can be expressed in one global function, the potential function. The concept was proposed by Dov Monderer and Lloyd Shapley. Games can be either ordinal or cardinal potential games...

s. 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. denotes the strategy set of player , where each is a non-empty subset of resources. Each resource has a load-dependent cost function that indicates the cost of the resource when players are using it. The cost function for each player is defined by: .

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)

External links

• Lecture notes of Yishay Mansour about Potential and congestion games