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,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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Alimonti, P., Kann, V.: Some APX-completeness results for cubic graphs. Theor. Comput. Sci. 237(1–2), 123–134 (2000)
Balcan, M.-F., Blum, A.: Approximation algorithms and online mechanisms for item pricing. In: Proc. ACM Conference on Electronic Commerce (EC) (2006)
Balcan, M.-F., Blum, A., Manshour, Y.: Item pricing for revenue maximization. In: Proc. ACM Conference on Electronic Commerce (EC) (2008)
Bouhtou, M., Grigoriev, A., van Hoesel, S., van der Kraaij, A.F., Spieksma, F.C.R., Uetz, M.: Pricing bridges to cross a river. Nav. Res. Logist. 54(4), 411–420 (2007)
Briest, P., Hoefer, M., Krysta, P.: Stackelberg network pricing games. In: Proc. 25th International Symposium on Theoretical Aspects of Computer Science (STACS), pp. 133–142 (2008)
Briest, P., Krysta, P.: Single-minded unlimited supply pricing on sparse instances. In: Proc. 17th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1093–1102 (2006)
Cardinal, J., Demaine, E.D., Fiorini, S., Joret, G., Langerman, S., Newman, I., Weimann, O.: The Stackelberg minimum spanning tree game. In: Proc. 10th International Workshop on Algorithms and Data Structures (WADS). Lecture Notes in Computer Science, vol. 4619, pp. 64–76. Springer, Berlin (2007)
Cardinal, J., Labbé, M., Langerman, S., Palop, B.: Pricing of geometric transportation networks. In: Proc. Canadian Conference on Computational Geometry (CCCG), pp. 92–96 (2005)
Demaine, E.D., Feige, U., Hajiaghayi, M., Salavatipour, M.R.: Combination can be hard: Approximability of the unique coverage problem. SIAM J. Comput. (2009, to appear)
Grigoriev, A., van Loon, J., Sitters, R., Uetz, M.: How to sell a graph: Guidelines for graph retailers. In: Proc. Workshop on Graph-Theoretic Concepts in Computer Science (WG). Lecture Notes in Computer Science, vol. 4271, pp. 125–136. Springer, Berlin (2006)
Guruswami, V., Hartline, J., Karlin, A., Kempe, D., Kenyon, C., McSherry, F.: On profit-maximizing envy-free pricing. In: Proc. 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1164–1173 (2005)
Hartline, J.D., Koltun, V.: Near-optimal pricing in near-linear time. In: Proc. Workshop on Algorithms and Data Structures (WADS). Lecture Notes in Computer Science, vol. 3608, pp. 422–431. Springer, Berlin (2005)
Labbé, M., Marcotte, P., Savard, G.: A bilevel model of taxation and its application to optimal highway pricing. Manag. Sci. 44(12), 1608–1622 (1998)
Papadimitriou, C.H., Yannakakis, M.: Optimization, approximation, and complexity classes. J. Comput. Syst. Sci. 43(3), 425–440 (1991)
Roch, S., Savard, G., Marcotte, P.: An approximation algorithm for Stackelberg network pricing. Networks 46(1), 57–67 (2005)
Schrijver, A.: Matroids, trees, stable sets. In: Combinatorial Optimization. Polyhedra and Efficiency, vol. B. Algorithms and Combinatorics, vol. 24. Springer, Berlin (2003). Chaps. 39–69
van Hoesel, S.: An overview of Stackelberg pricing in networks. Research Memoranda 042, Maastricht: METEOR, Maastricht Research School of Economics of Technology and Organization (2006)
von Stackelberg, H.: Marktform und Gleichgewicht (Market and Equilibrium). Springer, Vienna (1934)
Author information
Authors and Affiliations
Corresponding author
Additional information
A preliminary version of this article appeared in the Proceedings of the 10th Workshop on Algorithms and Data Structures (WADS 2007), see [7]. This work was partially supported by the Actions de Recherche Concertées (ARC) fund of the Communauté française de Belgique.
G. Joret is a Postdoctoral Researcher of the Fonds National de la Recherche Scientifique (F.R.S.–FNRS).
S. Langerman is a Research Associate of the Fonds National de la Recherche Scientifique (F.R.S.–FNRS).
Rights and permissions
About this article
Cite this article
Cardinal, J., Demaine, E.D., Fiorini, S. et al. The Stackelberg Minimum Spanning Tree Game. Algorithmica 59, 129–144 (2011). https://doi.org/10.1007/s00453-009-9299-y
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00453-009-9299-y