Futility of being selfish in optimized traffic

Optimizing traffic flow is essential for easing congestion. However, even when globally optimal, coordinated, and individualized routes are provided, users may choose alternative routes which offer lower individual costs. By analyzing the impact of selfish route choices on performance using the cavity method, we find that a small ratio of selfish route choices improves the global performance of uncoordinated transportation networks but degrades the efficiency of optimized systems. Remarkably, compliant users always gain in the former and selfish users may gain in the latter, under some parameter conditions. The theoretical results are in good agreement with large-scale simulations. Iterative route switching by a small fraction of selfish users leads to Nash equilibria close to the globally optimal routing solution. Our theoretical framework also generalizes the use of the cavity method, originally developed for the study of equilibrium states, to analyze iterative game-theoretical problems. These results shed light on the feasibility of easing congestion by route coordination when not all vehicles follow the coordinated routes.

Figure 1

A schematic diagram showing the recursion relation in Eqs. (19, 20, 21) and the dependence of (21) on (19). The recursion relation is iterated simultaneously for all nodes to obtain the joint functional distribution $P[E^V,{\tilde{E}}^V]$.

Figure 2

The fractional changes in travel costs (a) $\mathrm{\Delta }\mathcal{H}$, (b) $\mathrm{\Delta }{\mathcal{H}}_{\mathrm{selfish}}$, and (c) $\mathrm{\Delta }{\mathcal{H}}_{\mathrm{compliant}}$ as functions of $f_{\mathrm{s}}$, averaged over all users, selfish users, and compliant users, respectively, for $({\gamma }_r,\gamma )=(1,2)$. The corresponding results for cases with $({\gamma }_r,\gamma )=(2,2)$ are shown in panels (d), (e), and (f). The simulation results are obtained on random regular graphs with $N=100$ and $k=3$ for vehicle density $\alpha =M/N=0.1,0.5$, and 0.9 averaged over 1000 realizations. The analytical and semianalytical results are also shown.

Figure 3

The regimes with negative or positive (a) $\mathrm{\Delta }\mathcal{H}(1,2)$, (b) $\mathrm{\Delta }{\mathcal{H}}_{\mathrm{selfish}}(1,2)$, and (c) $\mathrm{\Delta }{\mathcal{H}}_{\mathrm{selfish}}(2,2)$ are shown in terms of the fraction of selfish users $f_{\mathrm{s}}$ and vehicle density $\alpha$. The predictions of the corresponding regime boundary by the analytical and semianalytical approaches are shown.

Figure 4

The values of ${\gamma }_r^{*}$ beyond which (a) $\mathrm{\Delta }\mathcal{H}>0$ and (b) $\mathrm{\Delta }{\mathcal{H}}_{\mathrm{compliant}}>0$, as a function of the density of vehicle $\alpha$. Simulation results are obtained on random regular graphs with $N=100$ and $k=3$ averaged over 1000 realizations, with $f_{\mathrm{s}}=0.1$ of the users selfishly rerouted; semianalytical and analytical results are also shown.

Figure 5

An example of consecutive rounds of selfish rerouting by $M=14$ users on a network with $N=30$ nodes. The origins of users and their common destination are shown by the filled circles and triangle, respectively. Links with nonzero traffic are shown in green, with width proportional to the size of the flow. (a) All users travel via their shortest path to the destination at $t=0$. (b) Half of the users reroute at $t=1$, i.e., $f_{\mathrm{s}}=0.5$. (c) The system arrives at a Nash equilibrium state at $t=9$. (d) All users reroute to minimize their own cost at $t=1$, i.e. $f_{\mathrm{s}}=1$; as we can see, some links close to the destination have low or zero traffic flow. (e) At $t=2$, selfish users switch to what were less occupied links at $t=1$, leaving other links underloaded. The system then switches back and forth between the configurations in panels (d) and (e) repeatedly.

Figure 6

[(a), (b)] The social travel cost $\mathcal{H}$ as a function of $t$, the number of selfish rerouting rounds, measured on specific instances of random regular graphs with $N=100, k=3, {\gamma }_r=1,2$ and various $f_{\mathrm{s}}$ for (a) $\alpha =0.1$ and (b) $\alpha =0.9$. [(c), (d)] The fraction of instances which show no change in travel cost $\mathcal{H}$ for the last consecutive 2500 steps in a simulation with 5000 steps, for (c) $\alpha =0.1$ and (d) $\alpha =0.9$.

Figure 7

The fractional difference $\psi$ between the cost after multiple rounds of selfish rerouting and the optimal cost, as a function of $\alpha$ and $f_{\mathrm{s}}$ for (a) $({\gamma }_r,\gamma )=(1,2)$ and (b) $({\gamma }_r,\gamma )=(2,2)$, respectively. The smaller the value of $\psi$, the closer the system's final state to the optimum. Simulation results are obtained on random regular graphs with $N=100$ and $k=3$ over 1000 realizations.

Figure 8

(a) The region of UK highway network used in our simulation is enclosed by the red rectangle. The network consists of 395 nodes, each of which represents the starting or the ending junction of roads. (b) An example of the configuration of traffic flow resulted from $M=11$ users traveling on the shortest paths from their origin (red filled circles) to the common destination in London (the blue triangle). (c) The configuration of traffic flow after all users reroute. As we can see, all users switch to the initially less occupied route, leaving their original occupied route empty.

Figure 9

The fractional changes (a) $\mathrm{\Delta }\mathcal{H}$, (b) $\mathrm{\Delta }{\mathcal{H}}_{\mathrm{selfish}}$, and (c) $\mathrm{\Delta }{\mathcal{H}}_{\mathrm{compliant}}$ of the travel cost averaged over all users, selfish and compliant users, respectively; simulations were carried out for 500 realizations on the English highway network with $({\gamma }_r,\gamma )=(1,2)$ and vehicle densities $\alpha =M/N=0.1,0.5$, and 0.9. The corresponding simulation results for cases with $({\gamma }_r,\gamma )=(2,2)$ are shown in panels (d), (e), and (f).

Figure 10

The regimes with negative or positive (a) $\mathrm{\Delta }\mathcal{H}(1,2)$, (b) $\mathrm{\Delta }{\mathcal{H}}_{\mathrm{selfish}}(1,2)$, and (c) $\mathrm{\Delta }{\mathcal{H}}_{\mathrm{selfish}}(2,2)$ in the simulations on the English highway network are shown in terms of the fraction of selfish users $f_{\mathrm{s}}$ and vehicle density $\alpha$.

Figure 11

The social travel cost $\mathcal{H}$ on the English highway network as a function of $t$, the rounds of selfish rerouting, measured on specific instances with ${\gamma }_r=1,2$ and various $f_{\mathrm{s}}$ values for (a) $\alpha =0.1$ and (b) $\alpha =0.9$.

Figure 12

The fractional difference $\psi$ between the cost after multiple rounds of selfish rerouting and the optimal cost on the English highway network, as a function of $\alpha$ and $f_{\mathrm{s}}$ for (a) $({\gamma }_r,\gamma )=(1,2)$ and (b) $({\gamma }_r,\gamma )=(2,2)$ respectively. The simulation results are obtained over 500 realizations.