A Characterization of Undirected Graphs Admitting Optimal Cost Shares
| Autor: | Tobias Harks, Anja Schedel, Manuel Surek |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
FOS: Computer and information sciences
Computer Science::Computer Science and Game Theory Discrete Mathematics (cs.DM) Computer Science - Computer Science and Game Theory General Mathematics Computer Science - Data Structures and Algorithms 91-02 TheoryofComputation_GENERAL Data Structures and Algorithms (cs.DS) G.2.2 Computer Science and Game Theory (cs.GT) MathematicsofComputing_DISCRETEMATHEMATICS Computer Science - Discrete Mathematics |
| Zdroj: | SIAM Journal on Discrete Mathematics. 33:1932-1996 |
| ISSN: | 1095-7146 0895-4801 |
| DOI: | 10.1137/18m1173265 |
| Popis: | In a seminal paper, Chen, Roughgarden and Valiant 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 budget-balanced and 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. 60 pages, 69 figures, OR 2017 Berlin, WINE 2017 Bangalore |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|