Routing Game

An (atomic) routing game, or congestion game, is represented by a tuple $(N,G=(V,E),\{a_i,b_i{\}}_{i\in N},\{c_e{\}}_{e\in E})$ where

• $G$ is a directed graph;
• for each player $i\in N$, $a_i,b_i\in V$ specify a source and sink vertex respectively;
• for each edge $e\in E$, $c_e:\mathbb{N}\to {\mathbb{R}}^{+}$ specifies a non-decreasing congestion cost function on that edge.

The strategy set $S_i$ of each player $i$ is the set of all paths from $a_i$ to $b_i$ in $G$. Given a strategy profile $s$, we denote $n_e(s)$ as the number of players whose path contains $e$. The cost of player $i$ sums up the congestion cost of all edges in their path:

$${\mathrm{cost}}_i(s)=\sum _{e\in s_i}{c}_e(n_e(s)).$$

Routing games are classic examples of Potential Game. Define

$$\Phi (s):=\sum _{e\in E}\sum _{k=1}^{n_e(s)}{c}_e(k).$$

To see this is the exact potential function of routing games, suppose $s_i^{\prime }$ has new edges $E_{\mathrm{new}}$ and removes edges $E_{\mathrm{old}}$ compared to $s_i$. Then, the difference in the potential function is

$$\begin{array}{rl}\Phi (s)-\Phi (s^{\prime })=& \sum _{e\in E_{\mathrm{old}}}{c}_e(n_e(s))+\sum _{e\in E_{\mathrm{new}}}-c_e(n_e(s)+1)+\sum _{e\in E\setminus (E_{\mathrm{old}}\cup E_{\mathrm{new}})}0\\ =& \sum _{e\in E_{\mathrm{old}}}{c}_e(n_e(s))-\sum _{e\in E_{\mathrm{new}}}{c}_e(n_e(s)+1)\\ =& {\mathrm{cost}}_i(s)-\mathrm{cost}(s_i^{\prime },s_{-i}).\end{array}$$

Price of Anarchy

We have the following tight bound of Price of Anarchy for routing games:

For any routing game with linear cost functions, the PoA is upper bounded by 2.5, and there exists a routing game with linear cost functions that has PoA equal to 2.5.

With non-linear cost functions, the PoA can be unbounded.

Ex

For example, consider a routing game with two parallel edges from $a$ to $b$, where the cost function of the first edge is $c_1(k)=1$ and the cost function of the second edge is $c_2(k)=(k/n{)}^p$ for some large $p$. An NE is that all players choose the second edge, resulting in a social cost of $n$. For the strategy where one player chooses the first edge while others choose the second edge, the social cost is $1+(n-1)((n-1)/n{)}^p\to 1$, as $p\to \infty$. Then the PoA is lower bounded by $n$.

Cost Sharing Game

A cost sharing game is a routing game with a decreasing cost $c_e(k)=\frac{C_e}{k}$ for some positive constant $C_e$. That is, the cost of an edge is shared equally among all players using that edge.

We have the following three properties

• Cost sharing games are exact potential games, with the potential function defined as $\Phi (s)={\sum }_{e\in E}{\sum }_{k=1}^{n_e(s)}\frac{C_e}{k}.$
• The PoA of cost sharing games is at most $n$.
  • Proof: Let $s^{\mathrm{NE}}$ be any NE strategy profile and $s^{\mathrm{opt}}$ be the social optimal strategy profile. By definition, we have ${\mathrm{cost}}_i(s_i^{\mathrm{NE}},s_{-i}^{\mathrm{NE}})\le {\mathrm{cost}}_i(s_i^{\mathrm{opt}},s_{-i}^{\mathrm{NE}})$. Note that $s_{-i}$ only determines how many players will share the cost with you, and the best case is that all players use the same path as you while the worst case is that no other players’ path overlaps with yours. Therefore, ${\mathrm{cost}}_i(s_i^{\mathrm{opt}},s_{-i}^{\mathrm{NE}})\le n{\mathrm{cost}}_i(s_i^{\mathrm{opt}},s_{-i}^{\mathrm{opt}})$. Summing over all players gives $\mathrm{cost}(s^{\mathrm{NE}})\le n\cdot \mathrm{cost}(s^{\mathrm{opt}}).$
• The PoA of cost sharing games is exactly $n$.
  • Proof: We only need to fine one instance with PoA of $n$. Consider $n$ agents with a shared source and a shared sink. There are two edges from the source to the sink, with costs $1$ and $n$ respectively. One NE is that all agents choose the second edge, resulting in a social cost of $n$, while the social optimal strategy profile is that all agents choose the first edge, resulting in a social cost of $1$. Thus, the PoA is $n$.
• The PoS of cost sharing games is exactly $H(n)=O(\ln n)$, where $H(n)={\sum }_{k=1}^n{k}^{-1}$ is the $n$-th harmonic number.
  • Let $s^{\mathrm{NE}}\in {\text{Argmin}}_{s\in S}\Phi (s)$. We know that $s^{\mathrm{NE}}$ is an NE of the potential game. Since for any $s$, we have $\mathrm{cost}(s)\le \Phi (s)\le H(n)\mathrm{cost}(s)$, we have $\mathrm{cost}(s^{\mathrm{NE}})\le \Phi (s^{\mathrm{NE}})\le \Phi (s^{\mathrm{opt}})\le H(n)\mathrm{cost}(s^{\mathrm{opt}}).$ Thus, the PoS is upper bounded by $H(n)$. The following game achieves this bound: $n$ players with a shared sink node; given some constant $t$ they can either build their own road with cost $t/i$ for Player $i$, or jointly build a road with a total cost of $t+1$. It is easy to see every player building their own road is the unique NE, as Player $n$ always prefers building their own road, and then so does Player $n-1,n-2,\dots ,1$. The cost of the NE strategy is $H(n)t$. However, if all players jointly build a road, the cost is $t$.