The Stackelberg Minimum Spanning Tree Game
We consider a one-round two-player network pricing game, the Stackelberg Minimum Spanning Tree game or StackMST. The game is played on a graph (representing a network), whose edges are colored either red or blue, and where the red edges have a given fixed cost (representing the competitor's pri...
| Main Authors: | , , , , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Springer Nature America, Inc
2019
|
| Online Access: | https://hdl.handle.net/1721.1/121355 |
| _version_ | 1826206378732027904 |
|---|---|
| author | Cardinal, Jean Demaine, Erik D Fiorini, Samuel Joret, Gwenaël Langerman, Stefan Newman, Ilan Weimann, Oren |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Cardinal, Jean Demaine, Erik D Fiorini, Samuel Joret, Gwenaël Langerman, Stefan Newman, Ilan Weimann, Oren |
| author_sort | Cardinal, Jean |
| collection | MIT |
| description | We consider a one-round two-player network pricing game, the Stackelberg Minimum Spanning Tree game or StackMST. The game is played on a graph (representing a network), whose edges are colored either red or blue, and where the red edges have a given fixed cost (representing the competitor's prices). The first player chooses an assignment of prices to the blue edges, and the second player then buys the cheapest possible minimum 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. This game is the minimum spanning tree analog of the well-studied Stackelberg shortest-path game. We analyze the complexity and approximability of the first player's best strategy in StackMST. In particular, we prove that the problem is APX-hard even if there are only two different red costs, and give an approximation algorithm whose approximation ratio is at most min {k,1+ln b,1+ln W}, where k is the number of distinct red costs, b is the number of blue edges, and W is the maximum ratio between red costs. We also give a natural integer linear programming formulation of the problem, and show that the integrality gap of the fractional relaxation asymptotically matches the approximation guarantee of our algorithm. |
| first_indexed | 2024-09-23T13:28:15Z |
| format | Article |
| id | mit-1721.1/121355 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T13:28:15Z |
| publishDate | 2019 |
| publisher | Springer Nature America, Inc |
| record_format | dspace |
| spelling | mit-1721.1/1213552022-09-28T14:31:19Z The Stackelberg Minimum Spanning Tree Game Cardinal, Jean Demaine, Erik D Fiorini, Samuel Joret, Gwenaël Langerman, Stefan Newman, Ilan Weimann, Oren Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science We consider a one-round two-player network pricing game, the Stackelberg Minimum Spanning Tree game or StackMST. The game is played on a graph (representing a network), whose edges are colored either red or blue, and where the red edges have a given fixed cost (representing the competitor's prices). The first player chooses an assignment of prices to the blue edges, and the second player then buys the cheapest possible minimum 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. This game is the minimum spanning tree analog of the well-studied Stackelberg shortest-path game. We analyze the complexity and approximability of the first player's best strategy in StackMST. In particular, we prove that the problem is APX-hard even if there are only two different red costs, and give an approximation algorithm whose approximation ratio is at most min {k,1+ln b,1+ln W}, where k is the number of distinct red costs, b is the number of blue edges, and W is the maximum ratio between red costs. We also give a natural integer linear programming formulation of the problem, and show that the integrality gap of the fractional relaxation asymptotically matches the approximation guarantee of our algorithm. Communauté française de Belgique. Actions de Recherche Concertées (ARC) fund 2019-06-19T14:06:57Z 2019-06-19T14:06:57Z 2009-03 2008-07 2019-06-19T10:58:18Z Article http://purl.org/eprint/type/JournalArticle 978-3-540-73951-7 https://hdl.handle.net/1721.1/121355 Jean Cardinal, Erik D. Demaine, Samuel Fiorini, Gwemael Joret, Stefan Langerman, Ilan Newman, and Oren Weimann. "The stackelberg minimum spanning tree game." Proc. 10th international Workshop on Algorithms and Data Structures (WADS), Lecture Notes in Computer Science, volume 4619 (2007): 64–76. en 10.1007/s00453-009-9299-y Lecture Notes in Computer Science Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Springer Nature America, Inc MIT web domain |
| spellingShingle | Cardinal, Jean Demaine, Erik D Fiorini, Samuel Joret, Gwenaël Langerman, Stefan Newman, Ilan Weimann, Oren The Stackelberg Minimum Spanning Tree Game |
| title | The Stackelberg Minimum Spanning Tree Game |
| title_full | The Stackelberg Minimum Spanning Tree Game |
| title_fullStr | The Stackelberg Minimum Spanning Tree Game |
| title_full_unstemmed | The Stackelberg Minimum Spanning Tree Game |
| title_short | The Stackelberg Minimum Spanning Tree Game |
| title_sort | stackelberg minimum spanning tree game |
| url | https://hdl.handle.net/1721.1/121355 |
| work_keys_str_mv | AT cardinaljean thestackelbergminimumspanningtreegame AT demaineerikd thestackelbergminimumspanningtreegame AT fiorinisamuel thestackelbergminimumspanningtreegame AT joretgwenael thestackelbergminimumspanningtreegame AT langermanstefan thestackelbergminimumspanningtreegame AT newmanilan thestackelbergminimumspanningtreegame AT weimannoren thestackelbergminimumspanningtreegame AT cardinaljean stackelbergminimumspanningtreegame AT demaineerikd stackelbergminimumspanningtreegame AT fiorinisamuel stackelbergminimumspanningtreegame AT joretgwenael stackelbergminimumspanningtreegame AT langermanstefan stackelbergminimumspanningtreegame AT newmanilan stackelbergminimumspanningtreegame AT weimannoren stackelbergminimumspanningtreegame |