Network congestion games are robust to variable demand

Abstract

Network congestion games have provided a fertile ground for the algorithmic game theorycommunity. Indeed, many of the pioneering works on bounding the efficiency of equilibria usethis framework as their starting point. In recent years, there has been an increased interestin studying randomness in this context though the efforts have been mostly devoted to under-standing what happens when link latencies are subject to random shocks. Although this is animportant practical consideration, it is not the only source of randomness in network congestiongames. Another important source is the inherent variability of the demand that most practicalnetworks suffer from. Therefore in this paper we look at the basic non-atomic network conges-tion game with the additional feature that demand is random. Our main result in this paper isthat under a very natural equilibrium notion, in which the basic behavioral assumption is thatusers evaluate their expected cost according to the demand they experience in the system, theprice of anarchy of the game is actually the same as that in the deterministic demand game.Moreover, the result can be extended to the more general class of smooth games.