Price of anarchy for non-atomic congestion games with stochastic demands

• We model user equilibrium and system optimum in transportation of stochastic demands.
• We establish upper bounds on the price of anarchy (PoA).
• Our upper bounds are tight for some special cases, such as that of deterministic demands.
• The PoA depends on the class of link cost functions and demand distributions.
• The network topology has influence on the PoA, but limited.

We generalize the notions of user equilibrium, system optimum and price of anarchy to non-atomic congestion games with stochastic demands. In this generalized model, we extend the two bounding methods from Roughgarden and Tardos (2004) and Correa et al. (2008) to bound the price of anarchy, and compare the upper bounds we have obtained. Our results show that the price of anarchy depends not only on the class of cost functions but also demand distributions and, to some extent, the network topology. The upper bounds are tight in some special cases, including the case of deterministic demands.