Non-Atomic Congestion Games and the Price of Anarchy
Published:
Background
Let \(G=(V,E)\) be directed transportation network, where each node in the set \(V=\{1,\dots,M\}\) represents a transportation hub and each edge \((i,j)\) in set \(E\subseteq\{(i,j): i,j \in V\}\) represents a possible trajectory from node \(\ell =(i,j)\). Note, however that the network is directed so if \(\ell=(i,j)\in E\), this does not necessarily imply that \((j,i)\in E\) (i.e we are not guaranteed a trajectory from node \(j\) to \(i\)).
To specify a path on a transportation network \(G=(V,E)\) we must first identify an origin \((O\in V)\) and destination \((D\in V)\). Once the the origin-destination pair \((O,D)\) is specified we define the set of all paths from node \(O\) to \(D\) as
\(P_{(O,D)}=\{\pi=(\pi_1,\pi_2,\dots,\pi_{n-1},\pi_n):\pi_1=O,\pi_n=D,\) \(\quad \quad \quad (\pi_i,\pi_{i+1})\in E \quad \forall i=1,\dots,n-1 \}.\)
Using the \((O,D)\) pair paths, we also define the set of all possible paths that vehicles/commodities in the transportation network can take as
\[P=\bigcup_{i=1}^K P_{(s_i,t_i)}\]A useful object, which tracks how each path \(p \in P\) relates the edges \(\ell \in E\), is an incidence matrix. The incidence matrix is a binary of matrix \(A \in \{0,1\}^{\vert P \vert \times \vert E \vert }\), where \(A_{ij}\) is \(1\) if the i-th path contains edge \(j\) and \(0\) otherwise.
Non-Atomic Congestion Game
Assume that their are \(N\) vehicles/commodities on the road. Each vehicle/commodity can be transported from some origin \(s_i\) to a destination \(t_i\). Assume that their are \(K\) possible origin-destination pairs \(\Theta=\{(s_i,t_i)\}_{i=1}^K\) that the vehicles/commodities use, each of which have inelastic/constant demand of \(r_i\). Also assume that each vehicle on the transportation network wants to minimize its own travel cost from their chosen origin to their chosen destination. Under these behavioral assumptions, the aim of a non-atomic congestion game is to characterize the aggregate behavior of the vehicles/commodities on the transportation network.
To formalize the non-atomic congestion game, we first define the players. Each \((O,D)\) pair \((s_i,t_i)\in \Theta\) represents a population of players with total demand \(r_i>0\). Each population \(i\) allocates its constituent \(r_i\) vehicles/commodities across each paths \(p \in P_{(s_i,t_i)}\). We denote the amount of vehicles/commodities routed to path \(p\in P_{(s_i,t_i)}\) as the path flow \(f_p\). Therefor we can define each population \(i\)’s set of feasible strategies as
\[S_i = \Big\{\{f_p\}_{p\in P_{(s_i,t_i)}}:\sum_{p\in P_{(s_i,t_i)}}f_p = r_i\Big\}.\]As currently formulated each population’s strategy is decoupled from the other populations’ strategy sets. To couple the strategies of the populations, we introduce the concept of link flows, where the link flow along the edge \(\ell\) represents the number of vehicles/commodities traveling across any particular edge \(\ell\in E\). Note that the the link flow, which we denote as \(x_{\ell}\), must be equal to the sum over all path flows corresponding to paths containing the edge \(\ell\). The coupling constraint can be written interms of the Incidence matrix \(A\) as
\[x_{\ell}=\sum_{p:\ell \in p}f_{p} \quad \forall \ell\in E \iff \begin{pmatrix} x_{\ell_1} \\ \vdots \\ x_{\ell_{|E|}} \end{pmatrix} = A^T\begin{pmatrix}f_{p_1} \\ \vdots \\ f_{p_{|P|}}\end{pmatrix}\]Finally we define the travel costs. We define \(c_e(x_e)\) as the cost of traveling along edge \(e\in E\). Typically this cost is a smooth function referred to as the BPR function. Consequently the total cost of a path \(C_p\) is equal to the sum over all edge costs in the path;
\[C_p = \sum_{\ell\in p}c_e(x_e).\]Wardrop Equilibrium
Next we characterize the expected equilibrium state of the transportation network. One would expect that the equilibrium state is one where no reallocation of vehicles/commodities to different paths \(p\) within their respective \((O,D)\) path sets \(P_{(s_i,t_i)}\) results in a decrease in cost for any player. Such an equilibrium is known as the Wardrop Equilibrium.
Wardrop Equilibrium (Definition)
Given a transportation network \(G=(V,E)\), a continuous link cost \(c_e:\mathbb{R}\to \mathbb{R}\), set of possible \((O,D)\) pairs \(\Theta=\{(s_t^i,t_t^i)\}_{i=1}^K\) with corresponding demands \(\{r_i\}_{i=1}^K\). The Wardrop Equilibrium is defined as the path flow vector \(f^*=\{f_p^*\}_{p\in P}\) such that for every \((s_i,t_i)\) pair the conditional
\[\exists p\in P_{(s_i,t_i)}\quad \text{s.t}\quad f_p> 0 \implies C_{p}(f^*) \leq C_{\tilde p}(f^*)\quad \forall \tilde p\in P_{(s_i,t_i)}\]holds, where \(C_p(f^*)=\sum_{\ell\in p}c_{x_\ell}(x_\ell)=\sum_{\ell\in p}c_{x_{\ell}}\Big(\sum_{p:\ell\in p}f_{p}^*\Big)\).
Wardrop Equilibrium (Corollary)
Given a transportation network \(G=(V,E)\), a continuous link cost \(c_e:\mathbb{R}\to \mathbb{R}\), set of possible \((O,D)\) pairs \(\Theta=\{(s_i,t_i)\}_{i=1}^K\) with corresponding demands \(\{r_i\}_{i=1}^K\). Assume the congestion game permits a Wardrop equilibrium \(f^*\). If there exists a subset \(Q \subseteq P_{(s_i,t_i)}\) such that for all \(p\in Q\), \(f_p>0\), then \(C_p(f^*)=C_{\tilde{p}}(f^*)\) for all \(p\in Q\).
Another, quantity of interest is the total transportation cost accrued across the transportation network when the system has reached a Wardrop equilibrium. We refer to this quantity as the social cost of the congestion game which we define as
\[J_{soc}(f^*)=\sum_{p\in P}f_p^*\cdot C_p(f^*).\]Pigou’s Example
Next we discuss a popular, but simple example of a congestion game which motivates a concept known as the price of anarchy. Consider a transportation network \(G=(\{0,1\},\{(0,1),(1,0)\})\) with one \((O,D)\) pair \((0,1)\), link costs \(c_{x_1}(x_1)=1\) and \(c_{x_2}(x_2)=x_2\), along with demand \(r=1\).
Consider that \(r<1\), then the optimal allocation strategy to minimize cost is naturally \(f_{(2)},f_{(1)}=x_2,x_1=(r,0)\) since \(c_{x_2}(x_2)=r<1=c_{x_1}(x_1)\). Now let \(r\) approach \(1\) from bellow. Since the equilibrium is \((r,0)\), we conclude that \(f^* = (x_2,x_1)=(1,0)\) is the also the wardrop equilibrium of Pigout’s congestion game. The social cost of this strategy is \(f^*_{(1)}\cdot C_{(1)}(f^*)+f^*_{(2)}\cdot C_{(2)}(f^*) = 1\). A natural question, is whether there exists any other path flow vector \(\bar{f}\) such that the social cost \(J_{soc}(\bar{f})< J_{soc}(f^*)\). Observe that
\[J_{soc}(f)=x_1c_{x_1}(x_1) + x_2c_{x_2}(x_2) = x_1 + x_2^2 \quad \text{s.t} \quad f_{(1)} + f_{(2)}=1\] \[\implies J_{soc}(f)= x_2^2 + (1-x_2) = (x_2- 0.5)^2 + 0.75.\]This means that \(\bar{f}\) which minimizes \(J_{soc}(f)\) is \(f=(0.5,0.5)\) which results in a social cost of \(0.75\). The ratio, \(J_{soc}(f^*)/J_{soc}(\bar f) = 1/(3/4)=4/3\), between the social cost of the wardrop equilibrium path flow vector and the minimum social cost is known as the price of anarchy (PoA). In other words, the PoA reflects how much worse the equilibrium is when all players act purely out of self-interest.