The Impact of Worst-Case Deviations in Non-Atomic Network Routing Games

Pieter Kleer, Guido Schäfer

Research output: Contribution to JournalArticleAcademicpeer-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 (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.

LanguageEnglish
Pages54-89
Number of pages36
JournalTheory of Computing Systems
Volume63
Issue number1
DOIs
Publication statusPublished - 15 Jan 2019

Fingerprint

Network routing
Latency
Routing
Deviation
Game
Risk Aversion
Selfish Routing
Deterioration
Costs
Smoothness
Non-negative
Model
Generalise
Arbitrary

Keywords

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

Cite this

@article{9e2185f5132e43c591be9e3b7da3e4c0,
title = "The Impact of Worst-Case Deviations in Non-Atomic Network Routing Games",
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.",
keywords = "Biased price of anarchy, Deviation ratio, Perturbations, Price of risk aversion, Selfish routing",
author = "Pieter Kleer and Guido Sch{\"a}fer",
year = "2019",
month = "1",
day = "15",
doi = "10.1007/s00224-017-9829-y",
language = "English",
volume = "63",
pages = "54--89",
journal = "Theory of Computing Systems",
issn = "1432-4350",
publisher = "Springer New York",
number = "1",

}

The Impact of Worst-Case Deviations in Non-Atomic Network Routing Games. / Kleer, Pieter; Schäfer, Guido.

In: Theory of Computing Systems, Vol. 63, No. 1, 15.01.2019, p. 54-89.

Research output: Contribution to JournalArticleAcademicpeer-review

TY - JOUR

T1 - The Impact of Worst-Case Deviations in Non-Atomic Network Routing Games

AU - Kleer, Pieter

AU - Schäfer, Guido

PY - 2019/1/15

Y1 - 2019/1/15

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

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

KW - Biased price of anarchy

KW - Deviation ratio

KW - Perturbations

KW - Price of risk aversion

KW - Selfish routing

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

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

U2 - 10.1007/s00224-017-9829-y

DO - 10.1007/s00224-017-9829-y

M3 - Article

VL - 63

SP - 54

EP - 89

JO - Theory of Computing Systems

T2 - Theory of Computing Systems

JF - Theory of Computing Systems

SN - 1432-4350

IS - 1

ER -