Congestion game


Congestion games 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 ; there are several players who need resources ; each player chooses a subset of these resources ; 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 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:
  • Does the existence of equilibrium, as well as the existence of a potential function, extend to more general models of congestion games?
  • What is the quantitative inefficiency of congestion games?
  • What is the computational complexity of finding an equilibrium?

    Example

Consider a traffic net where two players originate at point and need to get to point. Suppose that node is connected to node via two paths: and, where is a little closer than , as in the picture at the right.
The roads from both connection points to 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 and when players go there is.
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:
OATOBT
OAT
OBT

The pure Nash equilibria in this game are and : any unilateral change by one of the players increases the cost of this player. 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 and when players go there is. Then the cost matrix is:
OATOBT
OAT
OBT

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

Basic result

Notation

The basic definition of a CG has the following components.
  • A base set of congestible elements. In the above example, is the set of roads.
  • A set of players. In the above example.
  • A finite set of strategies for each player, where each strategy is a subset of.
  • * In the above example, both players have the same set of strategies:. CGs in which all players have the same set of strategies are called symmetric CGs. 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 'CGs.
  • * In general, a strategy can be any subset of. CGs in which a strategy can only be a path in a given graph are called network CGs. CGs in which a strategy can only be a single resource are called singleton CGs.
  • For each element and a vector of strategies, the load is defined as.
  • For each element there is a delay function' . Given a vector of strategies, the delay on is. Each is assumed to be positive and monotone increasing.
  • Given a strategy, player experiences delay ; each player wants to minimize his delay.
  • A Nash equilibrium is a vector of strategies such that, for each player, replacing with a different strategy would not decrease the delay experienced by.

    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. Note that this function is not the social welfare, 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 switches from to. Elements that are in both of the strategies
remain unaffected, elements that the player leaves decrease the potential by, and the elements the player joins increase the potential by. This change in potential is precisely the change in delay for player, so is in fact a potential function.
Now observe that any minimum of is a pure Nash equilibrium. Fixing all but one player, any improvement in strategy by that player corresponds to decreasing, which cannot happen at a minimum. Now since there are a finite number of configurations and each is monotone, there exists an equilibrium.
The existence of a potential function has an additional implication, called the finite improvement property . 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. 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 'CG' is the limit of a standard CG with n players, as. As in any nonatomic game, 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, Blonsky, and Roughgarden and Tardos.
  • We keep a finite set of congestible elements.
  • Instead of recognizing players, as in the discrete case, we have types of players, where each type is associated with a number, representing the rate of traffic for that type.
  • Each agent in type i picks a strategy from the strategy set.
  • As before, the delay functions 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, let denote the fraction of players in type using strategy. By definition,.
  • For each element, the load is defined as the sum of fractions of players using e, that is,.

    Existence of equilibria in nonatomic CGs

Strategies are now collections of strategy profiles. For a strategy set of size, the collection of all valid profiles is a compact subset of. We now define the potential function as, replacing the discrete integral with the standard one.
As a function of the strategy, is continuous: is continuous by assumption, and is a continuous function of the strategy. Then by the extreme value theorem, attains its global minimum.
The final step is to show that a minimum of is indeed a Nash equilibrium. Assume for contradiction that there exists a collection of that minimize but are not a Nash equilibrium. Then for some type, there exists some improvement over the current choice. That is,. The idea now is to take a small amount of players using strategy and move them to strategy. Now for any, we have increased its load by, so its term in is now. Differentiating the integral, this change is approximately, with error. The equivalent analysis of the change holds when we look at edges in.
Therefore, the change in potential is approximately, which is less than zero. This is a contradiction, as then was not minimized. Therefore, a minimum of 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 a nonatomic CG, 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 a nonatomic CG, 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.
In parallel, Haurie and Marcotte studied splittable CGs in the context of transportation networks. They defined a Nash-Cournot equilibrium and provided conditions for its existence and uniqueness. They showed that, under reasonable conditions, the asymptotic behavior of this NE yield a total flow vector corresponding to a Wardrop equilibrium.
The price of anarchy in splittable CGs was studied by Gairing, Monien and Tiemann, Cominetti, Correa and Stier-Moses, Harks, and finally Roughgarden and Schoppmann.
Huang studies the effect of collusion on the social cost in splittable CGs. He shows that if the network satifies some natural structural condition, and all delay functions are affine, then collusion decreases the social cost in equilibrium. But if either of these conditions is not satisfied, collusion might decrease the social cost.
Richman and Shimkin characterize the networks that guarantee that every splittable CG has a unique PNE. Harks and Timmermans also study equilibrium uniqueness in atomic splittable polymatroid CGs.