Name
Abstract | ||
|---|---|---|
We identify how to share costs locally in weighted congestion games with polynomial cost functions in order to minimize the worst-case price of anarchy (PoA). First, we prove that among all cost-sharing methods that guarantee the existence of pure Nash equilibria, the Shapley value minimizes the worst-case PoA. Second, if the guaranteed existence condition is dropped, then the proportional cost-sharing method minimizes the worst-case PoA over all cost-sharing methods. As a byproduct of our results, we obtain the first PoA analysis of the simple marginal contribution cost-sharing rule, and prove that marginal cost taxes are ineffective for improving equilibria in (atomic) congestion games. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1007/978-3-319-13129-0_6 | WEB AND INTERNET ECONOMICS |
Keywords | Field | DocType |
cost-sharing, selfish routing, congestion games | Mathematical economics,Economics,Mathematical optimization,Polynomial,Shapley value,Cost sharing,Marginal cost,Price of anarchy,Optimal cost,Nash equilibrium | Conference |
Volume | ISSN | Citations |
8877 | 0302-9743 | 11 |
PageRank | References | Authors |
0.52 | 26 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Vasilis Gkatzelis | 1 | 137 | 14.77 |
| Konstantinos Kollias | 2 | 46 | 5.18 |
| Tim Roughgarden | 3 | 4177 | 353.32 |