Ordinary and Prophet Planning under Uncertainty in Bernoulli Congestion Games
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2019
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913463331192832 |
|---|---|
| author | Cominetti, Roberto Scarsini, Marco Schröder, Marc Stier-Moses, Nicolás |
| author_facet | Cominetti, Roberto Scarsini, Marco Schröder, Marc Stier-Moses, Nicolás |
| contents | We consider an atomic congestion game in which each player $i$ 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 compute the parameterized Price of Anarchy (PoA) 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 that 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 type of planners we obtain tight bounds for the PoA, 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1903_03309 |
| institution | arXiv |
| publishDate | 2019 |
| record_format | arxiv |
| spellingShingle | Ordinary and Prophet Planning under Uncertainty in Bernoulli Congestion Games Cominetti, Roberto Scarsini, Marco Schröder, Marc Stier-Moses, Nicolás Computer Science and Game Theory Probability Primary: 91A14, secondary: 91A06, 91A10, 91A43, 91B70, 90B06 We consider an atomic congestion game in which each player $i$ 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 compute the parameterized Price of Anarchy (PoA) 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 that 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 type of planners we obtain tight bounds for the PoA, 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. |
| title | Ordinary and Prophet Planning under Uncertainty in Bernoulli Congestion Games |
| topic | Computer Science and Game Theory Probability Primary: 91A14, secondary: 91A06, 91A10, 91A43, 91B70, 90B06 |
| url | https://arxiv.org/abs/1903.03309 |