Abstract
We study a new class of games which generalizes congestion games and its bottleneck variant. We introduce congestion games with mixed objectives to model network scenarios in which players seek to optimize for latency and bandwidths alike. We characterize the existence of pure Nash equilibria (PNE) and the convergence of improvement dynamics. For games that do not possess PNE we give bounds on the approximation ratio of approximate pure Nash equilibria.
This work was partially supported by the German Research Foundation (DFG) within the Collaborative Research Centre “On-The-Fly Computing” (SFB 901) and by the EU within FET project MULTIPLEX under contract no. 317532.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Ackermann, H., Röglin, H., Vöcking, B.: Pure nash equilibria in player-specific and weighted congestion games. Theoret. Comput. Sci. 410(17), 1552–1563 (2009)
Ackermann, H., Röglin, H., Vöcking, B.: On the impact of combinatorial structure on congestion games. J. ACM 55(6), 25:1–25:22 (2008)
Ackermann, H., Skopalik, A.: Complexity of pure nash equilibria in player-specific network congestion games. Internet Math. 5(4), 323–342 (2008)
Banner, R., Orda, A.: Bottleneck routing games in communication networks. IEEE J. Sel. Areas Commun. 25(6), 1173–1179 (2007)
Caragiannis, I., Fanelli, A., Gravin, N., Skopalik, A.: Efficient computation of approximate pure nash equilibria in congestion games. In: IEEE 52nd Annual Symposium on Foundations of Computer Science (FOCS), pp. 532–541 (2011)
Caragiannis, I., Fanelli, A., Gravin, N., Skopalik, A.: Approximate pure nash equilibria in weighted congestion games: existence, efficient computation, and structure. ACM Trans. Econ. Comput. 3(1), 2:1–2:32 (2015)
Chien, S., Sinclair, A.: Convergence to approximate nash equilibria in congestion games. Games Econ. Behav. 71(2), 315–327 (2011)
Cole, R., Dodis, Y., Roughgarden, T.: Bottleneck links, variable demand, and the tragedy of the commons. Networks 60(3), 194–203 (2012)
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)
Feldotto, M., Gairing, M., Skopalik, A.: Bounding the potential function in congestion games and approximate pure nash equilibria. In: Liu, T.-Y., Qi, Q., Ye, Y. (eds.) WINE 2014. LNCS, vol. 8877, pp. 30–43. Springer, Heidelberg (2014). doi:10.1007/978-3-319-13129-0_3
Fotakis, D., Kontogiannis, S., Spirakis, P.: Selfish unsplittable flows. Theoret. Comput. Sci. 348(2), 226–239 (2005)
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, New York (1979)
Hansknecht, C., Klimm, M., Skopalik, A.: Approximate pure nash equilibria in weighted congestion games. In: Jansen, K., Rolim, J.D.P., Devanur, N.R., Moore, C. (eds.) Approximation, Randomization, and Combinatorial Optimization, Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), vol. 28, pp. 242–257. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2014)
Harks, T., Hoefer, M., Schewior, K., Skopalik, A.: Routing games with progressive filling. IEEE/ACM Trans. Netw. 24(4), 2553–2562 (2016)
Harks, T., Hoefer, M., Klimm, M., Skopalik, A.: Computing pure nash and strong equilibria in bottleneck congestion games. Math. Program. 141(1), 193–215 (2013)
Harks, T., Klimm, M., Möhring, R.H.: Strong nash equilibria in games with the lexicographical improvement property. In: Leonardi, S. (ed.) WINE 2009. LNCS, vol. 5929, pp. 463–470. Springer, Heidelberg (2009). doi:10.1007/978-3-642-10841-9_43
Mavronicolas, M., Milchtaich, I., Monien, B., Tiemann, K.: Congestion games with player-specific constants. In: Kučera, L., Kučera, A. (eds.) MFCS 2007. LNCS, vol. 4708, pp. 633–644. Springer, Heidelberg (2007). doi:10.1007/978-3-540-74456-6_56
Milchtaich, I.: Congestion games with player-specific payoff functions. Games Econ. Behav. 13(1), 111–124 (1996)
Monderer, D., Shapley, L.S.: Potential games. Games Econ. Behav. 14(1), 124–143 (1996)
Rosenthal, R.W.: A class of games possessing pure-strategy nash equilibria. Int. J. Game Theor. 2(1), 65–67 (1973)
Skopalik, A., Vöcking, B.: Inapproximability of pure nash equilibria. In: Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, STOC 2008, pp. 355–364. ACM, New York (2008)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer International Publishing AG
About this paper
Cite this paper
Feldotto, M., Leder, L., Skopalik, A. (2016). Congestion Games with Mixed Objectives. In: Chan, TH., Li, M., Wang, L. (eds) Combinatorial Optimization and Applications. COCOA 2016. Lecture Notes in Computer Science(), vol 10043. Springer, Cham. https://doi.org/10.1007/978-3-319-48749-6_47
Download citation
DOI: https://doi.org/10.1007/978-3-319-48749-6_47
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-48748-9
Online ISBN: 978-3-319-48749-6
eBook Packages: Computer ScienceComputer Science (R0)