Name
Abstract | ||
|---|---|---|
In a seminal paper, Chen, Roughgarden, and Valiant [SIAM J. Comput., 39 (5) (2010), pp. 1799-1832] studied cost sharing protocols for network design with the objective to implement a low-cost Steiner forest as a Nash equilibrium of an induced cost-sharing game. One of the most intriguing open problems to date is to understand the power of separable cost sharing protocols in order to induce low-cost Steiner forests. In this work, we focus on undirected networks and analyze topological properties of the underlying graph so that an optimal Steiner forest can be implemented as a Nash equilibrium (by some separable cost sharing protocol) independent of the edge costs. We term a graph efficient if the above stated property holds. As our main result, we give a complete characterization of efficient undirected graphs for two-player network design games: an undirected graph is efficient if and only if it does not contain (at least) one out of few forbidden subgraphs. Our characterization implies that several graph classes are efficient: generalized series-parallel graphs, fan and wheel graphs, and graphs with small cycles. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.1137/18M1173265 | SIAM JOURNAL ON DISCRETE MATHEMATICS |
Keywords | Field | DocType |
network cost sharing games,forbidden subgraphs,price of stability | Comparability graph,Indifference graph,Modular decomposition,Tree (graph theory),Computer science,Chordal graph,Discrete mathematics,Mathematical economics,Combinatorics,Mathematical optimization,Tree-depth,Pathwidth,Nash equilibrium | Journal |
Volume | Issue | ISSN |
33 | 4 | 0895-4801 |
Citations | PageRank | References |
0 | 0.34 | 21 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Tobias Harks | 1 | 0 | 2.37 |
| Anja Schedel | 2 | 0 | 1.01 |
| Manuel Surek | 3 | 0 | 0.34 |