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 (aka pure Nash equilibrium, PNE). During the proof, he in fact proved that every congestion game is an exact potential game. Later, Monderer and Shapley proved a converse result: any game with an exact potential function is equivalent to some congestion game. Later research focused on questions such as:

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 AT and BT when x players go there is ${\displaystyle x^{2}}$.

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

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

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 AT and BT when x players go there is ${\displaystyle 0.8x}$. Then the cost matrix is: