Ordinary and Prophet Planning Under Uncertainty in Bernoulli Congestion Games

We consider an atomic congestion game in which each player i participates in the game with an exogenous and known probability p(i) is an element of (0, 1], independently of everybody else, or stays out and incurs no cost. We compute the parameterized price of anarchy to characterize the impact of demand uncertainty on the efficiency of selfish behavior, considering two different notions of a social planner. A prophet planner knows the realization of the random participation in the game; the ordinary planner does not. As a consequence, a prophet planner can compute an adaptive social optimum that selects different solutions depending on the players who turn out to be active, whereas an ordinary planner faces the same uncertainty as the players and can only minimize the expected social cost according to the player participation distribution. For both types of planners, we obtain tight bounds for the price of anarchy by solving suitable optimization problems parameterized by the maximum participation probability q = max(i) p(i). In the case of affine costs, we find an analytic expression for the corresponding bounds.