Ordinary and Prophet Planning Under Uncertainty in Bernoulli Congestion Games

• 成果类型: Article
• 署名作者: Cominetti, Roberto; Scarsini, Marco; Schroder, Marc; Stier-Mosesd, Nicolas E.
• 署名单位: Universidad Adolfo Ibanez; Luiss Guido Carli University; Maastricht University
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2023.0252
• 发表日期: 2025
• 关键词: social planner; stochastic demands; incomplete information game; routing game; atomic congestion games; Price of anarchy

摘要

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.