Stochastic atomic congestion games: Price-of-Anarchy and convergence for large games
We consider atomic congestion games with stochastic demand in which each player participates in the game with probability p, and incurs no cost with probability 1-p. For congestion games with affine costs, we provide a tight upper bound for the Price-of-Anarchy as a function of p, which is monotonically increasing and converges to the well-known bound of 5/2 when p converges 1. On the other extreme, for p? 1/4 the bound is constant and equal to 4/3 independently of the game structure and the number of players. For general costs we also analyze the asymptotic convergence of such games when the number of players n grows to infinity but the probability tends to zero as $p_n=\lambda/n$, in which case we establish the convergence towards a Poisson limit game. In a different approach where the weight of the players tend to zero, we find that the limit yields a Wardrop equilibrium for a corresponding nonatomic game.