We consider an atomic congestion game in which each player i participates in the game with an exogenous and known probability, 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. In the case of affine costs, we find an analytic expression for the corresponding bounds.

Ordinary and Prophet Planning Under Uncertainty in Bernoulli Congestion Games / Cominetti, Roberto; Scarsini, Marco; Schröder, Marc; Stier-Moses, Nicolas E.. - In: OPERATIONS RESEARCH. - ISSN 0030-364X. - 73:2(2025), pp. 672-688. [10.1287/opre.2023.0252]

Ordinary and Prophet Planning Under Uncertainty in Bernoulli Congestion Games

Cominetti, Roberto;Scarsini, Marco;
2025

Abstract

We consider an atomic congestion game in which each player i participates in the game with an exogenous and known probability, 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. In the case of affine costs, we find an analytic expression for the corresponding bounds.
2025
social planner, stochastic demands, incomplete information game, routing game, atomic congestion games, price of anarchy
Ordinary and Prophet Planning Under Uncertainty in Bernoulli Congestion Games / Cominetti, Roberto; Scarsini, Marco; Schröder, Marc; Stier-Moses, Nicolas E.. - In: OPERATIONS RESEARCH. - ISSN 0030-364X. - 73:2(2025), pp. 672-688. [10.1287/opre.2023.0252]
File in questo prodotto:
File Dimensione Formato  
ORfrthCSSS-sm.pdf

Solo gestori archivio

Descrizione: supplemental material
Tipologia: Documento in Post-print
Licenza: Tutti i diritti riservati
Dimensione 464.78 kB
Formato Adobe PDF
464.78 kB Adobe PDF   Visualizza/Apri
1903.03309v8.pdf

Open Access

Descrizione: AAM Version
Tipologia: Documento in Post-print
Licenza: Tutti i diritti riservati
Dimensione 928.59 kB
Formato Adobe PDF
928.59 kB Adobe PDF Visualizza/Apri
OR2025CSSS.pdf

Solo gestori archivio

Tipologia: Versione dell'editore
Licenza: Tutti i diritti riservati
Dimensione 1.37 MB
Formato Adobe PDF
1.37 MB Adobe PDF   Visualizza/Apri
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11385/240518
Citazioni
  • Scopus ND
  • ???jsp.display-item.citation.isi??? 0
  • OpenAlex ND
social impact