We investigate how and to which extent one can exploit risk-aversion and modify the perceived cost of the players in selfish routing so that the Price of Anarchy $$\mathrm {PoA}$$ is improved. We introduce small random perturbations to the edge latencies so that the expected latency does not change, but the perceived cost of the players increases due to risk-aversion. We adopt the model of $$\gamma $$-modifiable routing games, a variant of routing games with restricted tolls. We prove that computing the best $$\gamma $$-enforceable flow is $$\mathrm {NP}$$-hard for parallel-link networks with affine latencies and two classes of heterogeneous risk-averse players. On the positive side, we show that for parallel-link networks with heterogeneous players and for series-parallel networks with homogeneous players, there exists a nicely structured $$\gamma $$-enforceable flow whose $$\mathrm {PoA}$$ improves fast as $$\gamma $$ increases. We show that the complexity of computing such a $$\gamma $$-enforceable flow is determined by the complexity of computing a Nash flow of the original game. Moreover, we prove that the $$\mathrm {PoA}$$ of this flow is best possible in the worst-case, in the sense that there are instances where ii¾?the best $$\gamma $$-enforceable flow has the same $$\mathrm {PoA}$$, and iii¾?considering more flexible modifications does not lead to any further improvement.
['Dimitris Fotakis', 'Dimitris Kalimeris', 'Thanasis Lianeas']
Improving Selfish Routing for Risk-Averse Players