Abstract
We provide a unifying, black-box tool for establishing existence of approximate equilibria in weighted congestion games and, at the same time, bounding their Price of Stability. Our framework can handle resources with general costs—including, in particular, decreasing ones—and is formulated in terms of a set of parameters which are determined via elementary analytic properties of the cost functions.
We demonstrate the power of our tool by applying it to recover the recent result of Caragiannis and Fanelli [ICALP’19] for polynomial congestion games; improve upon the bounds for fair cost sharing games by Chen and Roughgarden [Theory Comput. Syst., 2009]; and derive new bounds for nondecreasing concave costs. An interesting feature of our framework is that it can be readily applied to mixtures of different families of cost functions; for example, we provide bounds for games whose resources are conical combinations of polynomial and concave costs.
In the core of our analysis lies the use of a unifying approximate potential function which is simple and general enough to be applicable to arbitrary congestion games, but at the same time powerful enough to produce state-of-the-art bounds across a range of different cost functions.
Supported by the Alexander von Humboldt Foundation with funds from the German Federal Ministry of Education and Research (BMBF). Y. Giannakopoulos is an associated researcher with the Research Training Group GRK 2201 “Advanced Optimization in a Networked Economy”, funded by the German Research Foundation (DFG). A full version of this paper is available at [16]: https://arxiv.org/abs/2005.10101.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Anshelevich, E., Dasgupta, A., Kleinberg, J., Tardos, É., Wexler, T., Roughgarden, T.: The price of stability for network design with fair cost allocation. SIAM J. Comput. 38(4), 1602–1623 (2008). https://doi.org/10.1137/070680096
Bilò, V., Caragiannis, I., Fanelli, A., Monaco, G.: Improved lower bounds on the price of stability of undirected network design games. Theory Comput. Syst. 52(4), 668–686 (2013). https://doi.org/10.1007/s00224-012-9411-6
Bilò, V., Flammini, M., Moscardelli, L.: The price of stability for undirected broadcast network design with fair cost allocation is constant. Games Econ. Behav. (2014). https://doi.org/10.1016/j.geb.2014.09.010
Caragiannis, I., Fanelli, A.: On approximate pure Nash equilibria in weighted congestion games with polynomial latencies. In: Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP), pp. 133:1–133:12 (2019). https://doi.org/10.4230/LIPIcs.ICALP.2019.133
Caragiannis, I., Fanelli, A., Gravin, N., Skopalik, A.: Efficient computation of approximate pure Nash equilibria in congestion games. In: Proceedings of the 52nd IEEE Annual Symposium on Foundations of Computer Science (FOCS), pp. 532–541 (2011). https://doi.org/10.1109/focs.2011.50
Chen, H.L., Roughgarden, T.: Network design with weighted players. Theory Comput. Syst. 45(2), 302–324 (2009). https://doi.org/10.1007/s00224-008-9128-8
Christodoulou, G., Gairing, M., Giannakopoulos, Y., Poças, D., Waldmann, C.: Existence and complexity of approximate equilibria in weighted congestion games. In: Proceedings of the 47th International Colloquium on Automata, Languages, and Programming (ICALP), pp. 32:1–32:18 (2020). https://doi.org/10.4230/LIPIcs.ICALP.2020.32
Christodoulou, G., Gairing, M., Giannakopoulos, Y., Spirakis, P.G.: The price of stability of weighted congestion games. SIAM J. Comput. 48(5), 1544–1582 (2019). https://doi.org/10.1137/18M1207880
Christodoulou, G., Koutsoupias, E., Spirakis, P.G.: On the performance of approximate equilibria in congestion games. Algorithmica 61(1), 116–140 (2011). https://doi.org/10.1007/s00453-010-9449-2
Correa, J.R., Schulz, A.S., Stier-Moses, N.E.: Selfish routing in capacitated networks. Math. Oper. Res. 29(4), 961–976 (2004). https://doi.org/10.1287/moor.1040.0098
Dunkel, J., Schulz, A.S.: On the complexity of pure-strategy Nash equilibria in congestion and local-effect games. Math. Oper. Res. 33(4), 851–868 (2008). https://doi.org/10.1287/moor.1080.0322
Fiat, A., Kaplan, H., Levy, M., Olonetsky, S., Shabo, R.: On the price of stability for designing undirected networks with fair cost allocations. In: Proceedings of the 33rd International ColloquiumAutomata, Languages and Programming (ICALP), pp. 608–618 (2006). https://doi.org/10.1007/11786986_53
Fotakis, D., Kontogiannis, S., Koutsoupias, E., Mavronicolas, M., Spirakis, P.: The structure and complexity of Nash equilibria for a selfish routing game. Theoret. Comput. Sci. 410(36), 3305–3326 (2009). https://doi.org/10.1016/j.tcs.2008.01.004
Fotakis, D., Kontogiannis, S., Spirakis, P.: Selfish unsplittable flows. Theoret. Comput. Sci. 348(2), 226–239 (2005). https://doi.org/10.1016/j.tcs.2005.09.024
Freeman, R., Haney, S., Panigrahi, D.: On the price of stability of undirected multicast games. In: Cai, Y., Vetta, A. (eds.) WINE 2016. LNCS, vol. 10123, pp. 354–368. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-54110-4_25
Giannakopoulos, Y., Poças, D.: A unifying approximate potential for weighted congestion games. CoRR abs/2005.10101, May 2020. https://arxiv.org/abs/2005.10101
Goemans, M., Mirrokni, V., Vetta, A.: Sink equilibria and convergence. In: Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 142–151 (2005). https://doi.org/10.1109/SFCS.2005.68
Hansknecht, C., Klimm, M., Skopalik, A.: Approximate pure Nash equilibria in weighted congestion games. In: Proceedings of the 17th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), pp. 242–257 (2014). https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2014.242
Harks, T., Klimm, M.: On the existence of pure Nash equilibria in weighted congestion games. Math. Oper. Res. 37(3), 419–436 (2012). https://doi.org/10.1287/moor.1120.0543
Harks, T., Klimm, M., Möhring, R.H.: Strong equilibria in games with the lexicographical improvement property. Int. J. Game Theory 42(2), 461–482 (2012). https://doi.org/10.1007/s00182-012-0322-1
Koutsoupias, E., Papadimitriou, C.: Worst-case equilibria. In: Meinel, C., Tison, S. (eds.) STACS 1999. LNCS, vol. 1563, pp. 404–413. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-49116-3_38
Libman, L., Orda, A.: Atomic resource sharing in noncooperative networks. Telecommun. Syst. 17(4), 385–409 (2001). https://doi.org/10.1023/A:1016770831869
Monderer, D., Shapley, L.S.: Potential games. Games Econ. Behav. 14(1), 124–143 (1996). https://doi.org/10.1006/game.1996.0044
Nisan, N., Roughgarden, T., Tardos, É., Vazirani, V. (eds.): Algorithmic Game Theory. Cambridge University Press (2007). https://doi.org/10.1017/CBO9780511800481
Panagopoulou, P.N., Spirakis, P.G.: Algorithms for pure Nash equilibria in weighted congestion games. J. Exp. Algorithmics 11, 27 (2007). https://doi.org/10.1145/1187436.1216584
Papadimitriou, C.: Algorithms, games, and the internet. In: Proceedings of the 33rd Annual ACM Symposium on Theory of Computing (STOC), pp. 749–753 (2001). https://doi.org/10.1145/380752.380883
Rosenthal, R.W.: A class of games possessing pure-strategy Nash equilibria. Int. J. Game Theory 2(1), 65–67 (1973). https://doi.org/10.1007/BF01737559
Rosenthal, R.W.: The network equilibrium problem in integers. Networks 3(1), 53–59 (1973). https://doi.org/10.1002/net.3230030104
Roughgarden, T.: Routing games. In: Nisan, N., Roughgarden, T., Tardos, É., Vazirani, V. (eds.) Algorithmic Game Theory, Chap. 18. Cambridge University Press (2007). https://doi.org/10.1017/CBO9780511800481.020
Roughgarden, T.: Twenty Lectures on Algorithmic Game Theory. Cambridge University Press (2016). https://doi.org/10.1017/cbo9781316779309
Tardos, É., Wexler, T.: Network formation games and the potential function method. In: Nisan, N., Roughgarden, T., Tardos, É., Vazirani, V. (eds.) Algorithmic Game Theory, Chap. 19. Cambridge University Press (2007). https://doi.org/10.1017/cbo9780511800481.021
Vöcking, B.: Selfish load balancing. In: Nisan, N., Roughgarden, T., Tardos, É., Vazirani, V. (eds.) Algorithmic Game Theory, Chap. 20. Cambridge University Press (2007). https://doi.org/10.1017/cbo9780511800481.022
Acknowledgements
We thank Martin Gairing for interesting discussions.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Giannakopoulos, Y., Poças, D. (2020). A Unifying Approximate Potential for Weighted Congestion Games. In: Harks, T., Klimm, M. (eds) Algorithmic Game Theory. SAGT 2020. Lecture Notes in Computer Science(), vol 12283. Springer, Cham. https://doi.org/10.1007/978-3-030-57980-7_7
Download citation
DOI: https://doi.org/10.1007/978-3-030-57980-7_7
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-57979-1
Online ISBN: 978-3-030-57980-7
eBook Packages: Computer ScienceComputer Science (R0)