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

Pieter Kleer, Guido Schäfer*

*Corresponding author for this work

Research output: Chapter in Book / Report / Conference proceedingConference contributionAcademicpeer-review

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 [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.

Original languageEnglish
Title of host publicationAlgorithmic Game Theory - 9th International Symposium, SAGT 2016, Proceedings
EditorsMartin Gairing, Rahul Savani
PublisherSpringer Verlag
Pages129-140
Number of pages12
ISBN (Print)9783662533536
DOIs
Publication statusPublished - 1 Jan 2016
Event9th International Symposium on Algorithmic Game Theory, SAGT 2016 - Liverpool, United Kingdom
Duration: 19 Sep 201621 Sep 2016

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9928 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference9th International Symposium on Algorithmic Game Theory, SAGT 2016
CountryUnited Kingdom
CityLiverpool
Period19/09/1621/09/16

Fingerprint Dive into the research topics of 'The impact of worst-case deviations in non-atomic network routing games'. Together they form a unique fingerprint.

  • Cite this

    Kleer, P., & Schäfer, G. (2016). The impact of worst-case deviations in non-atomic network routing games. In M. Gairing, & R. Savani (Eds.), Algorithmic Game Theory - 9th International Symposium, SAGT 2016, Proceedings (pp. 129-140). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9928 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-662-53354-3_11