Paper by Erik D. Demaine
- Reference:
- Jean Cardinal, Erik D. Demaine, Samuel Fiorini, Gwenaël Joret, Stefan Langerman, Ilan Newman, and Oren Weimann, “The Stackelberg Minimum Spanning Tree Game”, in Proceedings of the 10th Workshop on Algorithms and Data Structures (WADS 2007), Lecture Notes in Computer Science, volume 4619, Halifax, Nova Scotia, Canada, August 15–17, 2007, pages 64–76.
- Abstract:
-
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, 3 + 2 ln b, 1 + lnW},
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.
- Length:
- The paper is 12 pages.
- Availability:
- The paper is available in PostScript (425k), gzipped PostScript (180k), and PDF (218k).
- See information on file formats.
- [Google Scholar search]
- Related papers:
- StackMST_Algorithmica (The Stackelberg Minimum Spanning Tree Game)
See also other papers by Erik Demaine.
These pages are generated automagically from a
BibTeX file.
Last updated July 23, 2024 by
Erik Demaine.