TY - GEN

T1 - The impact of worst-case deviations in non-atomic network routing games

AU - Kleer, Pieter

AU - Schäfer, Guido

PY - 2016/1/1

Y1 - 2016/1/1

N2 - 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 [9]. 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.

AB - 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 [9]. 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.

UR - http://www.scopus.com/inward/record.url?scp=84988027606&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84988027606&partnerID=8YFLogxK

U2 - 10.1007/978-3-662-53354-3_11

DO - 10.1007/978-3-662-53354-3_11

M3 - Conference contribution

AN - SCOPUS:84988027606

SN - 9783662533536

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 129

EP - 140

BT - Algorithmic Game Theory - 9th International Symposium, SAGT 2016, Proceedings

A2 - Gairing, Martin

A2 - Savani, Rahul

PB - Springer Verlag

T2 - 9th International Symposium on Algorithmic Game Theory, SAGT 2016

Y2 - 19 September 2016 through 21 September 2016

ER -