Congestion game
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. 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 <math>x^2</math>.
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 and when players go there is <math>0.8 x</math>. Then the cost matrix is:
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 <math>n=2</math>. * A finite set of strategies <math>S_i</math> for each player, where each strategy <math>P \in S_i</math> is a subset of . In the above example, both players have the same set of strategies: <math>S_1 = S_2 = \{ \{OA,AT\}, \{OB,BT\} \}</math>. 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 <math>e\in E</math> and a vector of strategies <math>(P_1, P_2, \ldots, P_n)</math>, the load* is defined as <math>x_e = \#\{ i : e \in P_i \}</math>. For each element <math>e\in E</math> there is a delay function <math>d_e : \mathbb{N} \longrightarrow \mathbb{R}</math> (also called latency function or cost function*). Given a vector of strategies, the delay on is <math>d_e(x_e)</math>. Each <math>d_e</math> is assumed to be positive and monotone increasing. * Given a strategy <math>P_i</math>, player experiences delay <math>\textstyle \sum_{e \in P_i} d_e(x_e)</math>; each player wants to minimize his delay. A Nash equilibrium* is a vector of strategies <math>(P_1, P_2, \ldots, P_n)</math> such that, for each player , replacing <math>P_i</math> with a different strategy <math>Q_i</math> 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. 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 <math>r_i</math>, representing the rate of traffic for that type.
- Each agent in type i picks a strategy from the strategy set <math>S_i</math>.
- As before, the delay functions <math>d_e</math> 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 <math>P \in S_i</math>, let <math>f_P</math> denote the fraction of players in type using strategy . By definition, <math>\textstyle \sum_{P\in S_i} f_P = r_i</math>.
- For each element <math>e\in E</math>, the load is defined as the sum of fractions of players using e, that is, <math>x_e = \sum_{P\ni e} f_P</math>.
Existence of equilibria in nonatomic CGs Strategies are now collections of strategy profiles <math>f_P</math>. For a strategy set <math>S_i</math> of size , the collection of all valid profiles is a compact subset of <math>[0,r_i]^n</math>. We now define the potential function as <math>\textstyle \Phi = \sum_{e\in E} \int_0^{x_e} d_e(z) \, dz</math>, replacing the discrete integral with the standard one.
As a function of the strategy, <math>\Phi</math> is continuous: <math>d_e</math> is continuous by assumption, and <math>x_e</math> is a continuous function of the strategy. Then by the extreme value theorem, <math>\Phi</math> attains its global minimum.
The final step is to show that a minimum of <math>\Phi</math> is indeed a Nash equilibrium. Assume for contradiction that there exists a collection of <math>f_P</math> that minimize <math>\Phi</math> but are not a Nash equilibrium. Then for some type , there exists some improvement <math>Q\in S_i</math> over the current choice . That is, <math>\textstyle \sum_{e \in Q} d_e(x_e) < \sum_{e \in P} d_e(x_e) </math>. The idea now is to take a small amount <math>\delta < f_P</math> of players using strategy and move them to strategy . Now for any <math>x_e \in Q</math>, we have increased its load by <math>\delta</math>, so its term in <math>\Phi</math> is now <math>\textstyle \int_0^{x_e+\delta} d_e(z)dz</math>. Differentiating the integral, this change is approximately <math>\delta \cdot d_e(x_e)</math>, with error <math>\delta^2</math>. The equivalent analysis of the change holds when we look at edges in .
Therefore, the change in potential is approximately <math>\textstyle \delta (\sum_{e \in Q} d_e(x_e) - \sum_{e \in P} d_e(x_e))</math>, which is less than zero. This is a contradiction, as then <math>\Phi</math> was not minimized. Therefore, a minimum of <math>\Phi</math> 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, 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 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 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.
Klimm and Warode studied atomic splittable network CGs with affine player-specific delay functions <math>d_{e,i}(x) = a_{e,i}\cdot x_e + b_{e,i}</math>, where xe is the load on edge e, and aei, bei are player-specific constants. They proved that computing a PNE is PPAD-complete.
Harks and Timmermans study splittable atomic CGs with singleton strategy sets - each player should split his load among the edges (not among the paths). This corresponds to a network of m parallel edges between the source and the target. They allow player-specific delay functions. The total cost suffered by each player i is <math>\sum_{e} x_{i,e}\cdot d_{e,i}(x)</math>. They present an algorithm for computing a PNE in time <math>O( (n m)^3 + n^2 m^{14} \log(D/k_0))</math>, where n is the number of players, m the number of edges, D is the maximum player-specific demand, and k0 the smallest packet size.
They also note that computing a PNE in atomic splittable CGs with singleton strategies and affine delay funcions can be presented as a Linear complementarity problem. This implies that not every such game has a PNE. Concrete examples of weighted CGs without PNE are given by Libman and Orda, as well as Goemans Mirrokni and Vetta. This raises the question of what conditions guarantee the existence of PNE.
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 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, <math>w_i < w_j</math> implies <math>|S_i|\geq |S_j|</math>). 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. 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. 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. 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 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 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 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 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 prove that the class of exponential functions guarantees the existence of a weighted potential, and hence the existence of PNE. Harks, Klimm and Mohring 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 <math>a_e \cdot \exp{(\phi\cdot x_e)} + b_e</math>, where <math>\phi</math> 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 <math>a_e \cdot f(x_e) + b_e</math>, where is a monotone function (the same for all resources). * Harks and Klimm 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 <math>a_e \cdot \exp{(\phi\cdot x_e)} + b_e</math>, where <math>\phi</math> 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 <math>a_e \cdot f(x_e) + b_e</math>, where is a monotone function (the same for all resources). Gairing, Monien and Tiemann
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 <math>d_{i,e}</math>. Given a strategy <math>P_i</math>, player experiences delay <math>\textstyle \sum_{e \in P_i} d_{i,e}(x_e)</math>.
Player-specific costs in singleton CGs (crowding games) Milchtaich 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. 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 <math>P_i=\{e\}</math>, player experiences delay <math>d_{i,e}(x_{e})</math>. If the player switches to a different strategy , his delay would be <math>d_{i,f}(x_f+1)</math>; hence, a strategy vector is a PNE iff for every player i, <math>d_{i,e}(x_{e})\leq d_{i,f}(x_{f}+1)</math> 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:
- <math>d_{A,x}(1) < d_{A,y}(0) < d_{A,y}(2) < d_{A,z}(0) < d_{A,z}(2) < d_{A,x}(2) </math>
- <math>d_{B,y}(1) < d_{B,x}(0) < d_{B,x}(2) < d_{B,z}(0) < d_{B,z}(2) < d_{B,y}(2) </math>
The following is a cyclic improvement path: <math>(z,y) \to (y,y) \to (y,z) \to (x,z)\to (x,x)\to (z,x) \to (z,y) </math>. 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. every strong PNE of a crowding game can be attained as a subgame-perfect equilibrium of a sequential version of the game. <math>d_{i,e}(x_{e}) = a_{i,e} + d(x_e)</math>, where <math>a_{i,e}</math> 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, M/M/1 queueing, and habitat selection. The following is known about weighted singleton CGs with separable costs:
If the base costs <math>a_{i,e}</math> are player-independent (<math>a_{i,e} = a_e</math> 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 (<math>a_{i,e} = a_i</math> for every resource e). 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. 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. 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. 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 equilibrium 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. * For every problem in the complexity class PLS (essentially, every local search problem), there exists an ordinal potential game with polynomially many players, such that the set of pure Nash equilibria equals the set of local optima. Even-Dar, Kesselman and Mansour 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 players, the number of resources, and 1/ε.
- When delay functions are degree-d polynomials, the approximation ratio is dO(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 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
Caragiannis, Fanelli, Gravin and Skopalik present an algorithm that computes a constant-factor approximation PNE in weighted CGs. In particular:
- With linear delay functions, the approximation ratio is <math>\frac{3+\sqrt{5}}{2}+O(\epsilon)</math>, and the runtime is polynomial in the number of players, the number of resources, and 1/ε.
- When delay functions are degree-d polynomials, the approximation ratio is <math>d^{2d + o(d)}</math>.
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: atomic CG, splittable CG or nonatomic CG;
- Weight of players: unweighted CG or weighted CG (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 (singleton CG) or path in a network (network CG) or any subset (general CG).
- Strategy sets of different players: different (asymmetric CG) or identical (symmetric CG).