License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2018.146
URN: urn:nbn:de:0030-drops-91508
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9150/
Go to the corresponding LIPIcs Volume Portal

Bilò, Vittorio ; Moscardelli, Luca ; Vinci, Cosimo

Uniform Mixed Equilibria in Network Congestion Games with Link Failures

pdf-format:
LIPIcs-ICALP-2018-146.pdf (0.5 MB)

Abstract

Motivated by possible applications in fault-tolerant routing, we introduce the notion of uniform mixed equilibria in network congestion games with adversarial link failures, where players need to route traffic from a source to a destination node. Given an integer rho >= 1, a rho-uniform mixed strategy is a mixed strategy in which a player plays exactly rho edge disjoint paths with uniform probabilities, so that a rho-uniform mixed equilibrium is a tuple of rho-uniform mixed strategies, one for each player, in which no player can lower her cost by deviating to another rho-uniform mixed strategy. For games with weighted players and affine latency functions, we show existence of rho-uniform mixed equilibria and provide a tight characterization of their price of anarchy. For games with unweighted players, instead, we extend the existential guarantee to any class of latency functions and, restricted to games with affine latencies, we derive a tight characterization of both the prices of anarchy and stability.

BibTeX - Entry

@InProceedings{bil_et_al:LIPIcs:2018:9150,
  author =	{Vittorio Bil{\`o} and Luca Moscardelli and Cosimo Vinci},
  title =	{{Uniform Mixed Equilibria in Network Congestion Games with Link Failures}},
  booktitle =	{45th International Colloquium on Automata, Languages, and  Programming (ICALP 2018)},
  pages =	{146:1--146:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Ioannis Chatzigiannakis and Christos Kaklamanis and D{\'a}niel Marx and Donald Sannella},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9150},
  URN =		{urn:nbn:de:0030-drops-91508},
  doi =		{10.4230/LIPIcs.ICALP.2018.146},
  annote =	{Keywords: Network Congestion Games, Fault-Tolerant Routing, Nash Equilibria, Price of Anarchy, Price of Stability}
}

Keywords: Network Congestion Games, Fault-Tolerant Routing, Nash Equilibria, Price of Anarchy, Price of Stability
Collection: 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Issue Date: 2018
Date of publication: 04.07.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI