Price of anarchy in congestion games

The Price of Anarchy (PoA) is a concept in game theory and mechanism design that measures how the social welfare of a system degrades due to selfish behavior of its agents. It has been studied extensively in various contexts, particularly in congestion games (CG).

Example

The inefficiency of congestion games was first illustrated by Pigou in 1920, using the following simple congestion game. Suppose there are two roads that lead from point A to point B:

• Road 1 is wide but slow. Using this road, it takes 1 minute to get from A to B, regardless of how many drivers use it.
• Road 2 is fast but narrow, so it becomes congested and slower as more drivers use it. If x drivers use the road, it takes them x/1000 minutes to get from A to B.

Suppose there are 1000 drivers who need to go from A to B. Each driver wants to minimize his own delay, but the government would like to minimize the total delay (the sum of delays of all drivers).

• First, let us compute the minimum possible delay. Suppose x drivers go to road 2 and 1000 − x go to road 1. Then, the total delay is x²/1000+(1000 − x). This is minimized when x ≈ 500, that is, 500 drivers go to road 2 and the other 500 to road 1; the total delay is 500×1/2 + 500×1 ≈ 750 minutes.
• For every single driver, the delay is always smaller when driving through road 2, as x/1000 < 1. This means that choosing road 2 is a dominant strategy. So in "anarchy" (that is, without central planning), all drivers choose road 2, their delay is 1 minute, and the total delay is 1000 minutes. The problem is that each agent minimizes his own delay, but ignores the cost imposed by his own actions on the delay of others; there is a negative externality which leads to an inefficient outcome.

In this example, selfish routing leads to a total delay that is 4/3 times higher than the optimum, so the price of anarchy is 4/3. In general, the price of anarchy may differ based on the type of congestion game, the structure of the network, and the delay functions. Various authors have computed upper and lower bounds on the PoA in various congestion games.

Effect of delay functions

To illustrate the effect of the delay functions on PoA, consider a variant of the above example in which the delay in road 1 is still 1 minute, but the delay in road 2 when x drivers use it is ${\displaystyle (x/1000)^{d}}$, for some d>1.

• The minimum possible delay is attained when the number of drivers going to road 2 is ${\displaystyle x={\frac {1000}{(d+1)^{1/d}}}}$. As ${\displaystyle d\to \infty }$, this number approaches 1000, so ${\displaystyle 1000\cdot (1-\epsilon _{d})}$ drivers go to road 2, where ${\displaystyle \epsilon _{d}\to 0}$. The total delay is ${\displaystyle 1000\epsilon _{d}+1000\cdot (1-\epsilon _{d})^{d+1}}$, which approaches 0 as ${\displaystyle d\to \infty }$.
• However, for every single driver in road 1, it is still worthwhile to move to road 2. Therefore, in anarchy, all drivers go to road 2, and the delay is ${\displaystyle 1000\cdot 1^{d+1}=1000}$ minutes.

Therefore, the price of anarchy approaches infinity as ${\displaystyle d\to \infty }$.

Definitions

A congestion game (CG) is defined by a set of resources. For example, in a road network, each road is an individual resource. For each

resource, there is a delay function (aka cost function). The function maps the amount of congestion in the resource (e.g. the number of drivers choosing to use the road) to the delay experienced by each player using it. The total cost of a player is the total delay in all the resources he chooses. Each player chooses a strategy in order to minimize his own cost.

A Nash equilibirum is a situation in which no player can improve his delay by unilaterally changing his choice. The price of anarchy (PoA) is the ratio between the largest delay in Nash equilibrium, and the smallest possible delay overall. The price of stability (PoS) is the ratio between the smallest delay in Nash equilibrium (that is: the best possible equilibrium), and the smallest possible delay overall. The PoA and PoS can also be computed with respect to other equilibrium concepts, such as mixed equilibrium or correlated equilibrium.

There are several main classes of congestion games:

• In atomic CGs, there are finitely many players, and each player chooses a single path (- a single subset of the resources). Atomic congestion games have two variants:
  • In unweighted CGs, each player contributes the same amount 1 to the congestion of the resources he uses. Hence, the congestion in each resource is simply the number of players choosing this resource.
  • In weighted CGs, each player i has a different weight w_i. For example, in road networks, the weight of a driver can be equal to the length of his car. The congestion in each resource is the sum of weights of all players choosing this resource.
• In nonatomic CGs, the number of players approaches infinity, which means that the contribution of each single player to the congestion is negligible. The players are represented by a continuous amount. Pigou's example (illustrated above) was actually originally stated as a nonatomic game. Suppose the delay through road 1 is 1. There is 1 continuous unit of players. The minimum total delay is attained when 1/2 of the players go to road 1 and 1/2 of the go to road 2; the total delay is than 1*1/2+1/2*1/2 = 3/4. However, for each single player, the delay is always smaller through road 2, so in Nash equilibrium, the total delay is 1*1=1.
• In splittable CGs, there are finitely many players, each player has a weight, and each player may split his weight among several paths (- several subsets of resources).

Another classification of CGs is based on the sets of strategies available to the players:

• In symmetric CGs, all players have the same set of possible strategies, as in Pigou's example above.
• In asymmetric CGs, different players may have different sets of possible strategies, such as drivers with different source and destination locations.

Moreover:

• In singleton CGs, every strategy of every player is a singleton set. That is: each players chooses a single resource.
• In network CGs, there is an underlying graph, and every strategy of every player is a simple path in the graph. If the CG is symmetric, then all players have the same source and destination; if it is asymmetric, then different players may have different sources or destinations.

Atomic congestion games

Christodoulou and Koutsoupias analyzed atomic unweighted CGs. They proved that the PoA when all delay functions are linear is exactly 2.5 (that is: the PoA is always at most 2.5, and in some cases it is exactly 2.5). They also gave upper and lower bounds for PoA when the delay functions are polynomials of bounded degree. In another paper, Christodoulou and Koutsoupias analyzed the PoS of atomic unweighted congestion games with linear delay functions. They proved that the PoS is at most 1.6, and showed an example in which the PoS is 1.577. They also showed that the PoA of correlated equilibria in this case is exactly 2.5 for unweighted games and exactly 2.618 for weighed games.

Awerbuch, Azar and Epstein analyzed analyzed atomic weighted CGs. They proved that the PoA when all delay functions are linear is exactly 2.618. They also showed that, when the delay functions are polynomials of degree d, the PoA is in ${\displaystyle d^{\Theta (d)}}$.

Aland, Dumrauf, Gairing, Monien and Schoppmann computed the exact PoA for atomic CGs, for delay functions that are polynomials of degree at most d:

• For unweighted games, the PoA is ${\displaystyle (\Phi _{d})^{d+1}}$, where ${\displaystyle \Phi _{d}}$ is the unique nonnegative real solution to ${\displaystyle (x+1)^{d}=x^{d+1}}$. Note that ${\displaystyle \Phi _{1}}$ is the Golden ratio, and ${\displaystyle \Phi _{d}}$ grows like ${\displaystyle \Theta \left({\frac {d}{\log {d}}}\right)}$. So the PoA is in ${\displaystyle \Theta \left({\frac {d}{\log {d}}}\right)^{d+1}}$.
• For weighted games, the PoA is ${\displaystyle {\frac {(k_{d}+1)^{2d+1}-(k_{d}+2)^{d}\cdot (k_{d})^{d+1}}{(k_{d}+1)^{d+1}-(k_{d}+2)^{d}+(k_{d}+1)^{d}-(k_{d})^{d+1}}}}$, where ${\displaystyle k_{d}:=\lfloor \Phi _{d}\rfloor }$. Asymptotically, this still grows like ${\displaystyle \Theta \left({\frac {d}{\log {d}}}\right)^{d+1}}$.

The same bounds hold whenever no player can improve his expected cost by a unilateral deviation. Therefore, the worst-case PoA are the same with respect to pure Nash equilibrium, mixed Nash equilibrium, correlated equilibrium and coarse-correlated equilibrium. Moreover, the bounds hold for unweighted and weighted network congestion games.

Bhawalkar, Gairing and Roughgarden analyze weighed CGs, and show how to compute the PoA for any class of cost functions (not necessarily polynomial). They also show that, under mild conditions on the allowable delay functions, the PoA with respect to pure Nash equilibria, mixed Nash equilibria, correlated equilibria and coarse correlated equilibria are always equal. They also show that, with polynomial cost functions, the worst-case PoA is attained on a simple network, consisting only of a set of parallel edges. They also show that the PoA of symmetric unweighted congestion games is always equal to the asymmetric ones.

Further results

De-Jong and Uetz study sequential CGs, in which players pick their strategies sequentially rather than simultaneously. They analyze the PoA of subgame perfect equilibrium. They show that the sequential PoA with affine cost functions is exactly 1.5 for two players and ≈2.13 for three players, and at least 2.46 for four players. For singleton congestion games with affine cost functions, when there are n players, the sequential PoA is at most n-1; when ${\displaystyle n\to \infty }$, the sequential PoA is at least 2+1/e ≈ 2.37. For symmetric singleton atomic congestion games with affine cost functions, the sequential PoA is exactly 4/3.

Fotakis studies the PoA of CGs with linearly-independent paths, which is an extension of the setting of parallel links.

Law, Huang and Liu study the PoA of CGs in cognitive radio networks.

Gairing, Burkhard and Karsten study the PoA of CGs with player-specific linear delay functions.

Mlichtaich analyzes the effect of network topology on the efficiency of PNE in atomic CGs:

• 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.

PoA of nonatomic congestion games

Roughgarden and Tardos analyzed nonatomic CGs. They showed that, when the delay functions are polynomials of degree at most d, the PoA is in ${\displaystyle \Theta \left({\frac {d}{\log {d}}}\right)}$, which is substantially smaller than the PoA of atomic games. In particular, when d=1, the PoA is 4/3; this shows that Pigou's simple example is the worst case for linear delay functions.

Chau and Sim extend the results of Roughgarden and Tardos by (1) considering symmetric cost maps and (2) incorporating elastic demands.

Correa, Schulz and Stier-Moses present a short, geometric proof to the results on PoA for nonatomic CGs. They also give stronger bounds on the PoA when equilibrium costs are within reasonable limits of the fixed costs.

Blum, Even-Dar and Ligett showed that all these PoA bounds apply under relatively weak behavioral assumptions: it is sufficient that all users achieve vanishing average regret over repeated plays of the game.

A useful concept in the analysis of PoA is smoothness. A delay function d is called ${\displaystyle (\lambda ,\mu )}$-smooth if for all ${\displaystyle x,y>0}$, ${\displaystyle yd(x)\leq \lambda yd(y)+\mu xd(x)}$. If the delay is ${\displaystyle (\lambda ,\mu )}$ smooth, ${\displaystyle f}$ is a Nash equilibrium, and ${\displaystyle f^{*}}$ is an optimal allocation, then ${\displaystyle \textstyle \sum _{e}x_{e}d_{e}(x_{e})\leq {\frac {\lambda }{1-\mu }}\sum _{e}x_{e}^{*}d_{e}(x_{e}^{*})}$. In other words, the price of anarchy is ${\displaystyle \textstyle {\frac {\lambda }{1-\mu }}}$.

Mlichtaich analyzed singleton nonatomic CGs, with the following additional characteristics:

• The utility of each player is composed of two parts: a player-specific value, minus a resource-specific delay. Formally, if player i chooses resource e, then ${\displaystyle u_{i}=v_{i}(e)-d_{e}(x_{e})}$, where ${\displaystyle v_{i}(e)}$ is the intrinsic value i assigns to e.
• The delay functions ${\displaystyle d_{e}(x_{e})}$ are strictly increasing.
• The marginal social cost of congestion in any resource e (defined as the derivative ${\displaystyle {\frac {d}{dx}}[x\cdot d_{e}(x)]}$) is strictly-increasing.

In such games, the equilibrium payoffs are always unique and Pareto-efficient, but may not maximize the sum of utilities. Moreover:

• If there are at least three resources, the equilibrium maximizes the sum (that is, PoS=PoA=1) iff the delay functions are logarithmic. For non-logarithmic delay functions, there are always fixed utilities or costs for which no equilibrium maximizes the sum of utilities (PoS>1, which implies PoA>1). When there are only two resources, the class of delay functions for which PoA=1 is somewhat larger.
• If the delay functions are not “too” convex, then it is possible to maximize the sum of utilities using a negotiation process, and there is an explicit formula which specifies the share of the maximum aggregate utility that should be allocated to each group of players.

PoA of splittable congestion games

Roughgarden and Schoppmann analyzed splittable congestion games. They showed that, when the delay functions are polynomials of degree at most d, the PoA is in ${\displaystyle \left({\frac {1+{\sqrt {d+1}}}{2}}\right)^{d+1}}$. In particular, when d=1, the PoA is at most 3/2. The PoA for splittable games is smaller than for atomic games, but larger than nonatomic games. For example:

• When d=1, the PoA is 1.333 for nonatomic games, 1.5 for splittable games and 2.5 for atomic games;
• When d=8, the PoA is 3.081 for nonatomic games, 512 for splittable games, and 1,101,126 for atomic games.

PoA with altruistic players

The basic CG model assumes that players are selfish - they care only about their own payoff. In fact, players may be altruistic and care about the social cost too. This can be modeled by assuming that the actual cost of each player is a weighted average of his own delay and the total delay. Altruism may have surprising effects on the system efficiency:

• In atomic CGs, in general, even partial altruism may harm the overall efficiency. However, in the special case of symmetric load-balancing games, optimal efficiency can be attained by balancing selfishness and altruism.
• In atomic CGs and cost sharing games, the robust PoA worsens with increasing altruism, whereas for valid utility games, it is not affected by altruism. But in general nonatomic CGs with uniform altruism, the PoA improves with increasing altruism. For atomic and nonatomic singleton CGs, there are bounds on the pure PoA that improve with the average altruism.

There are other papers studying the effect of altruism on the PoA. An alternative way to measure the effect of altruism on efficiency is via comparative statics: in a single game (not necessarily worst-case one), how does increasing the altruism coefficient affect the social cost? For some classes of CGs, the effect of altruism on efficiency may be negative.

See also

• Congestion pricing - a tax that aims to increase the efficiency in congested networks.
• Externality - a general discussion of the inefficiency caused by selfish behaviour.

References