Price of anarchy is maximized at the percolation threshold

When many independent users try to route traffic through a network, the flow can easily become suboptimal as a consequence of congestion of the most efficient paths. The degree of this suboptimality is quantified by the so-called price of anarchy (POA), but so far there are no general rules for when to expect a large POA in a random network. Here I address this question by introducing a simple model of flow through a network with randomly placed congestible and incongestible links. I show that the POA is maximized precisely when the fraction of congestible links matches the percolation threshold of the lattice. Both the POA and the total cost demonstrate critical scaling near the percolation threshold.

Figure 1

(a) Pigou's example of flow through a network with two roads, one of which has constant commute time and the other of which is congestible. (b) The model introduced here, where constant roads (thin [red] lines) and congestible roads (thick [blue] lines) are randomly mixed. A unit amount of traffic is passed through the network, and all roads are unidirectional and proceed to the right.

Figure 2

Electrical circuit analog of the lattice shown in Fig. 1. (a) Traffic splits between two paths, which generically have commute times $c_A$ and $c_B$, respectively, that are linear functions of the traffic along each road. (b) The equilibrium traffic, for which $c_A=c_B$, is analogous to the current through a resistor network with resistances matching the value of $\partial c/\partial x$ along each branch. The optimum traffic, on the other hand, is analogous to the current resulting from a circuit with doubled values of the resistance. Currents are assumed to proceed to the right. (c) The network model being considered [as in Fig. 1] can generically be mapped onto an electrical circuit by representing constant roads as unit voltage sources and congestible roads as either unit resistors, for the equilibrium case, or as resistors with resistance 2, for the optimum case. The diodes ensure that current proceeds to the right and that all commute times are positive.

Figure 3

POA as a function of the fraction $p$ of congestible roads in the lattice, plotted for different values of the system size $L$. The vertical dotted line indicates the lattice percolation threshold, $p_c\approx 0.6447$.

Figure 4

Schematic illustration of large clusters and percolating pathways of congestible roads. (a) At $p<p_c$ and $|p-p_c|\ll 1$, the system contains large, disconnected clusters of congestible roads, with typical size ${\xi }_{\parallel }$ in the downstream direction and ${\xi }_{\perp }$ in the perpendicular direction. One such cluster is highlighted in green (light gray). (b) At $p$ slightly larger than $p_c$, on the other hand, there are many parallel pathways for traversing the lattice using only congestible roads. The correlation lengths ${\xi }_{\parallel }$ and ${\xi }_{\perp }$ describe the typical horizontal and vertical separation between these paths. Small, isolated clusters and dead ends are not shown.

Figure 5

Spatial map of the traffic flow in a typical realization of a random network at $p\approx p_c$. Roads that carry finite traffic in the equilibrium are shown as black points, and light blue (gray) points indicate additional roads that are used in the optimum. The image has been cropped vertically but shows the full width ($L=75$) of the system.

Figure 6

Dependence of the commute time on the fraction $p$ of congestible roads, plotted for $L=50$. The solid (blue [gray]) line shows $C_{\text{opt}}$, and the (red [gray]) dots are $C_{\text{eq}}$. The dashed lines show the analytical results of Eqs. (2) and (3), respectively, for $L\to \infty$. The dotted vertical line indicates $p=p_c$.

Figure 7

Scaling of the average commute time $C$ with the system size $L$. Different curves are labeled by their corresponding value of $p$. At $p<p_c$, the commute time scales as $C\propto L^1$, and at $p>p_c$ the commute time scales as $C\propto L^0$. Precisely at $p=p_c$, the commute time follows $C\propto L^m$, with $m\approx 0.388$. Filled dots denote $C_{\text{eq}}$, and open circles are $C_{\text{opt}}$.

Figure 8

Critical scaling. (a) Inset: The scaled equilibrium commute time $C_{\text{eq}}/L^m$ near the percolation threshold (vertical dotted line). Main figure: $C_{\text{eq}}/L^m$ can be parameterized for all system sizes by $(p-p_c)L^{1/\nu }$, with $\nu \approx 2.6$. $C_{\text{opt}}$ (not shown) can be similarly scaled. (b) Near the percolation threshold, different curves for the POA also collapse when plotted as a function of $(p-p_c)L^{1/\nu }$.

Figure 9

POA for flow through a 3D bcc lattice with randomly placed congestible and constant roads, plotted for different system sizes. The vertical dotted line shows the lattice percolation threshold, $p_c\approx 0.2873$.

Figure 10

Traffic density in a network close to the percolation threshold, $p\approx p_c$. The color indicates the traffic on a particular road, normalized to the system-averaged traffic per road, $x_{\text{avg}}=1/\left(2L\right)$. The equilibrium configuration (left) generally has its traffic concentrated on fewer roads, while the optimum (right) has a more even distribution.