The stackelberg minimum spanning tree game on planar and bounded-treewidth graphs
The Stackelberg Minimum Spanning Tree Game is a two-level combinatorial pricing problem introduced at WADS’07. The game is played on a graph, whose edges are colored either red or blue, and where the red edges have a given fixed cost. The first player chooses an assignment of prices to the blue edge...
| Main Authors: | , , , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Springer
2011
|
| Online Access: | http://hdl.handle.net/1721.1/62548 https://orcid.org/0000-0003-3803-5703 |
| _version_ | 1826198288470114304 |
|---|---|
| author | Cardinal, Jean Demaine, Erik D. Fiorini, Samuel Joret, Gwenaël Newman, Ilan Weimann, Oren |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Cardinal, Jean Demaine, Erik D. Fiorini, Samuel Joret, Gwenaël Newman, Ilan Weimann, Oren |
| author_sort | Cardinal, Jean |
| collection | MIT |
| description | The Stackelberg Minimum Spanning Tree Game is a two-level combinatorial pricing problem introduced at WADS’07. The game is played on a graph, whose edges are colored either red or blue, and where the red edges have a given fixed cost. The first player chooses an assignment of prices to the blue edges, and the second player then buys the cheapest spanning tree, using any combination of red and blue edges. The goal of the first player is to maximize the total price of purchased blue edges. We study this problem in the cases of planar and bounded-treewidth graphs. We show that the problem is NP-hard on planar graphs but can be solved in polynomial time on graphs of bounded treewidth. |
| first_indexed | 2024-09-23T11:02:31Z |
| format | Article |
| id | mit-1721.1/62548 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T11:02:31Z |
| publishDate | 2011 |
| publisher | Springer |
| record_format | dspace |
| spelling | mit-1721.1/625482022-10-01T00:44:21Z The stackelberg minimum spanning tree game on planar and bounded-treewidth graphs Cardinal, Jean Demaine, Erik D. Fiorini, Samuel Joret, Gwenaël Newman, Ilan Weimann, Oren Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Demaine, Erik D. Demaine, Erik D. The Stackelberg Minimum Spanning Tree Game is a two-level combinatorial pricing problem introduced at WADS’07. The game is played on a graph, whose edges are colored either red or blue, and where the red edges have a given fixed cost. The first player chooses an assignment of prices to the blue edges, and the second player then buys the cheapest spanning tree, using any combination of red and blue edges. The goal of the first player is to maximize the total price of purchased blue edges. We study this problem in the cases of planar and bounded-treewidth graphs. We show that the problem is NP-hard on planar graphs but can be solved in polynomial time on graphs of bounded treewidth. 2011-04-28T18:04:58Z 2011-04-28T18:04:58Z 2009-01 Article http://purl.org/eprint/type/ConferencePaper 9783642108402 3642108407 http://hdl.handle.net/1721.1/62548 Cardinal, Jean et al. “The Stackelberg Minimum Spanning Tree Game on Planar and Bounded-Treewidth Graphs.” Internet and Network Economics. Ed. Stefano Leonardi. Berlin, Heidelberg: Springer Berlin Heidelberg, 2009. 125-136. Copyright © 2009, Springer https://orcid.org/0000-0003-3803-5703 en_US http://dx.doi.org/10.1007/978-3-642-10841-9_13 Internet and network economics (WINE) (Lecture notes in computer science, v. 5929) Creative Commons Attribution-Noncommercial-Share Alike 3.0 http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf Springer MIT web domain |
| spellingShingle | Cardinal, Jean Demaine, Erik D. Fiorini, Samuel Joret, Gwenaël Newman, Ilan Weimann, Oren The stackelberg minimum spanning tree game on planar and bounded-treewidth graphs |
| title | The stackelberg minimum spanning tree game on planar and bounded-treewidth graphs |
| title_full | The stackelberg minimum spanning tree game on planar and bounded-treewidth graphs |
| title_fullStr | The stackelberg minimum spanning tree game on planar and bounded-treewidth graphs |
| title_full_unstemmed | The stackelberg minimum spanning tree game on planar and bounded-treewidth graphs |
| title_short | The stackelberg minimum spanning tree game on planar and bounded-treewidth graphs |
| title_sort | stackelberg minimum spanning tree game on planar and bounded treewidth graphs |
| url | http://hdl.handle.net/1721.1/62548 https://orcid.org/0000-0003-3803-5703 |
| work_keys_str_mv | AT cardinaljean thestackelbergminimumspanningtreegameonplanarandboundedtreewidthgraphs AT demaineerikd thestackelbergminimumspanningtreegameonplanarandboundedtreewidthgraphs AT fiorinisamuel thestackelbergminimumspanningtreegameonplanarandboundedtreewidthgraphs AT joretgwenael thestackelbergminimumspanningtreegameonplanarandboundedtreewidthgraphs AT newmanilan thestackelbergminimumspanningtreegameonplanarandboundedtreewidthgraphs AT weimannoren thestackelbergminimumspanningtreegameonplanarandboundedtreewidthgraphs AT cardinaljean stackelbergminimumspanningtreegameonplanarandboundedtreewidthgraphs AT demaineerikd stackelbergminimumspanningtreegameonplanarandboundedtreewidthgraphs AT fiorinisamuel stackelbergminimumspanningtreegameonplanarandboundedtreewidthgraphs AT joretgwenael stackelbergminimumspanningtreegameonplanarandboundedtreewidthgraphs AT newmanilan stackelbergminimumspanningtreegameonplanarandboundedtreewidthgraphs AT weimannoren stackelbergminimumspanningtreegameonplanarandboundedtreewidthgraphs |