Improving Selfish Routing for Risk-Averse Players

Dimitris Fotakis, Dimitris Kalimeris, Thanasis Lianeas

Abstract

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 (i) the best $$\gamma $$ -enforceable flow has the same $$\mathrm {PoA}$$ , and (ii) considering more flexible modifications does not lead to any further improvement.
BibTeX
@inproceedings{fotakis2015improving,
  author = {Dimitris Fotakis and Dimitris Kalimeris and Thanasis Lianeas},
  title = {{Improving Selfish Routing for Risk-Averse Players}},
  booktitle = {WINE},
  year = {2015},
  doi = {10.1007/978-3-662-48995-6\_24},
}

Loading related content...

Figure