Document Open Access Logo

Network Investment Games with Wardrop Followers

Authors Daniel Schmand , Marc Schröder , Alexander Skopalik

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2019.151.pdf
  • Filesize: 437 kB
  • 14 pages

Document Identifiers

Author Details

Daniel Schmand
  • Goethe University Frankfurt, Germany
Marc Schröder
  • RWTH Aachen University, Germany
Alexander Skopalik
  • University of Twente, Netherlands

Cite AsGet BibTex

Daniel Schmand, Marc Schröder, and Alexander Skopalik. Network Investment Games with Wardrop Followers. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 151:1-151:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ICALP.2019.151

Abstract

We study a two-sided network investment game consisting of two sets of players, called providers and users. The game is set in two stages. In the first stage, providers aim to maximize their profit by investing in bandwidth of cloud computing services. The investments of the providers yield a set of usable services for the users. In the second stage, each user wants to process a task and therefore selects a bundle of services so as to minimize the total processing time. We assume the total processing time to be separable over the chosen services and the processing time of each service to depend on the utilization of the service and the installed bandwidth. We provide insights on how competition between providers affects the total costs of the users and show that every game on a series-parallel graph can be reduced to an equivalent single edge game when analyzing the set of subgame perfect Nash equilibria.

Subject Classification

ACM Subject Classification
  • Theory of computation → Algorithmic game theory and mechanism design
  • Theory of computation → Network games
Keywords
  • Network Investment Game
  • Wardrop Equilibrium
  • Subgame Perfect Nash Equilibrium

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Daron Acemoglu and Asuman Ozdaglar. Competition and efficiency in congested markets. Mathematics of Operations Research, 32(1):1-31, 2007. Google Scholar
  2. Daron Acemoglu and Asuman Ozdaglar. Competition in parallel-serial networks. IEEE Journal on Selected Areas in Communications, 25(6), 2007. Google Scholar
  3. Amazon Web Services - Cloud Computing Services. https://aws.amazon.com/pricing/. Accessed: 2018-12-19.
  4. Elliot Anshelevich, Anirban Dasgupta, Jon Kleinberg, Eva Tardos, Tom Wexler, and Tim Roughgarden. The price of stability for network design with fair cost allocation. SIAM Journal on Computing, 38(4):1602-1623, 2008. Google Scholar
  5. Elliot Anshelevich, Anirban Dasgupta, Éva Tardos, and Tom Wexler. Near-optimal network design with selfish agents. In ACM Symposium on Theory of Computing, pages 511-520, 2003. Google Scholar
  6. Maria-Florina Balcan, Avrim Blum, and Yishay Mansour. Item pricing for revenue maximization. In Proceedings of the 9th ACM conference on Electronic commerce, pages 50-59. ACM, 2008. Google Scholar
  7. Martin Beckmann, Charles McGuire, and Christopher Winsten. Studies in the Economics of Transportation. Technical report, Cowles Commission for Research in Economics, 1956. Google Scholar
  8. Davide Bilò, Luciano Gualà, Guido Proietti, and Peter Widmayer. Computational aspects of a 2-player Stackelberg shortest paths tree game. In International Workshop on Internet and Network Economics, pages 251-262. Springer, 2008. Google Scholar
  9. Toni Böhnlein, Stefan Kratsch, and Oliver Schaudt. Revenue maximization in Stackelberg Pricing Games: Beyond the combinatorial setting. In LIPIcs-Leibniz International Proceedings in Informatics, volume 80. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017. Google Scholar
  10. Patrick Briest, Martin Hoefer, and Piotr Krysta. Stackelberg network pricing games. Algorithmica, 62(3-4):733-753, 2012. Google Scholar
  11. Sergio Cabello. Stackelberg Shortest Path Tree Game, Revisited. CoRR, abs/1207.2317, 2012. URL: http://arxiv.org/abs/1207.2317.
  12. Jean Cardinal, Erik D Demaine, Samuel Fiorini, Gwenaël Joret, Stefan Langerman, Ilan Newman, and Oren Weimann. The Stackelberg minimum spanning tree game. Algorithmica, 59(2):129-144, 2011. Google Scholar
  13. José Correa, Cristóbal Guzmán, Thanasis Lianeas, Evdokia Nikolova, and Marc Schröder. Network Pricing: How to Induce Optimal Flows Under Strategic Link Operators. In ACM Conference on Economics and Computation, pages 375-392, 2018. Google Scholar
  14. José Correa, Roger Lederman, and Nicolás Stier-Moses. Sensitivity analysis of markup equilibria in complementary markets. Operations Research Letters, 42(2):173-179, 2014. Google Scholar
  15. Antoine-Augustin Cournot. Recherches sur les principes mathématiques de la théorie des richesses par Augustin Cournot. Hachette, Paris, 1838. Google Scholar
  16. Stella Dafermos and Frederick Sparrow. The traffic assignment problem for a general network. Journal of Research of the National Bureau of Standards B, 73(2):91-118, 1969. Google Scholar
  17. Google Cloud. https://cloud.google.com/pricing/. Accessed: 2018-12-19.
  18. Tobias Harks, Marc Schröder, and Dries Vermeulen. Toll Caps in Privatized Road Networks. European Journal of Operational Research, 276(3):947-956, 2019. Google Scholar
  19. Tobias Harks and Veerle Timmermans. Computing Equilibria in Atomic Splittable Polymatroid Congestion Games with Convex Costs. arXiv preprint, 2018. URL: http://arxiv.org/abs/1808.04712.
  20. Ara Hayrapetyan, Éva Tardos, and Tom Wexler. A network pricing game for selfish traffic. Distributed Computing, 19(4):255-266, 2007. Google Scholar
  21. Jeff Hecht. The bandwidth bottleneck that is throttling the Internet. Nature, 536(7615):139-142, 2016. Google Scholar
  22. Ramesh Johari, Gabriel Weintraub, and Benjamin Van Roy. Investment and market structure in industries with congestion. Operations Research, 58(5):1303-1317, 2010. Google Scholar
  23. Elias Koutsoupias and Christos Papadimitriou. Worst-case equilibria. In Annual Symposium on Theoretical Aspects of Computer Science, pages 404-413, 1999. Google Scholar
  24. Martine Labbé, Patrice Marcotte, and Gilles Savard. A bilevel model of taxation and its application to optimal highway pricing. Management science, 44(12-part-1):1608-1622, 1998. Google Scholar
  25. Henry Lin, Tim Roughgarden, and Éva Tardos. A stronger bound on Braess’s Paradox. In ACM-SIAM Symposium on Discrete Algorithms, pages 340-341, 2004. Google Scholar
  26. Microsoft Azure Cloud Computing Platform &Services. https://azure.microsoft.com/en-us/pricing. Accessed: 2018-12-19.
  27. Igal Milchtaich. Congestion games with player-specific payoff functions. Games and Economic Behavior, 13(1):111-124, 1996. Google Scholar
  28. Hervé Moulin. Equal or proportional division of a surplus, and other methods. International Journal of Game Theory, 16(3):161-186, 1987. Google Scholar
  29. Asuman Ozdaglar. Price competition with elastic traffic. Networks, 52(3):141-155, 2008. Google Scholar
  30. Tim Roughgarden and Éva Tardos. How bad is selfish routing? Journal of the ACM, 49(2):236-259, 2002. Google Scholar
  31. Daniel Schmand, Marc Schröder, and Alexander Skopalik. Network Investment Games with Wardrop Followers. CoRR, abs/1904.10417, 2019. URL: http://arxiv.org/abs/1904.10417.
  32. Heinrich von Stackelberg. Marktform und Gleichgewicht. Springer, 1934. Google Scholar
  33. John Wardrop. Some theoretical aspects of road traffic research. In Inst Civil Engineers Proc London/UK/, 1952. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact