Ordinary and prophet planning under uncertainty in Bernoulli congestion games

Abstract

We consider an atomic congestion game in which each player i participates inthe game with an exogenous and known probability pi ? (0, 1], independently of every-body else, or stays out and incurs no cost. We compute the parameterized price of anarchyto characterize the impact of demand uncertainty on the efficiency of selfish behavior, con-sidering two different notions of a social planner. A prophet planner knows the realizationof 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 solutionsdepending on the players who turn out to be active, whereas an ordinary planner faces thesame uncertainty as the players and can only minimize the expected social cost accordingto the player participation distribution. For both types of planners, we obtain tight boundsfor the price of anarchy by solving suitable optimization problems parameterized by themaximum participation probability q ? maxi pi. In the case of affine costs, we find an ana-lytic expression for the corresponding bounds.