The Price of Stability of Weighted Congestion Games

Authors George Christodoulou, Martin Gairing, Yiannis Giannakopoulos , Paul G. Spirakis



PDF
Thumbnail PDF

File

LIPIcs.ICALP.2018.150.pdf
  • Filesize: 0.49 MB
  • 16 pages

Document Identifiers

Author Details

George Christodoulou
  • Department of Computer Science, University of Liverpool, Liverpool, UK
Martin Gairing
  • Department of Computer Science, University of Liverpool, Liverpool, UK
Yiannis Giannakopoulos
  • Department of Mathematics, TU Munich, Munich, Germany
Paul G. Spirakis
  • Department of Computer Science, University of Liverpool, Liverpool, UK, Computer Engineering and Informatics Department, University of Patras, Patras, Greece

Cite AsGet BibTex

George Christodoulou, Martin Gairing, Yiannis Giannakopoulos, and Paul G. Spirakis. The Price of Stability of Weighted Congestion Games. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 150:1-150:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.ICALP.2018.150

Abstract

We give exponential lower bounds on the Price of Stability (PoS) of weighted congestion games with polynomial cost functions. In particular, for any positive integer d we construct rather simple games with cost functions of degree at most d which have a PoS of at least Omega(Phi_d)^{d+1}, where Phi_d ~ d/ln d is the unique positive root of equation x^{d+1}=(x+1)^d. This essentially closes the huge gap between Theta(d) and Phi_d^{d+1} and asymptotically matches the Price of Anarchy upper bound. We further show that the PoS remains exponential even for singleton games. More generally, we also provide a lower bound of Omega((1+1/alpha)^d/d) on the PoS of alpha-approximate Nash equilibria, even for singleton games. All our lower bounds extend to network congestion games, and hold for mixed and correlated equilibria as well. On the positive side, we give a general upper bound on the PoS of alpha-approximate Nash equilibria, which is sensitive to the range W of the player weights and the approximation parameter alpha. We do this by explicitly constructing a novel approximate potential function, based on Faulhaber's formula, that generalizes Rosenthal's potential in a continuous, analytic way. From the general theorem, we deduce two interesting corollaries. First, we derive the existence of an approximate pure Nash equilibrium with PoS at most (d+3)/2; the equilibrium's approximation parameter ranges from Theta(1) to d+1 in a smooth way with respect to W. Secondly, we show that for unweighted congestion games, the PoS of alpha-approximate Nash equilibria is at most (d+1)/alpha.

Subject Classification

ACM Subject Classification
  • Theory of computation → Algorithmic game theory
  • Theory of computation → Quality of equilibria
  • Theory of computation → Network games
Keywords
  • Congestion games
  • price of stability
  • Nash equilibrium
  • approximate equilibrium
  • potential games

Metrics

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

References

  1. Milton Abramowitz and Irene A. Stegun. Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables. Dover, New York, 9th printing, 10th gpo printing edition, 1964. URL: http://people.maths.ox.ac.uk/~macdonald/aands/index.html.
  2. Heiner Ackermann, Heiko Röglin, and Berthold Vöcking. On the impact of combinatorial structure on congestion games. Journal of the ACM, 55(6):1-22, dec 2008. URL: http://dx.doi.org/10.1145/1455248.1455249.
  3. Sebastian Aland, Dominic Dumrauf, Martin Gairing, Burkhard Monien, and Florian Schoppmann. Exact price of anarchy for polynomial congestion games. SIAM Journal on Computing, 40(5):1211-1233, jan 2011. URL: http://dx.doi.org/10.1137/090748986.
  4. Susanne Albers. On the value of coordination in network design. SIAM Journal on Computing, 38(6):2273-2302, 2009. Google Scholar
  5. Elliot Anshelevich, Anirban Dasgupta, Jon Kleinberg, Éva 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, jan 2008. URL: http://dx.doi.org/10.1137/070680096.
  6. Baruch Awerbuch, Yossi Azar, and Amir Epstein. The price of routing unsplittable flow. SIAM Journal on Computing, 42(1):160-177, jan 2013. URL: http://dx.doi.org/10.1137/070702370.
  7. Kshipra Bhawalkar, Martin Gairing, and Tim Roughgarden. Weighted congestion games: The price of anarchy, universal worst-case examples, and tightness. ACM Trans. Econ. Comput., 2(4):141-1423, oct 2014. URL: http://dx.doi.org/10.1145/2629666.
  8. Vittorio Bilò. A unifying tool for bounding the quality of non-cooperative solutions in weighted congestion games. Theory of Computing Systems, 62, dec 2017. URL: http://dx.doi.org/10.1007/s00224-017-9826-1.
  9. Vittorio Bilò, Ioannis Caragiannis, Angelo Fanelli, and Gianpiero Monaco. Improved Lower Bounds on the Price of Stability of Undirected Network Design Games. Theory of Computing Systems, 52(4):668-686, may 2013. URL: http://dx.doi.org/10.1007/s00224-012-9411-6.
  10. Vittorio Bilò, Michele Flammini, and Luca Moscardelli. The price of stability for undirected broadcast network design with fair cost allocation is constant. Games and Economic Behavior, 2014. Google Scholar
  11. Vittorio Bilò and Cosimo Vinci. On the impact of singleton strategies in congestion games. In 25th Annual European Symposium on Algorithms, ESA 2017, September 4-6, 2017, Vienna, Austria, volume 87 of LIPIcs, pages 17:1-17:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017. URL: http://dx.doi.org/10.4230/LIPIcs.ESA.2017.17.
  12. Ioannis Caragiannis, Angelo Fanelli, Nick Gravin, and Alexander Skopalik. Efficient computation of approximate pure Nash equilibria in congestion games. In 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, oct 2011. URL: http://dx.doi.org/10.1109/focs.2011.50.
  13. Ioannis Caragiannis, Angelo Fanelli, Nick Gravin, and Alexander Skopalik. Approximate pure Nash equilibria in weighted congestion games: Existence, efficient computation, and structure. ACM Trans. Econ. Comput., 3(1):2:1-2:32, 2015. URL: http://dx.doi.org/10.1145/2614687.
  14. Ioannis Caragiannis, Michele Flammini, Christos Kaklamanis, Panagiotis Kanellopoulos, and Luca Moscardelli. Tight bounds for selfish and greedy load balancing. Algorithmica, 61(3):606-637, 2010. URL: http://dx.doi.org/10.1007/s00453-010-9427-8.
  15. George Christodoulou and Martin Gairing. Price of stability in polynomial congestion games. ACM Transactions on Economics and Computation, 4(2):1-17, dec 2015. URL: http://dx.doi.org/10.1145/2841229.
  16. George Christodoulou and Elias Koutsoupias. On the price of anarchy and stability of correlated equilibria of linear congestion games. In Algorithms - ESA 2005, 13th Annual European Symposium, pages 59-70, 2005. Google Scholar
  17. George Christodoulou and Elias Koutsoupias. The price of anarchy of finite congestion games. In STOC '05: Proceedings of the 37th annual ACM symposium on Theory of computing, pages 67-73, New York, NY, USA, 2005. ACM. URL: http://dx.doi.org/10.1145/1060590.1060600.
  18. George Christodoulou, Elias Koutsoupias, and Paul G. Spirakis. On the performance of approximate equilibria in congestion games. Algorithmica, 61(1):116-140, 2011. URL: http://dx.doi.org/10.1007/s00453-010-9449-2.
  19. John H. Conway and Richard K. Guy. The Book of Numbers. Springer New York, 1996. URL: http://dx.doi.org/10.1007/978-1-4612-4072-3.
  20. Juliane Dunkel and Andreas S. Schulz. On the complexity of pure-strategy Nash equilibria in congestion and local-effect games. Mathematics of Operations Research, 33(4):851-868, 2008. Google Scholar
  21. Alex Fabrikant, Christos Papadimitriou, and Kunal Talwar. The complexity of pure Nash equilibria. In Proceedings of the Thirty-sixth Annual ACM Symposium on Theory of Computing, STOC '04, pages 604-612, New York, NY, USA, 2004. URL: http://dx.doi.org/10.1145/1007352.1007445.
  22. Matthias Feldotto, Martin Gairing, Grammateia Kotsialou, and Alexander Skopalik. Computing approximate pure Nash equilibria in Shapley value weighted congestion games. In Web and Internet Economics, pages 191-204. Springer International Publishing, 2017. URL: http://dx.doi.org/10.1007/978-3-319-71924-5_14.
  23. Amos Fiat, Haim Kaplan, Meital Levy, Svetlana Olonetsky, and Ronen Shabo. On the price of stability for designing undirected networks with fair cost allocations. In Michele Bugliesi, Bart Preneel, Vladimiro Sassone, and Ingo Wegener, editors, Automata, Languages and Programming: 33rd International Colloquium (ICALP), pages 608-618, 2006. URL: http://dx.doi.org/10.1007/11786986_53.
  24. Dimitris Fotakis, Spyros Kontogiannis, Elias Koutsoupias, Marios Mavronicolas, and Paul Spirakis. The structure and complexity of Nash equilibria for a selfish routing game. Theoretical Computer Science, 410(36):3305-3326, 2009. URL: http://dx.doi.org/10.1016/j.tcs.2008.01.004.
  25. Dimitris Fotakis, Spyros Kontogiannis, and Paul Spirakis. Selfish unsplittable flows. Theoretical Computer Science, 348(2):226-239, 2005. Google Scholar
  26. Yiannis Giannakopoulos, George Christodoulou, Martin Gairing, and Paul Spirakis. The price of stability of weighted congestion games. CoRR, abs/1802.09952, 2018. URL: http://arxiv.org/abs/arXiv:1802.09952.
  27. M. Goemans, Vahab Mirrokni, and A. Vetta. Sink equilibria and convergence. In 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05), pages 142-151, Oct 2005. URL: http://dx.doi.org/10.1109/SFCS.2005.68.
  28. Ronald L. Graham, Donald E. Knuth, and Oren Patashnik. Concrete Mathematics: A Foundation for Computer Science. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 1989. Google Scholar
  29. Christoph Hansknecht, Max Klimm, and Alexander Skopalik. Approximate pure Nash equilibria in weighted congestion games. In Klaus Jansen, José D. P. Rolim, Nikhil R. Devanur, and Cristopher Moore, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014), volume 28 of Leibniz International Proceedings in Informatics (LIPIcs), pages 242-257. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2014. URL: http://dx.doi.org/10.4230/LIPIcs.APPROX-RANDOM.2014.242.
  30. Tobias Harks and Max Klimm. On the existence of pure Nash equilibria in weighted congestion games. Mathematics of Operations Research, 37(3):419-436, 2012. URL: http://dx.doi.org/10.1287/moor.1120.0543.
  31. Tobias Harks, Max Klimm, and Rolf H Möhring. Characterizing the existence of potential functions in weighted congestion games. Theory Comput Syst, 49:46-70, 2011. URL: http://dx.doi.org/10.1007/s00224-011-9315-x.
  32. Tobias Harks, Max Klimm, and Rolf H Möhring. Strong equilibria in games with the lexicographical improvement property. International Journal of Game Theory, 42(2):461-482, 2012. URL: http://dx.doi.org/10.1007/s00182-012-0322-1.
  33. Donald E. Knuth. Johann Faulhaber and sums of powers. Mathematics of Computation, 61(203):277-277, sep 1993. URL: http://dx.doi.org/10.1090/s0025-5718-1993-1197512-7.
  34. Elias Koutsoupias and Christos Papadimitriou. Worst-case equilibria. In 16th Annual Symposium on Theoretical Aspects of Computer Science, STACS '99, pages 404-413, 1999. Google Scholar
  35. Euiwoong Lee and Katrina Ligett. Improved bounds on the price of stability in network cost sharing games. In Proceedings of the 14th ACM Conference on Electronic Commerce, EC '13, pages 607-620. ACM, 2013. URL: http://dx.doi.org/10.1145/2482540.2482562.
  36. Lavy Libman and Ariel Orda. Atomic resource sharing in noncooperative networks. Telecommunication Systems, 17(4):385-409, Aug 2001. URL: http://dx.doi.org/10.1023/A:1016770831869.
  37. Dov Monderer and Lloyd S. Shapley. Potential games. Games and economic behavior, 14(1):124-143, 1996. Google Scholar
  38. Noam Nisan, Tim Roughgarden, Éva Tardos, and Vijay Vazirani, editors. Algorithmic Game Theory. Cambridge University Press, 2007. Google Scholar
  39. Robert W Rosenthal. A class of games possessing pure-strategy Nash equilibria. International Journal of Game Theory, 2(1):65-67, 1973. Google Scholar
  40. Robert W Rosenthal. The network equilibrium problem in integers. Networks, 3(1):53-59, 1973. Google Scholar
  41. Tim Roughgarden. Intrinsic robustness of the price of anarchy. J. ACM, 62(5):32:1-32:42, 2015. URL: http://dx.doi.org/10.1145/2806883.
  42. Tim Roughgarden and Éva Tardos. How bad is selfish routing? J. ACM, 49(2):236-259, mar 2002. URL: http://dx.doi.org/10.1145/506147.506153.
  43. Tim Roughgarden and Éva Tardos. Bounding the inefficiency of equilibria in nonatomic congestion games. Games and Economic Behavior, 47(2):389-403, may 2004. URL: http://dx.doi.org/10.1016/j.geb.2003.06.004.
  44. Andreas S. Schulz and Nicolás Stier Moses. On the performance of user equilibria in traffic networks. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '03, pages 86-87, Philadelphia, PA, USA, 2003. Society for Industrial and Applied Mathematics. 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