Name
Abstract | ||
|---|---|---|
In cost-sharing games with delays, a set of agents jointly uses a subset of resources. Each resource has a fixed cost that has to be shared by the players, and each agent has a nonshareable player-specific delay for each resource. A separable cost-sharing protocol determines cost shares that are budget-balanced, separable, and guarantee existence of pure Nash equilibria (PNE). We provide black-box reductions reducing the design of such a protocol to the design of an approximation algorithm for the underlying cost-minimization problem. In this way, we obtain separable cost-sharing protocols in matroid games, single-source connection games, and connection games on n-series-parallel graphs. All these reductions are efficiently computable - given an initial allocation profile, we obtain a cheaper profile and separable cost shares turning the profile into a PNE. Hence, in these domains, any approximation algorithm yields a separable cost-sharing protocol with price of stability bounded by the approximation factor. |
Year | DOI | Venue |
|---|---|---|
2021 | 10.1287/moor.2020.1050 | MATHEMATICS OF OPERATIONS RESEARCH |
Keywords | DocType | Volume |
cost sharing, price of stability, matroids, connection games | Journal | 46 |
Issue | ISSN | Citations |
1 | 0364-765X | 0 |
PageRank | References | Authors |
0.34 | 0 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Tobias Harks | 1 | 0 | 2.37 |
| Martin Hoefer | 2 | 661 | 59.37 |
| Anja Schedel | 3 | 0 | 1.01 |
| Manuel Surek | 4 | 0 | 0.34 |