Marc Schroder

interaction seminar

Marc Schroder

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

IBD Salle 16

Îlot Bernard du Bois - Salle 16

AMU - AMSE
5-9 boulevard Maurice Bourdet
13001 Marseille

Date(s)
Thursday, March 5 2020| 12:30pm to 1:45pm
Contact(s)

Gaëtan Fournier: gaetan.fournier[at]univ-amu.fr
Raghul Venkatesh: raghul.venkatesh[at]univ-amu.fr

Abstract

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