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:
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 (i.e. is more likely to be chosen by each player), 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: +Cost Matrix OAT OBT OAT (5,5) (2,3) OBT (3,2) (6,6) 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 and when players go there is . Then the cost matrix is: +Cost Matrix OAT OBT OAT (2.6,2.6) (1.8,2.8) OBT (2.8,1.8) (3.6,3.6) 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 (also called resources or factors). In the above example, is the set of roads (, , and ). 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 (as in the above example) 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 (also called latency function or cost 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 (i.e. ) decrease the potential by , and the elements the player joins (i.e. ) 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 (FIP). 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 (that is, the sequence will not cycle). 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 (also called atomic 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 satisfies 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.
Computation Marcotte presented four numeric algorithms for computing NE on congested transportation networks, and analyzed their convergence properties. Meunier and Pradeau presented a numeric algorithm, similar to the Lemke-Howson algorithm, for nonatomic network CGs with affine player-specific delay functions. Both these numeric algorithms were not shown to run in polynomial time.
Cominetti, Correa and Stier-Moses studied splittable CGs with affine player-independent delay functions: , where xe is the load on edge e, and ae,be are player-independent constants. They showed a convex potential function whose global minima are PNE. This means that epsilon-approximate PNEs can be computed in polytime by convex programming.
Huang also considered affine player-independent delay functions. He devised a combinatorial algorithm computing an exact PNE for splittable CGs on symmetric graphs that satisfy a natural structural condition he calls "well-designed" (for example, series–parallel graphs).
Bhaskar and Lolakapuri considered splittable network CGs with convex player-independent delay functions. They presented two algorithms for computing approximate PNE: the first is exponential in the number of players, and while the second is exponential in the number of edges. They also show that in general networks, it is NP-hard to decide if there exists a PNE where every player has cost at most some given constant C.