Document Open Access Logo

Equilibrium Computation in Atomic Splittable Routing Games

Authors Umang Bhaskar, Phani Raj Lolakapuri

PDF
Thumbnail PDF

File

LIPIcs.ESA.2018.58.pdf
  • Filesize: 0.51 MB
  • 14 pages

Document Identifiers

Author Details

Umang Bhaskar
  • Tata Institute of Fundamental Research, Mumbai, India
Phani Raj Lolakapuri
  • Tata Institute of Fundamental Research, Mumbai, India

Funding

  • Bhaskar, Umang: This work was partly funded by a Ramanujan Fellowship.

Cite As Get BibTex

Umang Bhaskar and Phani Raj Lolakapuri. Equilibrium Computation in Atomic Splittable Routing Games. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 58:1-58:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ESA.2018.58

Abstract

We present polynomial-time algorithms as well as hardness results for equilibrium computation in atomic splittable routing games, for the case of general convex cost functions. These games model traffic in freight transportation, market oligopolies, data networks, and various other applications. An atomic splittable routing game is played on a network where the edges have traffic-dependent cost functions, and player strategies correspond to flows in the network. A player can thus split its traffic arbitrarily among different paths. While many properties of equilibria in these games have been studied, efficient algorithms for equilibrium computation are known for only two cases: if cost functions are affine, or if players are symmetric. Neither of these conditions is met in most practical applications. We present two algorithms for routing games with general convex cost functions on parallel links. The first algorithm is exponential in the number of players, while the second is exponential in the number of edges; thus if either of these is small, we get a polynomial-time algorithm. These are the first algorithms for these games with convex cost functions. Lastly, we show that in general networks, given input C, it is NP-hard to decide if there exists an equilibrium where every player has cost at most C.

Subject Classification

ACM Subject Classification
  • Theory of computation → Network games
Keywords
  • Routing Games
  • Equilibrium Computation
  • Convex costs
  • Splittable flows

Metrics

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

Related Versions

References

  1. Heiner Ackermann, Heiko Röglin, and Berthold Vöcking. On the impact of combinatorial structure on congestion games. In 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 21-24 October 2006, Berkeley, California, USA, Proceedings, pages 613-622, 2006. Google Scholar
  2. Eitan Altman, Tamer Başar, Tania Jimenez, and Nahum Shimkin. Competitive routing in networks with polynomial costs. Automatic Control, IEEE Transactions on, 47(1):92-96, 2002. Google Scholar
  3. MJ Beckmann, CB Mc Guire, and CB Weinstein. Studies in the economics of transportation, Yale University Press. New Haven, Connecticut, USA, 1956. Google Scholar
  4. Umang Bhaskar, Lisa Fleischer, Darrell Hoy, and Chien-Chung Huang. On the uniqueness of equilibrium in atomic splittable routing games. Math. Oper. Res., 40(3):634-654, 2015. URL: http://dx.doi.org/10.1287/moor.2014.0688.
  5. Umang Bhaskar, Lisa Fleischer, and Chien-Chung Huang. The price of collusion in series-parallel networks. In Integer Programming and Combinatorial Optimization, 14th International Conference, IPCO 2010, Lausanne, Switzerland, June 9-11, 2010. Proceedings, pages 313-326, 2010. Google Scholar
  6. Umang Bhaskar and Phani Raj Lolakapuri. Equilibrium computation in atomic splittable routing games with convex cost functions. CoRR, abs/1804.10044, 2018. URL: http://arxiv.org/abs/1804.10044.
  7. Kshipra Bhawalkar, Martin Gairing, and Tim Roughgarden. Weighted congestion games: The price of anarchy, universal worst-case examples, and tightness. ACM Trans. Economics and Comput., 2(4):14:1-14:23, 2014. Google Scholar
  8. Roberto Cominetti, José R. Correa, and Nicolás E. Stier Moses. The impact of oligopolistic competition in networks. Operations Research, 57(6):1421-1437, 2009. URL: http://dx.doi.org/10.1287/opre.1080.0653.
  9. Constantinos Daskalakis. On the complexity of approximating a Nash equilibrium. ACM Trans. Algorithms, 9(3):23:1-23:35, 2013. Google Scholar
  10. Alex Fabrikant, Christos H. Papadimitriou, and Kunal Talwar. The complexity of pure Nash equilibria. In Proceedings of the 36th Annual ACM Symposium on Theory of Computing, Chicago, IL, USA, June 13-16, 2004, pages 604-612, 2004. Google Scholar
  11. Jugal Garg, Ruta Mehta, Vijay V. Vazirani, and Sadra Yazdanbod. Settling the complexity of Leontief and PLC exchange markets under exact and approximate equilibria. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 890-901, 2017. Google Scholar
  12. Itzhak Gilboa and Eitan Zemel. Nash and correlated equilibria: Some complexity considerations. Games and Economic Behavior, 1(1):80-93, 1989. Google Scholar
  13. Geoff Gordon and Ryan Tibshirani. Karush-Kuhn-Tucker conditions. Optimization, 10(725/36):725, 2012. Google Scholar
  14. Tobias Harks. Stackelberg strategies and collusion in network games with splittable flow. Theory of Computing Systems, 48(4):781-802, 2011. Google Scholar
  15. Tobias Harks, Ingo Kleinert, Max Klimm, and Rolf H Möhring. Computing network tolls with support constraints. Networks, 65(3):262-285, 2015. Google Scholar
  16. Tobias Harks and Veerle Timmermans. Equilibrium computation in atomic splittable singleton congestion games. In Integer Programming and Combinatorial Optimization - 19th International Conference, IPCO 2017, Waterloo, ON, Canada, June 26-28, 2017, Proceedings, pages 442-454, 2017. Google Scholar
  17. Ara Hayrapetyan, Éva Tardos, and Tom Wexler. The effect of collusion in congestion games. In Proceedings of the 38th Annual ACM Symposium on Theory of Computing, Seattle, WA, USA, May 21-23, 2006, pages 89-98, 2006. Google Scholar
  18. Chien-Chung Huang. Collusion in atomic splittable routing games. Theory Comput. Syst., 52(4):763-801, 2013. URL: http://dx.doi.org/10.1007/s00224-012-9421-4.
  19. Elias Koutsoupias and Christos H. Papadimitriou. Worst-case equilibria. Computer Science Review, 3(2):65-69, 2009. Google Scholar
  20. Patrice Marcotte. Algorithms for the network oligopoly problem. Journal of the Operational Research Society, pages 1051-1065, 1987. Google Scholar
  21. Ariel Orda, Raphael Rom, and Nahum Shimkin. Competitive routing in multiuser communication networks. IEEE/ACM Transactions on Networking (ToN), 1(5):510-521, 1993. Google Scholar
  22. Oran Richman and Nahum Shimkin. Topological uniqueness of the Nash equilibrium for selfish routing with atomic users. Math. Oper. Res., 32(1):215-232, 2007. URL: http://dx.doi.org/10.1287/moor.1060.0229.
  23. J Ben Rosen. Existence and uniqueness of equilibrium points for concave n-person games. Econometrica: Journal of the Econometric Society, pages 520-534, 1965. Google Scholar
  24. Robert W Rosenthal. A class of games possessing pure-strategy Nash equilibria. International Journal of Game Theory, 2(1):65-67, 1973. Google Scholar
  25. Tim Roughgarden and Florian Schoppmann. Local smoothness and the price of anarchy in splittable congestion games. Journal of Economic Theory, 156:317-342, 2015. Google Scholar
  26. Subhash Suri, Csaba D Tóth, and Yunhong Zhou. Selfish load balancing and atomic congestion games. Algorithmica, 47(1):79-96, 2007. Google Scholar
  27. Chaitanya Swamy. The effectiveness of Stackelberg strategies and tolls for network congestion games. ACM Trans. Algorithms, 8(4):36:1-36:19, 2012. URL: http://dx.doi.org/10.1145/2344422.2344426.
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 About DROPS Imprint Privacy Contact