• Abstract. We consider atomic congestion games with players that participate with an exogenous and known probability \(p_i\in [0,1]\), independently of everybody else, or stay out, incurring no cost. When players are present, they choose routes with lowest expected cost, accounting for the participation probabilities of everybody else. In this setting, the Price of Anarchy (PoA) can be defined as the worst-case ratio of the expected social cost at equilibrium to that of any other routing, among instances with possibly different probabilities \(p_i\) not exceeding \(p\). We characterize the PoA as a function \(p\), where the choice of parametrization arises from a monotonicity property that implies that the worst case is attained when all players have the same participation probability. For the case of affine costs, we provide an analytic expression for the continuous PoA function: it is equal to \(4/3\) for \(0 < p < 1/4\), and increases towards \(5/2\) when \(p \to 1\). Casting the game into the lambda-mu smoothness framework paves the way to the characterization of the PoA function for the different regimes, which is the main technical contribution. These results allow us to quantify the impact of demand uncertainty on the inefficiency caused by selfish behavior. The parametrized PoA function can be interpreted as providing a continuous transition between the PoA of nonatomic and atomic games. These bounds are tight and are attained on routing games — as opposed to general congestion games — with purely linear costs (i.e., with no constant terms). Finally, we connect this class of games to results on the convergence of congestion games when the number of players grows to infinity.

Nicolas Stier-Moses (Meta/Facebook)

16 February '22

• Bio. Nicolas Stier-Moses is a Director at the Core Data Science team of Meta (formerly Facebook). The work of the team leverages innovative research to drive impact to the products, infrastructure and processes at Meta. The team draws inspiration from a rich and diverse set of disciplines including Operations, Statistics, Economics, Mechanism Design, Machine Learning, Experimentation, Algorithms, and Computational Social Science (in no particular order). Prior to joining Meta, Nicolas was an Associate Professor at the Decision, Risk and Operations Division of Columbia Business School and at the Business School of Universidad Torcuato Di Tella. He received a Ph.D. degree from the Operations Research Center of the Massachusetts Institute of Technology.