Price of Anarchy in Stochastic Atomic Congestion Games with Affine Costs
| Autor: | Nicolas E. Stier-Moses, Roberto Cominetti, Marco Scarsini, Marc Schröder |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2019 |
| Předmět: | |
| Zdroj: | EC '19: Proceedings of the 2019 ACM Conference on Economics and Computation, 579-580 STARTPAGE=579;ENDPAGE=580;TITLE=EC '19: Proceedings of the 2019 ACM Conference on Economics and Computation |
| DOI: | 10.1145/3328526.3329579 |
| Popis: | We consider an atomic congestion game in which each player participates in the game with an exogenous and known probability $p_{i}\in[0,1]$, independently of everybody else, or stays out and incurs no cost. We first prove that the resulting game is potential. Then, we compute the parameterized price of anarchy to characterize the impact of demand uncertainty on the efficiency of selfish behavior. It turns out that the price of anarchy as a function of the maximum participation probability $p=\max_{i} p_{i}$ is a nondecreasing function. The worst case is attained when players have the same participation probabilities $p_{i}\equiv p$. For the case of affine costs, we provide an analytic expression for the parameterized price of anarchy as a function of $p$. This function is continuous on $(0,1]$, is equal to $4/3$ for $0 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|