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