Congestion game

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. ^[1] 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 ^[2] 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 congesion games?
• What is the computational complexity of finding an equilibrium?

Example

The directed graph for a simple congestion game.

Consider a traffic net where two players originate at point ${\displaystyle O}$ and need to get to point ${\displaystyle T}$. Suppose that node ${\displaystyle O}$ is connected to node ${\displaystyle T}$ via two paths: ${\displaystyle O}$-${\displaystyle A}$-${\displaystyle T}$ and ${\displaystyle O}$-${\displaystyle B}$-${\displaystyle T}$, where ${\displaystyle A}$ is a little closer than ${\displaystyle B}$ (i.e. ${\displaystyle A}$ is more likely to be chosen by each player), as in the picture at the right.

The roads from both connection points to ${\displaystyle 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 ${\displaystyle A}$${\displaystyle T}$ and ${\displaystyle B}$${\displaystyle T}$ when ${\displaystyle x}$ players go there is ${\displaystyle x^{2}}$.

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

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

Cost Matrix

p2 p1	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 ${\displaystyle A}$${\displaystyle T}$ and ${\displaystyle B}$${\displaystyle T}$ when ${\displaystyle x}$ players go there is ${\displaystyle 0.8x}$. Then the cost matrix is:

Cost Matrix

p2 p1	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 (OAT,OAT): any player switching to OBT increases his cost from 2.6 to 2.8. An equilibrium still exists, but it is not effiicent: the sum of costs is 5.2, while the sum of cost in (OAT,OBT) and (OBT,OAT) is 4.6.

Basic result

Notation

The basic definition of a CG has the following components.

• A base set ${\displaystyle E}$ of congestible elements (also called resources or factors). In the above example, ${\displaystyle E}$ is the set of roads (${\displaystyle O}$${\displaystyle A}$, ${\displaystyle A}$${\displaystyle T}$, ${\displaystyle O}$${\displaystyle B}$ and ${\displaystyle B}$${\displaystyle T}$).
• A set of ${\displaystyle n}$ players. In the above example ${\displaystyle n=2}$.
• A finite set of strategies ${\displaystyle S_{i}}$ for each player, where each strategy ${\displaystyle P\in S_{i}}$ is a subset of ${\displaystyle E}$.
  • In the above example, both players have the same set of strategies: ${\displaystyle S_{1}=S_{2}=\{\{OA,AT\},\{OB,BT\}\}}$. 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 asymmetricCGs.
  • In general, a strategy can be any subset of ${\displaystyle E}$. 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 ${\displaystyle e\in E}$ and a vector of strategies ${\displaystyle (P_{1},P_{2},\ldots ,P_{n})}$, the load is defined as ${\displaystyle x_{e}=\#\{i:e\in P_{i}\}}$.
• For each element ${\displaystyle e\in E}$ there is a delay function${\displaystyle d_{e}:\mathbb {N} \longrightarrow \mathbb {R} }$ (also called latency function or cost function). Given a vector of strategies, the delay on ${\displaystyle e}$ is ${\displaystyle d_{e}(x_{e})}$. Each ${\displaystyle d_{e}}$ is assumed to be positive and monotone increasing.
• Given a strategy ${\displaystyle P_{i}}$, player ${\displaystyle i}$ experiences delay ${\displaystyle \textstyle \sum _{e\in P_{i}}d_{e}(x_{e})}$; each player wants to minimize his delay.
• A Nash equilibrium is a vector of strategies ${\displaystyle (P_{1},P_{2},\ldots ,P_{n})}$ such that, for each player ${\displaystyle i}$, replacing ${\displaystyle P_{i}}$ with a different strategy ${\displaystyle Q_{i}}$ would not decrease the delay experienced by ${\displaystyle i}$.

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. ^[1] Moreover, this construction will also show that iterated best response finds a Nash equilibrium. Define ${\displaystyle \textstyle \Phi =\sum _{e\in E}\sum _{k=1}^{x_{e}}d_{e}(k)}$. Note that this function is not the social welfare ${\displaystyle \textstyle \sum _{e\in E}x_{e}d_{e}(x_{e})}$, 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 ${\displaystyle i}$ switches from ${\displaystyle P_{i}}$ to ${\displaystyle Q_{i}}$. Elements that are in both of the strategies remain unaffected, elements that the player leaves (i.e. ${\displaystyle e\in P_{i}-Q_{i}}$) decrease the potential by ${\displaystyle d_{e}(x_{e})}$, and the elements the player joins (i.e. ${\displaystyle e\in Q_{i}-P_{i}}$) increase the potential by ${\displaystyle d_{e}(x_{e}+1)}$. This change in potential is precisely the change in delay for player ${\displaystyle i}$, so ${\displaystyle \Phi }$ is in fact a potential function.

Now observe that any minimum of ${\displaystyle \Phi }$ is a pure Nash equilibrium. Fixing all but one player, any improvement in strategy by that player corresponds to decreasing ${\displaystyle \Phi }$, which cannot happen at a minimum. Now since there are a finite number of configurations and each ${\displaystyle d_{e}}$ 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 (aka continuous) CG is the limit of a standard CG with n players, as ${\displaystyle n\rightarrow \infty }$. 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, ^[3] Friedman ^[4] and Blonsky. ^{[5] [6]}

• We keep ${\displaystyle E}$ a finite set of congestible elements.
• Instead of recognizing ${\displaystyle n}$ players, as in the discrete case, we have ${\displaystyle n}$types of players, where each type ${\displaystyle i}$ is associated with a number ${\displaystyle r_{i}}$, representing the rate of traffic for that type.
• Each agent in type i picks a strategy from the strategy set ${\displaystyle S_{i}}$.
• As before, the delay functions ${\displaystyle d_{e}}$ 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 ${\displaystyle P\in S_{i}}$, let ${\displaystyle f_{P}}$ denote the fraction of players in type ${\displaystyle i}$ using strategy ${\displaystyle P}$. By definition, ${\displaystyle \textstyle \sum _{P\in S_{i}}f_{P}=r_{i}}$.
• For each element ${\displaystyle e\in E}$, the load is defined as the sum of fractions of players using e, that is, ${\displaystyle x_{e}=\sum _{P\ni e}f_{P}}$.

Existence of equilibria in nonatomic CGs

Strategies are now collections of strategy profiles ${\displaystyle f_{P}}$. For a strategy set ${\displaystyle S_{i}}$ of size ${\displaystyle n}$, the collection of all valid profiles is a compact subset of ${\displaystyle [0,r_{i}]^{n}}$. We now define the potential function as ${\displaystyle \textstyle \Phi =\sum _{e\in E}\int _{0}^{x_{e}}d_{e}(z)\,dz}$, replacing the discrete integral with the standard one.

As a function of the strategy, ${\displaystyle \Phi }$ is continuous: ${\displaystyle d_{e}}$ is continuous by assumption, and ${\displaystyle x_{e}}$ is a continuous function of the strategy. Then by the extreme value theorem, ${\displaystyle \Phi }$ attains its global minimum.

The final step is to show that a minimum of ${\displaystyle \Phi }$ is indeed a Nash equilibrium. Assume for contradiction that there exists a collection of ${\displaystyle f_{P}}$ that minimize ${\displaystyle \Phi }$ but are not a Nash equilibrium. Then for some type ${\displaystyle i}$, there exists some improvement ${\displaystyle Q\in S_{i}}$ over the current choice ${\displaystyle P}$. That is, ${\displaystyle \textstyle \sum _{e\in Q}d_{e}(x_{e})<\sum _{e\in P}d_{e}(x_{e})}$. The idea now is to take a small amount ${\displaystyle \delta <f_{P}}$ of players using strategy ${\displaystyle P}$ and move them to strategy ${\displaystyle Q}$. Now for any ${\displaystyle x_{e}\in Q}$, we have increased its load by ${\displaystyle \delta }$, so its term in ${\displaystyle \Phi }$ is now ${\displaystyle \textstyle \int _{0}^{x_{e}+\delta }d_{e}(z)dz}$. Differentiating the integral, this change is approximately ${\displaystyle \delta \cdot d_{e}(x_{e})}$, with error ${\displaystyle \delta ^{2}}$. The equivalent analysis of the change holds when we look at edges in ${\displaystyle P}$.

Therefore, the change in potential is approximately ${\displaystyle \textstyle \delta (\sum _{e\in Q}d_{e}(x_{e})-\sum _{e\in P}d_{e}(x_{e}))}$, which is less than zero. This is a contradiction, as then ${\displaystyle \Phi }$ was not minimized. Therefore, a minimum of ${\displaystyle \Phi }$ 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 nonatomic CGs, 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 nonatomic CGs, 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. ^{[7] [8]} 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.

Weighted congestion games

In a weightedCG, different players may have different effects on the congestion. For example, in a road network, a truck adds congestion much more than a motorcycle. In general, the weight of a player may depend on the resource (resource-specific weights): for every player i and resource e, there is weight ${\displaystyle w_{i,e}}$, and the load on the resource e is ${\displaystyle x_{e}=\sum _{i:e\in P_{i}}w_{i,e}}$. An important special case is when the weight depends only on the player (resource-independent weights), that is, each player i has a weight ${\displaystyle w_{i}}$, and ${\displaystyle x_{e}=\sum _{i:e\in P_{i}}w_{i}}$.

Weighted singleton CGs with resource-independent weights

Milchtaich ^[9] considered the special case of weighted CGs in which each strategy is a single resource ("singleton CG"), the weights are resource-independent, and all players have the same strategy set. The following is proved:

• If all players have the same delay functions, then the game has the finite-improvement property (and thus has a PNE).
• If there are only two strategies (and arbitrarily many players with possibly different delay functions), then the game has the finite-improvement property (and thus has a PNE).
• If there are only two players (with possibly different delay functions), then the game has the finite-best-response property (and thus has a PNE).
• If there are three or more strategies and three or more players with different delay functions, a PNE might not exist.

Weighted network CGs

Milchtaich considered the special case of weighted CGs in which each strategy is a path in a given undirected graph ("network CG"). He proved that every finite game can be represented as a weighted network congestion game, with nondecreasing (but not necessarily negative) cost-functions. ^[10] This implies that not every such game has a PNE. Concrete examples of weighted CGs without PNE are given by Libman and Orda, ^[11] as well as Goemans Mirrokni and Vetta. ^[12] This raises the quesiton of what conditions guarantee the existence of PNE. ^[13]

In particular, we say that a certain graph G guarantees a certain property if every weighted network CG in which the underlying network is G has that property. Milchtaich ^[14] characterized networks that guarantee the existence of PNE, as well as the finite-improvement property, with the additional condition that a player with a lower weight has weakly more allowed strategies (formally, ${\displaystyle w_{i}<w_{j}}$ implies ${\displaystyle |S_{i}|\geq |S_{j}|}$). He proved that:

• A graph G guarantees the finite-improvement property iff G is homeomorphic to either a parallel network (a graph made of one or more single-edge networks connected in parallel), or to a parallel network connected in series with one or two single-edge networks.^: Thm.2
• A graph G guarantees the existence of a PNE iff G is homeomorphic to a connection in series of one or more networks from a set of six "allowed networks"; an equivalent condition is that no network from a set of six "forbidden network" is embedded in G.^: Thm.3

In the special case in which every player is allowed to use any strategy ("public edges"), there are more networks that guarantee the existence of PNE; a complete characterization of such networks is posed as an open problem. ^[14]

Mlichtaich ^[15] analyzes the effect of network topology on the efficiency of PNE:

• A graph G guarantees that every PNE is Pareto-efficient, iff three simple "forbidden networks" are not embedded in G.
• A graph G guarantees that Braess's paradox does not occur, iff it is a series-parallel graph.

Milchtaich ^[16] analyzes the effect of network topology on the uniqueness of the PNE costs:

• A graph G guarantees that the PNE costs are unique iff G is a connection in series of one or more networks of several several simple kinds.
• A graph G does not guarantee that PNE costs are unique iff G contains an embedded network of a particular simple type.

Holzman and Law-Yone ^[17] also characterize the networks that guarantee that every atomic CG has a strong PNE, a unique PNE, or a Pareto-efficient PNE.

Richman and Shimkin ^[18] characterize the networks that guarantee that every splittable CG has a unique PNE.

General weighted CGs

We say that a class C of functions guarantees a certain property if every weighted CG in which all delay functions are elements of C has that property.

• Fotakis, Kontogiannis and Spirakis ^[19] prove that the class of linear functions guarantees the existence of an exact potential, and hence the existence of PNE.
• Panagopoulou and Spirakis ^[20] prove that the class of exponential functions guarantees the existence of a weighted potential, and hence the existence of PNE.
• Harks, Klimm and Mohring ^[21] prove that a class of functions guarantees the existence of an exact potential, if and only if it contains only affine functions. This characterization remain valid when restricted to two-player games, three-resource games, singleton games, games with symmetric strategies, or games with integral weights. Moreover, a class of functions guarantees the existence of a weighted potential, if and only if either (1) it contains only affine functions, or (2) it contains only exponential functions of the form ${\displaystyle a_{e}\cdot \exp {(\phi \cdot x_{e})}+b_{e}}$, where ${\displaystyle \phi }$ is the same for all resources. This characterization remain valid when restricted to four-player games, four-resource games, singleton games, games with symmetric strategies, or games with integral weights. For two-player games, a class of functions guarantees the existence of a weighted potential, if and only if all functions in it are of the form ${\displaystyle a_{e}\cdot f(x_{e})+b_{e}}$, where ${\displaystyle f}$ is a monotone function (the same for all resources).
• Harks and Klimm ^[22] prove a similar result for the existence of PNE: they prove that a class of functions guarantees the existence of PNE if and only if either (1) it contains only affine functions, or (2) it contains only exponential functions of the form ${\displaystyle a_{e}\cdot \exp {(\phi \cdot x_{e})}+b_{e}}$, where ${\displaystyle \phi }$ is the same for all resources. This characterization remain valid when restricted to three-player games. For two-player games, a class of functions guarantees the existence of PNE if and only if all functions in it are of the form ${\displaystyle a_{e}\cdot f(x_{e})+b_{e}}$, where ${\displaystyle f}$ is a monotone function (the same for all resources).

Other results

There are many other papers about weighted congestion games. ^{[23] [24] [25]}

Player-specific cost functions

The basic CG model can be extended by allowing the delay function of each resource to depend on the player. So for each resource e and player i, there is a delay function ${\displaystyle d_{i,e}}$. Given a strategy ${\displaystyle P_{i}}$, player ${\displaystyle i}$ experiences delay ${\displaystyle \textstyle \sum _{e\in P_{i}}d_{i,e}(x_{e})}$.

Player-specific costs in singleton CGs (crowding games)

Milchtaich ^[9] introduced and studied CGs with player-specific costs in the following special case:

• Each player chooses a single resource (such games are called singleton CGs);
• All players have the same set of strategies.

This special case of CG is also called a crowding game. ^{[26] [27]} It represents a setting in which several people simultaneously choose a place to go to (e.g. a room, a settlement, a restaurant), and their payoff is determined both by the place and by the number of other players choosing the same place.

In a crowding game, given a strategy ${\displaystyle P_{i}=\{e\}}$, player ${\displaystyle i}$ experiences delay ${\displaystyle d_{i,e}(x_{e})}$. If the player switches to a different strategy ${\displaystyle f}$, his delay would be ${\displaystyle d_{i,f}(x_{f}+1)}$; hence, a strategy vector is a PNE iff for every player i, ${\displaystyle d_{i,e}(x_{e})\leq d_{i,f}(x_{f}+1)}$ for all e,f.

In general, CGs with player-specific delays might not admit a potential function. For example, suppose there are three resources x,y,z and two players A and B with the following delay functions:

• ${\displaystyle d_{A,x}(1)<d_{A,y}(0)<d_{A,y}(2)<d_{A,z}(0)<d_{A,z}(2)<d_{A,x}(2)}$
• ${\displaystyle d_{B,y}(1)<d_{B,x}(0)<d_{B,x}(2)<d_{B,z}(0)<d_{B,z}(2)<d_{B,y}(2)}$

The following is a cyclic improvement path: ${\displaystyle (z,y)\to (y,y)\to (y,z)\to (x,z)\to (x,x)\to (z,x)\to (z,y)}$. This shows that the finite-improvement property does not hold, so the game cannot have a potential function (not even a generalized-ordinal-potential function). However:

• With only two resources, the finite improvement property holds. ^{[9] : Thm.1} Hence, a PNE exists.
• With only two players, every finite best-response property holds. Hence, a PNE exists.

When there are three or more players, even best-response paths might be cyclic. However, every CG still has a PNE. ^{[9] : Thm.2} The proof is constructive and shows an algorithm that finds a Nash equilibrium in at most ${\displaystyle {n+1 \choose 2}}$ steps. Moreover, every CG is weakly acyclic: for any initial strategy-vector, at least one best-response path starting at this vector has a length of at most ${\displaystyle r{n+1 \choose 2}}$, which terminates at an equilibrium. ^{[9] : Thm.3}

Every crowding game is sequentially solvable. ^[26] This means that, for every ordering of the players, the sequential game in which each player in turn picks a strategy has a subgame-perfect equilibrium in which the players' actions are a PNE in the original simultaneous game. Every crowding game has at least one strong PNE; ^[28] every strong PNE of a crowding game can be attained as a subgame-perfect equilibrium of a sequential version of the game. ^[26]

In general, a crowding game might have many different PNE. For example, suppose there are n players and n resources, and the negative effect of congestion on the payoff is much higher than the positive value of the resources. Then there are n! different PNEs: every one-to-one matching of players to resources is a PNE, as no player would move to a resource occupied by another player. However, if a crowding game is replicated m times, then the set of PNEs converges to a single point as m goes to infinity. Moreover, in a "large" (nonatomic) crowding game, there is generically a unique PNE. This PNE has an interesting graph-theoretic property. Let G be a bipartite graph with players on one side and resources on the other side, where each player is adjacent to all the resources that his copies choose in the unique PNE. Then G contains no cycles. ^[27]

Separable cost functions

A special case of the player-specific delay functions is that the delay functions can be separated into a player-specific factor and a general factor. There are two sub-cases:

• Multiplicatively-separablecost functions: ${\displaystyle d_{i,e}(x_{e})=a_{i,e}\cdot d(x_{e})}$, where ${\displaystyle a_{i,e}}$ is a constant that represents the base cost of resource e to player i, and d is a general delay function (the same for all resources).
• Additively-separablecost functions: ^[29] ${\displaystyle d_{i,e}(x_{e})=a_{i,e}+d(x_{e})}$, where ${\displaystyle a_{i,e}}$ is a constant that represents the fixed cost of resource e to player i, and d is a general delay function (the same for all resources).

When only pure-strategies are considered, these two notions are equivalent, since the logarithm of a product is a sum. Moreover, when players may have resource-specific weights, the setting with resource-specific delay functions can be reduced to the setting with a universal delay function. Games with separable cost functions occur in load-balancing, ^[30] M/M/1 queueing, ^[31] and habitat selection. ^[32] The following is known about weighted singleton CGs with separable costs: ^[33]

• If the base costs ${\displaystyle a_{i,e}}$ are player-independent (${\displaystyle a_{i,e}=a_{e}}$ for every player i), then the CG has the FIP, hence it has a PNE. The same holds if the base costs are resource-independent (${\displaystyle a_{i,e}=a_{i}}$ for every resource e). ^{[30] [34]} The proof is based on a vector-valued potential function. For each state of the game, the potential is a vector of size n containing the costs of all players, sorted from large to small. Whenever a player deviates to a resource with a smaller cost for him, the vector of costs becomes smaller in the leximin order.
• If the weights are player-independent (equivalently: the CG is unweighted and the delay-functions are resource-specific), then it has the FIP, hence it has a PNE. ^{[35] [29]} If the cost-functions are additively-separable, then the game even has an exact potential function. The result holds even if the cost functions are not monotonically-increasing with the load. If the cost-functions are not additively-separable, then FIP may not hold, and there may be no potential function, but a PNE still exists. ^{[9] : Thm.2}
• If the weights are resource-independent, then a PNE exists in the following cases:
  • When there are at most three players, a PNE exists, ^{[36] : Cor.3} though the best-response improvement property might not hold. In contrast, there is a CG with separable costs and resource-independent weights with eight players in which no PNE exists. ^{[33] : Thm.3}
  • When cost functions are additively-separable with linear variable-cost functions, the CG has a weighted potential, hence it has the FIP, hence it has a PNE. ^{[36] : Thm.6}
  • When cost functions are additively-separable with logarithmic variable-cost function, and there are at most three players, the CG has the best-response improvement property, hence it has a PNE. However, it might not have the finite-improvement property. ^[37] For more than three players, the existence of PNE is open.

Every weighted singleton CG with separable player-specific preferences is isomorphic to a weighted network CG with player-independent preference. ^{[33] [2]}

Network CGs with player-specific costs

Milchtaich considered the special case of CGs with player-specific costs, in which each strategy is a path in a given graph ("network CG"). He proved that every finite game can be represented as an (unweighted) network congestion game with player-specific costs, with nondecreasing (but not necessarily negative) cost-functions. ^[10] A complete characterization of networks that guarantee the existence of PNE in such CGs is posed as an open problem. ^[14]

Computing a pure Nash equilibrium

Computing an equilibrium in unweighted CGs

The proof of existence of PNE is constructive: it shows a finite algorithm (an improvement path) that always finds a PNE. This raises the question of how many steps are required to find this PNE? Fabrikant, Papadimitriou and Talwar ^[38] proved:

• If all strategies are paths in a network ("network CG"), and all players have the same set of strategies ("symmetric CG"), then a PNE can be computed in polynomial time by maximizing the potential, through reduction to min-cost flow. The algorithm can be adapted to nonatomic CGs: under certain smoothness assumptions, a Nash equilibirum in such a game can be approximated in strongly-polynomial time.
• If the strategies can be general subsets, or the players may have different sets of strategies ("asymmetric CG"), then computing a PNE is PLS-complete. This implies that there are examples with exponentially-long improvement paths. It also implies that finding a Nash equilibrium reachable from a specified state is PSPACE-complete.
• Every problem in the class PLS can be presented as a game whose pure equilibria are guaraneed to exist by a potential-function argument.

Even-Dar, Kesselman and Mansour ^[30] analyze the number of steps required for convergence to equilibrium in a load-balancing setting.

Caragiannis, Fanelli, Gravin and Skopalik ^[39] present an algorithm that computes a constant-factor approximation PNE. In particular:

• With linear delay functions, the approximation ratio is 2+ε, and the runtime is polynomial in the number of playres, the number of resources, and 1/ε.
• When delay functions are degree-d polynomials, the approximation ratio is d^O(d).

Their algorithm identifies a short sequence of best-response moves, that leads to an approximate equilibrium. They also show that, for more general CGs, attaining any polynomial approximation of PNE is PLS-complete.

Computing an equilibrium in weighted network CGs

Fotakis, Kontogiannis and Spirakis ^[19] present an algorithm that, in any weighted network CG with linear delay functions, finds a PNE in pseudo-polynomial time (polynomial in the number of players n and the sum of players' weights W). Their algorithm is a greedy best-response algorithm: players enter the game in descending order of their weight, and choose a best-response to existing players' strategies.

Panagopoulou and Spirakis ^[20] show empirical evidence that the algorithm of Fotakis, Kontogiannis and Spirakis in fact runs in time polynomial in n and log W. They also propose an initial strategy-vector that dramatically speeds this algorithm.

In general, a weighted network CG may not have a PNE. Milchtaich ^[14] proves that deciding whether a given weighted network CG has a PNE is NP-hard even in the following cases:

• There are two players; all players are allowed to use all paths; all cost-functions are nonnegative.
• There are two players; the CG is unweighted; the costs are player-specific and nonnegative.

The proof is by reduction from the directed edge-disjoint paths problem. ^[40]

Caragiannis, Fanelli, Gravin and Skopalik ^[41] present an algorithm that computes a constant-factor approximation PNE in weighted CGs. In particular:

• With linear delay functions, the approximation ratio is ${\displaystyle {\frac {3+{\sqrt {5}}}{2}}+O(\epsilon )}$, and the runtime is polynomial in the number of playres, the number of resources, and 1/ε.
• When delay functions are degree-d polynomials, the approximation ratio is ${\displaystyle d^{2d+o(d)}}$.

To prove their results, they show that, although weighted CGs may not have a potential function, every weighted CG can be approximated by a certain potential game. This lets them show that every weighted CG has a (d!)-approximate PNE. Their algorithm identifies a short sequence of best-response moves, that leads to such an approximate PNE.

Summary of congestion game classifications

In summary, CGs can be classified according to various parameters:

• Number and splittability of players: atomicCG, splittable CG or nonatomic CG;
• Weight of players: unweightedCG or weightedCG (with resource-independent weights or resource-specific weights);
• Cost functions for different players using the same resource: identical or player-specific (with separable or nonseparable cost-functions).
• Possible strategies: one resource (singletonCG) or path in a network (network CG) or any subset (general CG).
• Strategy sets of different players: different (asymmetric CG) or identical (symmetric CG).

See also

• Since every CG has a Nash equilibrium, the next natural topic is to analyze their quality. This is done using the concept of Price of anarchy in congestion games .
• ּResource allocation games ^{[42] [31]} are somewhat related to congestion games.
• Incomplete information: Facchini, van Megen, Borm and Tijs ^[35] extend Rosenthal's model to a setting with incomplete information. They prove that the related Bayesian games are potential games, and therefore have pure Bayesian-Nash equilibria.
• Coalitions: Fotakis, Kontogiannis and Spirakis ^[43] study CGs in which players participate in coalitions.
• Congestion games in nature: Milinsky ^[44] describes an experiment in which a natural CG converges into a Nash equilibrium. In his experiment, he fed six sticklebacks from two ends of a tank. The fish distribution between the two ends was, on average, similar to the ratio of the food supply rates, so that no individual fish could increase his feeding rate by moving to the other side. Mlichtaich ^[3] presents a more general treatment of CGs in interspecific competition.

References

1. Rosenthal, Robert W. (1973), "A class of games possessing pure-strategy Nash equilibria", International Journal of Game Theory, 2: 65–67, doi:10.1007/BF01737559, MR   0319584, S2CID   121904640 .
2. Monderer, Dov; Shapley, Lloyd S. (1996-05-01). "Potential Games". Games and Economic Behavior. 14 (1): 124–143. doi:10.1006/game.1996.0044. ISSN   0899-8256.
3. Milchtaich, Igal (1996). "Congestion Models of Competition". The American Naturalist. 147 (5): 760–783. doi:10.1086/285878. ISSN   0003-0147. JSTOR   2463089. S2CID   55004212.
4. Friedman, Eric J. (1996-09-01). "Dynamics and Rationality in Ordered Externality Games". Games and Economic Behavior. 16 (1): 65–76. doi:10.1006/game.1996.0074. ISSN   0899-8256.
5. Blonski, Matthias (1999-08-01). "Anonymous Games with Binary Actions". Games and Economic Behavior. 28 (2): 171–180. doi:10.1006/game.1998.0699. ISSN   0899-8256.
6. Roughgarden, Tim; Tardos, Éva (2004-05-01). "Bounding the inefficiency of equilibria in nonatomic congestion games". Games and Economic Behavior. 47 (2): 389–403. doi:10.1016/j.geb.2003.06.004. ISSN   0899-8256. S2CID   10778635.
7. Orda, A.; Rom, R.; Shimkin, N. (1993-10-01). "Competitive routing in multiuser communication networks". IEEE/ACM Transactions on Networking. 1 (5): 510–521. doi:10.1109/90.251910. ISSN   1558-2566. S2CID   1184436.
8. Roughgarden, Tim; Schoppmann, Florian (2015-03-01). "Local smoothness and the price of anarchy in splittable congestion games". Journal of Economic Theory. Computer Science and Economic Theory. 156: 317–342. doi:10.1016/j.jet.2014.04.005. ISSN   0022-0531.
9. Milchtaich, Igal (1996-03-01). "Congestion Games with Player-Specific Payoff Functions". Games and Economic Behavior. 13 (1): 111–124. doi:10.1006/game.1996.0027. ISSN   0899-8256.
10. Milchtaich, Igal (2013-11-01). "Representation of finite games as network congestion games". International Journal of Game Theory. 42 (4): 1085–1096. doi:10.1007/s00182-012-0363-5. ISSN   1432-1270. S2CID   253713700.
11. Libman, Lavy; Orda, Ariel (2001-08-01). "Atomic Resource Sharing in Noncooperative Networks". Telecommunication Systems. 17 (4): 385–409. doi:10.1023/A:1016770831869. ISSN   1572-9451.
12. Goemans, M.; Mirrokni, Vahab; Vetta, A. (2005-10-01). "Sink Equilibria and Convergence". 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05). pp. 142–151. doi:10.1109/SFCS.2005.68. ISBN   0-7695-2468-0. S2CID   17850062.
13. Milchtaich, Igal (2006). "The Equilibrium Existence Problem in Finite Network Congestion Games". In Spirakis, Paul; Mavronicolas, Marios; Kontogiannis, Spyros (eds.). Internet and Network Economics. Lecture Notes in Computer Science. Vol. 4286. Berlin, Heidelberg: Springer. pp. 87–98. doi:10.1007/11944874_9. ISBN   978-3-540-68141-0.
14. Milchtaich, Igal (2015-08-01). "Network topology and equilibrium existence in weighted network congestion games". International Journal of Game Theory. 44 (3): 515–541. doi:10.1007/s00182-014-0443-9. ISSN   1432-1270. S2CID   253723798.
15. Milchtaich, Igal (2006-11-01). "Network topology and the efficiency of equilibrium". Games and Economic Behavior. 57 (2): 321–346. doi:10.1016/j.geb.2005.09.005. hdl: 10419/259308 . ISSN   0899-8256.
16. Milchtaich, Igal (2005-02-01). "Topological Conditions for Uniqueness of Equilibrium in Networks". Mathematics of Operations Research . 30 (1): 225–244. doi:10.1287/moor.1040.0122. ISSN   0364-765X.
17. Holzman, Ron; Law-Yone, Nissan (1997-10-01). "Strong Equilibrium in Congestion Games". Games and Economic Behavior. 21 (1): 85–101. doi:10.1006/game.1997.0592. ISSN   0899-8256.
18. Richman, Oran; Shimkin, Nahum (2007-02-01). "Topological Uniqueness of the Nash Equilibrium for Selfish Routing with Atomic Users". Mathematics of Operations Research . 32 (1): 215–232. doi:10.1287/moor.1060.0229. ISSN   0364-765X.
19. Fotakis, Dimitris; Kontogiannis, Spyros; Spirakis, Paul (2005-12-08). "Selfish unsplittable flows". Theoretical Computer Science. Automata, Languages and Programming: Algorithms and Complexity (ICALP-A 2004). 348 (2): 226–239. doi:10.1016/j.tcs.2005.09.024. ISSN   0304-3975.
20. Panagopoulou, Panagiota N.; Spirakis, Paul G. (2007-02-09). "Algorithms for pure Nash equilibria in weighted congestion games". ACM Journal of Experimental Algorithmics. 11: 2.7–es. doi:10.1145/1187436.1216584. ISSN   1084-6654. S2CID   17903962.
21. Harks, Tobias; Klimm, Max; Möhring, Rolf H. (2011-07-01). "Characterizing the Existence of Potential Functions in Weighted Congestion Games". Theory of Computing Systems. 49 (1): 46–70. doi:10.1007/s00224-011-9315-x. ISSN   1433-0490. S2CID   912932.
22. Harks, Tobias; Klimm, Max (2012-08-01). "On the Existence of Pure Nash Equilibria in Weighted Congestion Games". Mathematics of Operations Research . 37 (3): 419–436. doi:10.1287/moor.1120.0543. ISSN   0364-765X.
23. Kollias, Konstantinos; Roughgarden, Tim (2011). "Restoring Pure Equilibria to Weighted Congestion Games". In Aceto, Luca; Henzinger, Monika; Sgall, Jiří (eds.). Automata, Languages and Programming. Lecture Notes in Computer Science. Vol. 6756. Berlin, Heidelberg: Springer. pp. 539–551. doi:10.1007/978-3-642-22012-8_43. ISBN   978-3-642-22012-8.
24. Ackermann, Heiner; Röglin, Heiko; Vöcking, Berthold (2009-04-06). "Pure Nash equilibria in player-specific and weighted congestion games". Theoretical Computer Science. Internet and Network Economics. 410 (17): 1552–1563. doi: 10.1016/j.tcs.2008.12.035 . ISSN   0304-3975.
25. Panagopoulou, Panagiota N.; Spirakis, Paul G. (2007-02-09). "Algorithms for pure Nash equilibria in weighted congestion games". ACM Journal of Experimental Algorithmics. 11: 2.7–es. doi:10.1145/1187436.1216584. ISSN   1084-6654. S2CID   17903962.
26. Milchtaich, Igal (1998-12-01). "Crowding games are sequentially solvable". International Journal of Game Theory. 27 (4): 501–509. doi:10.1007/s001820050086. ISSN   1432-1270. S2CID   125221.
27. Milchtaich, Igal (2000). "Generic Uniqueness of Equilibrium in Large Crowding Games". Mathematics of Operations Research . 25 (3): 349–364. doi:10.1287/moor.25.3.349.12220. ISSN   0364-765X. JSTOR   3690472.
28. Konishi, Hideo; Le Breton, Michel; Weber, Shlomo (1997-01-01). "Equilibria in a Model with Partial Rivalry". Journal of Economic Theory. 72 (1): 225–237. doi:10.1006/jeth.1996.2203. ISSN   0022-0531.
29. Konishi, Hideo; Le Breton, Michel; Weber, Shlomo (1997-10-01). "Pure Strategy Nash Equilibrium in a Group Formation Game with Positive Externalities". Games and Economic Behavior. 21 (1): 161–182. doi:10.1006/game.1997.0542. ISSN   0899-8256.
30. Even-Dar, Eyal; Kesselman, Alex; Mansour, Yishay (2003). "Convergence Time to Nash Equilibria". In Baeten, Jos C. M.; Lenstra, Jan Karel; Parrow, Joachim; Woeginger, Gerhard J. (eds.). Automata, Languages and Programming. Lecture Notes in Computer Science. Vol. 2719. Berlin, Heidelberg: Springer. pp. 502–513. doi:10.1007/3-540-45061-0_41. ISBN   978-3-540-45061-0.
31. Libman, Lavy; Orda, Ariel (2001-08-01). "Atomic Resource Sharing in Noncooperative Networks". Telecommunication Systems. 17 (4): 385–409. doi:10.1023/A:1016770831869. ISSN   1572-9451.
32. Brown, Joel S. (1990). "Habitat Selection as an Evolutionary Game". Evolution. 44 (3): 732–746. doi:10.2307/2409448. ISSN   0014-3820. JSTOR   2409448. PMID   28567976.
33. Milchtaich, Igal (2009-11-01). "Weighted congestion games with separable preferences". Games and Economic Behavior. 67 (2): 750–757. doi:10.1016/j.geb.2009.03.009. hdl: 10419/96071 . ISSN   0899-8256.
34. Fabrikant, Alex; Papadimitriou, Christos; Talwar, Kunal (2004-06-13). "The complexity of pure Nash equilibria". Proceedings of the thirty-sixth annual ACM symposium on Theory of computing. STOC '04. New York, NY, USA: Association for Computing Machinery. pp. 604–612. doi:10.1145/1007352.1007445. ISBN   978-1-58113-852-8. S2CID   1037326.
35. Facchini, Giovanni; van Megen, Freek; Borm, Peter; Tijs, Stef (1997-03-01). "CONGESTION MODELS AND WEIGHTED BAYESIAN POTENTIAL GAMES". Theory and Decision. 42 (2): 193–206. doi:10.1023/A:1004991825894. ISSN   1573-7187. S2CID   123623707.
36. Mavronicolas, Marios; Milchtaich, Igal; Monien, Burkhard; Tiemann, Karsten (2007). "Congestion Games with Player-Specific Constants". In Kučera, Luděk; Kučera, Antonín (eds.). Mathematical Foundations of Computer Science 2007. Lecture Notes in Computer Science. Vol. 4708. Berlin, Heidelberg: Springer. pp. 633–644. doi:10.1007/978-3-540-74456-6_56. ISBN   978-3-540-74456-6.
37. Gairing, Martin; Monien, Burkhard; Tiemann, Karsten (2006). "Routing (Un-) Splittable Flow in Games with Player-Specific Linear Latency Functions". In Bugliesi, Michele; Preneel, Bart; Sassone, Vladimiro; Wegener, Ingo (eds.). Automata, Languages and Programming. Lecture Notes in Computer Science. Vol. 4051. Berlin, Heidelberg: Springer. pp. 501–512. doi:10.1007/11786986_44. ISBN   978-3-540-35905-0.
38. Fabrikant, Alex; Papadimitriou, Christos; Talwar, Kunal (2004-06-13). "The complexity of pure Nash equilibria". Proceedings of the thirty-sixth annual ACM symposium on Theory of computing. STOC '04. New York, NY, USA: Association for Computing Machinery. pp. 604–612. doi:10.1145/1007352.1007445. ISBN   978-1-58113-852-8. S2CID   1037326.
39. Caragiannis, Ioannis; Fanelli, Angelo; Gravin, Nick; Skopalik, Alexander (2011-10-01). "Efficient Computation of Approximate Pure Nash Equilibria in Congestion Games". 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science. pp. 532–541. arXiv: 1104.2690 . doi:10.1109/FOCS.2011.50. ISBN   978-0-7695-4571-4. S2CID   14879292.
40. Fortune, Steven; Hopcroft, John; Wyllie, James (1980-02-01). "The directed subgraph homeomorphism problem". Theoretical Computer Science. 10 (2): 111–121. doi: 10.1016/0304-3975(80)90009-2 . ISSN   0304-3975.
41. Caragiannis, Ioannis; Fanelli, Angelo; Gravin, Nick; Skopalik, Alexander (2015-03-27). "Approximate Pure Nash Equilibria in Weighted Congestion Games: Existence, Efficient Computation, and Structure". ACM Transactions on Economics and Computation. 3 (1): 2:1–2:32. doi:10.1145/2614687. ISSN   2167-8375. S2CID   5581666.
42. Kukushkin, N. S.; Men'Shikov, I. S.; Men'Shikova, O. R.; Morozov, V. V. (1990). "Resource allocation games". Computational Mathematics and Modeling. 1 (4): 433. doi:10.1007/BF01128293. S2CID   120639586.
43. Fotakis, Dimitris; Kontogiannis, Spyros; Spirakis, Paul (2006). "Atomic Congestion Games Among Coalitions". In Bugliesi, Michele; Preneel, Bart; Sassone, Vladimiro; Wegener, Ingo (eds.). Automata, Languages and Programming. Lecture Notes in Computer Science. Vol. 4051. Berlin, Heidelberg: Springer. pp. 572–583. doi:10.1007/11786986_50. ISBN   978-3-540-35905-0.
44. Milinski, Manfred (2010-04-26). "An Evolutionarily Stable Feeding Strategy in Sticklebacks". Zeitschrift für Tierpsychologie. 51 (1): 36–40. doi:10.1111/j.1439-0310.1979.tb00669.x.

External links

• Lecture notes of Yishay Mansour about Potential and congestion games
• Lecture notes of Michal Feldman and Noam Nisan about Potential and congestion games
• Vazirani, Vijay V.; Nisan, Noam; Roughgarden, Tim; Tardos, Éva (2007). Algorithmic Game Theory (PDF). Cambridge, UK: Cambridge University Press. ISBN   0-521-87282-0.