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 tra c 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 a ne 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 a ne latencies, we derive a tight characterization of both the prices of anarchy and stability.

Uniform mixed equilibria in network congestion games with link failures

Vinci C.
2018-01-01

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 tra c 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 a ne 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 a ne latencies, we derive a tight characterization of both the prices of anarchy and stability.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

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: https://hdl.handle.net/11386/4785749
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 8
  • ???jsp.display-item.citation.isi??? ND
social impact