Marc Schroder

interaction seminar

Marc Schroder

RWTH Aachen University
Price of anarchy in Bernoulli congestion games with affine costs

IBD Salle 16

Îlot Bernard du Bois - Salle 16

5-9 boulevard Maurice Bourdet
13001 Marseille

Jeudi 5 mars 2020| 12:30 - 13:45

Gaëtan Fournier : gaetan.fournier[at]
Raghul Venkatesh : raghul.venkatesh[at]


We consider atomic congestion games with Bernoulli demands. The game captures the fact that players may end up not being able to participate. Participation happens independently and with exogenous probabilities p_i∈ [0, 1] that are common knowledge. Conversely, exclusion happens with probability 1−p_i, in which case players incur no cost. We prove that this is a potential game, and that the price of anarchy parameterized by the probabilities is a nondecreasing function of p = max_i p_i . The worst case is attained for players with the same probabilities p_i≡p. In
the case of affine costs we provide an analytic expression for the parameterized price of anarchy as a function of p. This function is continuous on (0, 1], it is equal to 4/3 for 0 < p ≤ 1/4, and increases towards the known atomic bound of 5/2 when p→1. The result follows using the (λ, μ)-smoothness framework and optimizing the parameters to get sharp bounds. We show that these bounds are tight and are attained on routing games with purely linear costs (i.e., without constant terms).