Skip to main content

2015 | OriginalPaper | Buchkapitel

A Selective Tour Through Congestion Games

verfasst von : Dimitris Fotakis

Erschienen in: Algorithms, Probability, Networks, and Games

Verlag: Springer International Publishing

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

We give a sketchy and mostly informal overview of research on algorithmic properties of congestion games in the last ten years. We discuss existence of potential functions and pure Nash equilibria in games with weighted players, simple and fast algorithms that reach a pure Nash equilibrium, and efficient approaches to improving the Price of Anarchy.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Fußnoten
1
Note that matroid congestion games and congestion games on extension-parallel networks have a different combinatorial structure and may have quite different properties. E.g., a network consisting of two parallel-link networks composed in series is not extension-parallel, but corresponds to a symmetric matroid congestion game.
 
2
For some \(\varepsilon > 0\), a configuration \(\varvec{s}\) is an \(\varepsilon \)-Nash equilibrium if for every path p with \(s_p > 0\) and every path \(p'\), \(d_p(\varvec{s}) \le d_{p'}(\varvec{s}) + \varepsilon \).
 
Literatur
1.
Zurück zum Zitat Ackermann, H., Röglin, H., Vöcking, B.: On the impact of combinatorial structre on congestion games. J. Assoc. Comput. Mach. 55(6), 1–22 (2008)CrossRefMATH Ackermann, H., Röglin, H., Vöcking, B.: On the impact of combinatorial structre on congestion games. J. Assoc. Comput. Mach. 55(6), 1–22 (2008)CrossRefMATH
2.
Zurück zum Zitat Aland, S., Dumrauf, D., Gairing, M., Monien, B., Schoppmann, F.: Exact price of anarchy for polynomial congestion games. SIAM J. Comput. 40(5), 1211–1233 (2011)MathSciNetCrossRefMATH Aland, S., Dumrauf, D., Gairing, M., Monien, B., Schoppmann, F.: Exact price of anarchy for polynomial congestion games. SIAM J. Comput. 40(5), 1211–1233 (2011)MathSciNetCrossRefMATH
3.
Zurück zum Zitat Althöfer, I.: On sparse approximations to randomized strategies and convex combinations. Linear Algebra Appl. 99, 339–355 (1994)MathSciNetCrossRefMATH Althöfer, I.: On sparse approximations to randomized strategies and convex combinations. Linear Algebra Appl. 99, 339–355 (1994)MathSciNetCrossRefMATH
4.
Zurück zum Zitat Anshelevich, E., Dasgupta, A., Kleinberg, J.M., Tardos, É., Wexler, T., Roughgarden, T.: The price of stability for network design with fair cost allocation. SIAM J. Comput. 38(4), 1602–1623 (2008)MathSciNetCrossRefMATH Anshelevich, E., Dasgupta, A., Kleinberg, J.M., Tardos, É., Wexler, T., Roughgarden, T.: The price of stability for network design with fair cost allocation. SIAM J. Comput. 38(4), 1602–1623 (2008)MathSciNetCrossRefMATH
5.
Zurück zum Zitat Ashlagi, I., Krysta, P., Tennenholtz, M.: Social context games. In: Papadimitriou, C., Zhang, S. (eds.) WINE 2008. LNCS, vol. 5385, pp. 675–683. Springer, Heidelberg (2008) CrossRef Ashlagi, I., Krysta, P., Tennenholtz, M.: Social context games. In: Papadimitriou, C., Zhang, S. (eds.) WINE 2008. LNCS, vol. 5385, pp. 675–683. Springer, Heidelberg (2008) CrossRef
6.
Zurück zum Zitat Awerbuch, B., Azar, Y., Epstein, A.: The price of routing unsplittable flow. In: Proceedings of the 37th ACM Symposium on Theory of Computing (STOC 2005), pp. 57–66 (2005) Awerbuch, B., Azar, Y., Epstein, A.: The price of routing unsplittable flow. In: Proceedings of the 37th ACM Symposium on Theory of Computing (STOC 2005), pp. 57–66 (2005)
7.
Zurück zum Zitat Barman, S.: Approximating Carathéodory’s theorem and nash equilibria. In: Proceedings of the 47th ACM Symposium on Theory of Computing (STOC 2015) (2015) Barman, S.: Approximating Carathéodory’s theorem and nash equilibria. In: Proceedings of the 47th ACM Symposium on Theory of Computing (STOC 2015) (2015)
8.
Zurück zum Zitat Beckmann, M., McGuire, C.B., Winsten, C.B.: Studies in the Economics of Transportation. Yale University Press, New Haven (1956) Beckmann, M., McGuire, C.B., Winsten, C.B.: Studies in the Economics of Transportation. Yale University Press, New Haven (1956)
9.
10.
Zurück zum Zitat Braess, D.: Über ein paradox aus der Verkehrsplanung. Unternehmensforschung 12, 258–268 (1968)MathSciNetMATH Braess, D.: Über ein paradox aus der Verkehrsplanung. Unternehmensforschung 12, 258–268 (1968)MathSciNetMATH
11.
Zurück zum Zitat Caragiannis, I., Flammini, M., Kaklamanis, C., Kanellopoulos, P., Moscardelli, L.: Tight bounds for selfish and greedy load balancing. Algorithmica 61(3), 606–637 (2011)MathSciNetCrossRefMATH Caragiannis, I., Flammini, M., Kaklamanis, C., Kanellopoulos, P., Moscardelli, L.: Tight bounds for selfish and greedy load balancing. Algorithmica 61(3), 606–637 (2011)MathSciNetCrossRefMATH
12.
Zurück zum Zitat Caragiannis, I., Kaklamanis, C., Kanellopoulos, P.: Taxes for linear atomic congestion games. ACM Trans. Algorithms 7(1), 13 (2010)MathSciNetCrossRefMATH Caragiannis, I., Kaklamanis, C., Kanellopoulos, P.: Taxes for linear atomic congestion games. ACM Trans. Algorithms 7(1), 13 (2010)MathSciNetCrossRefMATH
13.
Zurück zum Zitat Christodoulou, G., Koutsoupias, E.: The Price of anarchy of finite congestion games. In: Proceedings of the 37th ACM Symposium on Theory of Computing (STOC 2005), pp. 67–73 (2005) Christodoulou, G., Koutsoupias, E.: The Price of anarchy of finite congestion games. In: Proceedings of the 37th ACM Symposium on Theory of Computing (STOC 2005), pp. 67–73 (2005)
14.
Zurück zum Zitat Christodoulou, G., Koutsoupias, E., Spirakis, P.G.: On the performance of approximate equilibria in congestion games. Algorithmica 61(1), 116–140 (2011)MathSciNetCrossRefMATH Christodoulou, G., Koutsoupias, E., Spirakis, P.G.: On the performance of approximate equilibria in congestion games. Algorithmica 61(1), 116–140 (2011)MathSciNetCrossRefMATH
15.
Zurück zum Zitat Chung, F., Young, S.J.: Braess’s paradox in large sparse graphs. In: Saberi, A. (ed.) WINE 2010. LNCS, vol. 6484, pp. 194–208. Springer, Heidelberg (2010) CrossRef Chung, F., Young, S.J.: Braess’s paradox in large sparse graphs. In: Saberi, A. (ed.) WINE 2010. LNCS, vol. 6484, pp. 194–208. Springer, Heidelberg (2010) CrossRef
16.
17.
Zurück zum Zitat Correa, J.R., Schulz, A.S., Stier, N.E.: Moses. selfish routing in capacitated networks. Math. Oper. Res. 29(4), 961–976 (2004)MathSciNetCrossRefMATH Correa, J.R., Schulz, A.S., Stier, N.E.: Moses. selfish routing in capacitated networks. Math. Oper. Res. 29(4), 961–976 (2004)MathSciNetCrossRefMATH
18.
Zurück zum Zitat Correa, J.R., Stier-Moses, N.E.: Stackelberg Routing in Atomic Network Games. In: Technical report DRO-2007-03, Columbia Business School (2007) Correa, J.R., Stier-Moses, N.E.: Stackelberg Routing in Atomic Network Games. In: Technical report DRO-2007-03, Columbia Business School (2007)
19.
Zurück zum Zitat Fabrikant, A., Papadimitriou, C., Talwar, K.: The complexity of pure nash equilibria. In: Proceedings of the 36th ACM Symposium on Theory of Computing (STOC 2004), pp. 604–612 (2004) Fabrikant, A., Papadimitriou, C., Talwar, K.: The complexity of pure nash equilibria. In: Proceedings of the 36th ACM Symposium on Theory of Computing (STOC 2004), pp. 604–612 (2004)
20.
Zurück zum Zitat Fleischer, L., Jain, K., Mahdian, M.: Tolls for heterogeneous selfish users in multicommodity networks and generalized congestion games. In: Proceedings of the 45th IEEE Symposium on Foundations of Computer Science (FOCS 2004), pp. 277–285 (2004) Fleischer, L., Jain, K., Mahdian, M.: Tolls for heterogeneous selfish users in multicommodity networks and generalized congestion games. In: Proceedings of the 45th IEEE Symposium on Foundations of Computer Science (FOCS 2004), pp. 277–285 (2004)
22.
Zurück zum Zitat Fotakis, D.: Congestion games with linearly independent paths: convergence time and price of anarchy. Theory Comput. Syst. 47(1), 113–136 (2010)MathSciNetCrossRefMATH Fotakis, D.: Congestion games with linearly independent paths: convergence time and price of anarchy. Theory Comput. Syst. 47(1), 113–136 (2010)MathSciNetCrossRefMATH
23.
Zurück zum Zitat Fotakis, D., Gkatzelis, V., Kaporis, A.C., Spirakis, P.G.: The impact of social ignorance on weighted congestion games. Theory Comput. Syst. 50(3), 559–578 (2012)MathSciNetCrossRefMATH Fotakis, D., Gkatzelis, V., Kaporis, A.C., Spirakis, P.G.: The impact of social ignorance on weighted congestion games. Theory Comput. Syst. 50(3), 559–578 (2012)MathSciNetCrossRefMATH
24.
Zurück zum Zitat Fotakis, D., Kaporis, A.C., Spirakis, P.G.: Efficient methods for selfish network design. Theor. Comput. Sci. 448, 9–20 (2012)MathSciNetCrossRefMATH Fotakis, D., Kaporis, A.C., Spirakis, P.G.: Efficient methods for selfish network design. Theor. Comput. Sci. 448, 9–20 (2012)MathSciNetCrossRefMATH
25.
Zurück zum Zitat Fotakis, D., Kaporis, A.C., Lianeas, T., Spirakis, P.G.: Resolving braess’s paradox in random networks. In: Chen, Y., Immorlica, N. (eds.) WINE 2013. LNCS, vol. 8289, pp. 188–201. Springer, Heidelberg (2013) CrossRef Fotakis, D., Kaporis, A.C., Lianeas, T., Spirakis, P.G.: Resolving braess’s paradox in random networks. In: Chen, Y., Immorlica, N. (eds.) WINE 2013. LNCS, vol. 8289, pp. 188–201. Springer, Heidelberg (2013) CrossRef
26.
Zurück zum Zitat Fotakis, D., Kaporis, A.C., Spirakis, P.G.: Atomic congestion games: fast, myopic and concurrent. Theory Comput. Syst. 47(1), 38–59 (2010)MathSciNetCrossRefMATH Fotakis, D., Kaporis, A.C., Spirakis, P.G.: Atomic congestion games: fast, myopic and concurrent. Theory Comput. Syst. 47(1), 38–59 (2010)MathSciNetCrossRefMATH
27.
Zurück zum Zitat Fotakis, D., Kaporis, A.C., Spirakis, P.G.: Efficient methods for selfish network design. Theor. Comput. Sci. 448, 9–20 (2012)MathSciNetCrossRefMATH Fotakis, D., Kaporis, A.C., Spirakis, P.G.: Efficient methods for selfish network design. Theor. Comput. Sci. 448, 9–20 (2012)MathSciNetCrossRefMATH
28.
Zurück zum Zitat Fotakis, D., Karakostas, G., Kolliopoulos, S.G.: On the existence of optimal taxes for network congestion games with heterogeneous users. In: Kontogiannis, S., Koutsoupias, E., Spirakis, P.G. (eds.) SAGT 2010. LNCS, vol. 6386, pp. 162–173. Springer, Heidelberg (2010) CrossRef Fotakis, D., Karakostas, G., Kolliopoulos, S.G.: On the existence of optimal taxes for network congestion games with heterogeneous users. In: Kontogiannis, S., Koutsoupias, E., Spirakis, P.G. (eds.) SAGT 2010. LNCS, vol. 6386, pp. 162–173. Springer, Heidelberg (2010) CrossRef
29.
Zurück zum Zitat Fotakis, D., Kontogiannis, S.C., Koutsoupias, E., Mavronicolas, M., Spirakis, P.G.: The structure and complexity of Nash equilibria for a selfish routing game. Theor. Comput. Sci. 410(36), 3305–3326 (2009)MathSciNetCrossRefMATH Fotakis, D., Kontogiannis, S.C., Koutsoupias, E., Mavronicolas, M., Spirakis, P.G.: The structure and complexity of Nash equilibria for a selfish routing game. Theor. Comput. Sci. 410(36), 3305–3326 (2009)MathSciNetCrossRefMATH
30.
31.
Zurück zum Zitat Fotakis, D.A., Kontogiannis, S.C., Spirakis, P.G.: Symmetry in network congestion games: pure equilibria and anarchy cost. In: Erlebach, T., Persinao, G. (eds.) WAOA 2005. LNCS, vol. 3879, pp. 161–175. Springer, Heidelberg (2006) CrossRef Fotakis, D.A., Kontogiannis, S.C., Spirakis, P.G.: Symmetry in network congestion games: pure equilibria and anarchy cost. In: Erlebach, T., Persinao, G. (eds.) WAOA 2005. LNCS, vol. 3879, pp. 161–175. Springer, Heidelberg (2006) CrossRef
32.
33.
Zurück zum Zitat Gairing, M., Lücking, T., Mavronicolas, M., Monien, B., Rode, M.: Nash equilibria in discrete routing games with convex latency functions. J. Comput. Syst. Sci. 74(7), 1199–1225 (2008)MathSciNetCrossRefMATH Gairing, M., Lücking, T., Mavronicolas, M., Monien, B., Rode, M.: Nash equilibria in discrete routing games with convex latency functions. J. Comput. Syst. Sci. 74(7), 1199–1225 (2008)MathSciNetCrossRefMATH
34.
Zurück zum Zitat Harks, T., Klimm, M., Möhring, R.H.: Characterizing the existence of potential functions in weighted congestion games. Theory Comput. Syst. 49(1), 46–70 (2011)MathSciNetCrossRefMATH Harks, T., Klimm, M., Möhring, R.H.: Characterizing the existence of potential functions in weighted congestion games. Theory Comput. Syst. 49(1), 46–70 (2011)MathSciNetCrossRefMATH
35.
Zurück zum Zitat Holzman, R., Law-Yone, N.: (Lev-tov). Network structure and strong equilibrium in route selection games. Math. Soc. Sci. 46, 193–205 (2003)CrossRefMATH Holzman, R., Law-Yone, N.: (Lev-tov). Network structure and strong equilibrium in route selection games. Math. Soc. Sci. 46, 193–205 (2003)CrossRefMATH
36.
Zurück zum Zitat Kaporis, A.C., Spirakis, P.G.: The price of optimum in Stackelberg games on arbitrary single commodity networks and latency functions. Theor. Comput. Sci. 410(8–10), 745–755 (2009)MathSciNetCrossRefMATH Kaporis, A.C., Spirakis, P.G.: The price of optimum in Stackelberg games on arbitrary single commodity networks and latency functions. Theor. Comput. Sci. 410(8–10), 745–755 (2009)MathSciNetCrossRefMATH
37.
Zurück zum Zitat Karakostas, G., Kolliopoulos, S.: Edge pricing of multicommodity networks for heterogeneous selfish users. In: Proceedings of the 45th IEEE Symposium on Foundations of Computer Science (FOCS 2004), pp. 268–276 (2004) Karakostas, G., Kolliopoulos, S.: Edge pricing of multicommodity networks for heterogeneous selfish users. In: Proceedings of the 45th IEEE Symposium on Foundations of Computer Science (FOCS 2004), pp. 268–276 (2004)
38.
Zurück zum Zitat Karakostas, G., Kolliopoulos, S.: Stackelberg strategies for selfish routing in general multicommodity networks. Algorithmica 53(1), 132–153 (2009)MathSciNetCrossRefMATH Karakostas, G., Kolliopoulos, S.: Stackelberg strategies for selfish routing in general multicommodity networks. Algorithmica 53(1), 132–153 (2009)MathSciNetCrossRefMATH
39.
Zurück zum Zitat Korilis, Y.A., Lazar, A.A., Orda, A.: Achieving network optima using Stackelberg routing strategies. IEEE/ACM Trans. Networking 5(1), 161–173 (1997)CrossRef Korilis, Y.A., Lazar, A.A., Orda, A.: Achieving network optima using Stackelberg routing strategies. IEEE/ACM Trans. Networking 5(1), 161–173 (1997)CrossRef
40.
Zurück zum Zitat Koutsoupias, E., Mavronicolas, M., Spirakis, P.: Approximate equilibria and ball fusion. Theory Comput. Syst. 36, 683–693 (2003)MathSciNetCrossRefMATH Koutsoupias, E., Mavronicolas, M., Spirakis, P.: Approximate equilibria and ball fusion. Theory Comput. Syst. 36, 683–693 (2003)MathSciNetCrossRefMATH
41.
Zurück zum Zitat Koutsoupias, E., Papadimitriou, C.H.: Worst-case equilibria. Comput. Sci. Rev. 3(2), 65–69 (2009)CrossRefMATH Koutsoupias, E., Papadimitriou, C.H.: Worst-case equilibria. Comput. Sci. Rev. 3(2), 65–69 (2009)CrossRefMATH
42.
Zurück zum Zitat Lipton, R.J., Markakis, E., Mehta, A.: Playing large games using simple strategies. In: Proceedings of the 4th ACM Conference on Electronic Commerce (EC 2003), pp. 36–41 (2003) Lipton, R.J., Markakis, E., Mehta, A.: Playing large games using simple strategies. In: Proceedings of the 4th ACM Conference on Electronic Commerce (EC 2003), pp. 36–41 (2003)
43.
Zurück zum Zitat Lücking, T., Mavronicolas, M., Monien, B., Rode, M.: A new model for selfish routing. Theor. Comput. Sci. 406(3), 187–206 (2008)MathSciNetCrossRefMATH Lücking, T., Mavronicolas, M., Monien, B., Rode, M.: A new model for selfish routing. Theor. Comput. Sci. 406(3), 187–206 (2008)MathSciNetCrossRefMATH
47.
Zurück zum Zitat Panagopoulou, P.N., Spirakis, P.G.: Algorithms for pure Nash equilibria in weighted congestion games. ACM J. Exp. Algorithmics 11, 1–19 (2006)MathSciNetMATH Panagopoulou, P.N., Spirakis, P.G.: Algorithms for pure Nash equilibria in weighted congestion games. ACM J. Exp. Algorithmics 11, 1–19 (2006)MathSciNetMATH
48.
49.
Zurück zum Zitat Roughgarden, T.: The price of anarchy is independent of the network topology. In: Proceedings of the 34th ACM Symposium on Theory of Computing (STOC 2002), pp. 428–437 (2002) Roughgarden, T.: The price of anarchy is independent of the network topology. In: Proceedings of the 34th ACM Symposium on Theory of Computing (STOC 2002), pp. 428–437 (2002)
51.
Zurück zum Zitat Roughgarden, T.: On the severity of Braess’s paradox: designing networks for selfish users is hard. J. Comput. Syst. Sci. 72(5), 922–953 (2006)MathSciNetCrossRefMATH Roughgarden, T.: On the severity of Braess’s paradox: designing networks for selfish users is hard. J. Comput. Syst. Sci. 72(5), 922–953 (2006)MathSciNetCrossRefMATH
52.
Zurück zum Zitat Swamy, C.: The effectiveness of stackelberg strategies and tolls for network congestion games. In: Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA 2007), pp. 1133–1142 (2007) Swamy, C.: The effectiveness of stackelberg strategies and tolls for network congestion games. In: Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA 2007), pp. 1133–1142 (2007)
53.
Metadaten
Titel
A Selective Tour Through Congestion Games
verfasst von
Dimitris Fotakis
Copyright-Jahr
2015
DOI
https://doi.org/10.1007/978-3-319-24024-4_14