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 ρ ≥ 1, a ρ-uniform mixed strategy is a mixed strategy in which a player plays exactly ρ edge disjoint paths with uniform probabilities, so that a ρ-uniform mixed equilibrium is a tuple of ρ-uniform mixed strategies, one for each player, in which no player can lower her cost by deviating to another ρ-uniform mixed strategy. For games with weighted players and affine latency functions, we show existence of ρ-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.

Uniform mixed equilibria in network congestion games with link failures

Moscardelli, Luca;
2018

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 ρ ≥ 1, a ρ-uniform mixed strategy is a mixed strategy in which a player plays exactly ρ edge disjoint paths with uniform probabilities, so that a ρ-uniform mixed equilibrium is a tuple of ρ-uniform mixed strategies, one for each player, in which no player can lower her cost by deviating to another ρ-uniform mixed strategy. For games with weighted players and affine latency functions, we show existence of ρ-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.
9783959770767
File in questo prodotto:
File Dimensione Formato  
LIPIcs-ICALP-2018-146.pdf

accesso aperto

Tipologia: Documento in Post-print
Dimensione 498.74 kB
Formato Adobe PDF
498.74 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11564/699356
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 5
  • ???jsp.display-item.citation.isi??? ND
social impact