## Abstract

We introduce a unifying model to study the impact of worst-case latency deviations in non-atomic selfish routing games. In our model, latencies are subject to (bounded) deviations which are taken into account by the players. The quality deterioration caused by such deviations is assessed by the Deviation Ratio, i.e., the worst case ratio of the cost of a Nash flow with respect to deviated latencies and the cost of a Nash flow with respect to the unaltered latencies. This notion is inspired by the Price of Risk Aversion recently studied by Nikolova and Stier-Moses (Nikolova and Stier-Moses 2015). Here we generalize their model and results. In particular, we derive tight bounds on the Deviation Ratio for multi-commodity instances with a common source and arbitrary non-negative and non-decreasing latency functions. These bounds exhibit a linear dependency on the size of the network (besides other parameters). In contrast, we show that for general multi-commodity networks an exponential dependency is inevitable. We also improve recent smoothness results to bound the Price of Risk Aversion.

Original language | English |
---|---|

Pages (from-to) | 54-89 |

Number of pages | 36 |

Journal | Theory of Computing Systems |

Volume | 63 |

Issue number | 1 |

DOIs | |

Publication status | Published - 15 Jan 2019 |

### Funding

Pieter Kleer is supported by the NWO Gravitation Project NETWORKS, Grant Number 024.002.003.

Funders | Funder number |
---|---|

Nederlandse Organisatie voor Wetenschappelijk Onderzoek | 024.002.003 |

## Keywords

- Biased price of anarchy
- Deviation ratio
- Perturbations
- Price of risk aversion
- Selfish routing