nach oben

Journal of Combinatorial Optimization

Erschienen in:

20.10.2017

Congestion games with mixed objectives

verfasst von: Matthias Feldotto, Lennart Leder, Alexander Skopalik

Erschienen in: Journal of Combinatorial Optimization | Ausgabe 4/2018

Einloggen

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

search-config

KI-gestützte Suche

Aus

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 (non-)existence of pure Nash equilibria (PNE), the convergence of improvement dynamics, the quality of equilibria and show the complexity of the decision problem. For games that do not possess PNE we give bounds on the approximation ratio of approximate pure Nash equilibria.

Vorheriger Artikel The mixed center location problem

Nächster Artikel Cost-efficient scheduling on machines from the cloud

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

Ackermann H, Röglin H, Vöcking B (2009) Pure nash equilibria in player-specific and weighted congestion games. Theor Comput Sci 410(17):1552–1563MathSciNetCrossRef

Ackermann H, Röglin H, Vöcking B (2008) On the impact of combinatorial structure on congestion games. J ACM 55(6):25:1–25:22MathSciNetCrossRef

Ackermann H, Skopalik A (2008) Complexity of pure nash Equilibria in player-specific network congestion games. Internet Math 5(4):323–342MathSciNetCrossRef

Banner R, Orda A (2007) Bottleneck routing games in communication networks. IEEE J Sel Areas Commun 25(6):1173–1179CrossRef

Caragiannis I, Fanelli A, Gravin N, Skopalik A (2011) Efficient Computation of approximate pure Nash equilibria in congestion games. In IEEE 52nd annual symposium on foundations of computer science (FOCS), pp 532–541

Caragiannis I, Fanelli A, Gravin N, Skopalik A (2015) Approximate pure Nash equilibria in weighted congestion games: existence, efficient computation, and structure. ACM Trans Econ Comput 3(1):1–2MathSciNetCrossRef

Chien S, Sinclair A (2011) Convergence to approximate nash equilibria in congestion games. Games Econ Behav 71(2):315–327MathSciNetCrossRef

Cole R, Dodis Y, Roughgarden T (2012) Bottleneck links, variable demand, and the tragedy of the commons. Networks 60(3):194–203MathSciNetCrossRef

Dunkel J, Schulz AS (2008) On the complexity of pure-strategy Nash equilibria in congestion and local-effect games. Math Oper Res 33(4):851–868MathSciNetCrossRef

Feldotto M, Gairing M, Skopalik A (2014) Bounding the potential function in congestion games and approximate pure Nash equilibria. In Liu T, Qi Q, Ye Y (eds) Web and internet economics - 10th international conference, WINE 2014, Beijing, China, December 14–17, 2014. Proceedings. Lecture Notes in Computer Science, vol 8877, pp 30–43. Springer

Fortune S, Hopcroft J, Wyllie J (1980) The directed subgraph homeomorphism problem. Theor Comput Sci 10(2):111–121MathSciNetCrossRef

Fotakis D, Kontogiannis S, Spirakis P (2005) Selfish unsplittable flows. Theor Comput Sci 348(2):226–239MathSciNetCrossRef

Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. W. H. Freeman, New YorkMATH

Hansknecht C, Klimm M, Skopalik A (2014) Approximate pure Nash equilibria in weighted congestion games. In Jansen K, Rolim JDP, Devanur NR, 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

Harks T, Hoefer M, Schewior K, Skopalik A (2016) Routing games with progressive filling. IEEE/ACM Trans Netw 24(4):2553–2562CrossRef

Harks T, Hoefer M, Klimm M, Skopalik A (2013) Computing pure nash and strong equilibria in bottleneck congestion games. Math Program 141(1):193–215MathSciNetCrossRef

Harks T, Klimm M, Möhring RH (2009) Strong Nash equilibria in games with the lexicographical improvement property. In Leonardi S (ed) Internet and network economics, 5th international workshop, WINE 2009, Rome, Italy, December 14–18, 2009. Proceedings. Lecture notes in computer science, vol 5929, pp 463–470. Springer

Mavronicolas M, Milchtaich I, Monien B, Tiemann K (2007) Congestion games with player-specific constants. In Kucera L, Kucera A (eds) Mathematical foundations of computer science 2007, 32nd international symposium, MFCS 2007, Ceský Krumlov, Czech Republic, August 26–31, 2007, Proceedings. Lecture notes in computer science, vol 4708, pp 633–644. Springer

Milchtaich I (1996) Congestion games with player-specific payoff functions. Games Econ Behav 13(1):111–124MathSciNetCrossRef

Monderer D, Shapley LS (1996) Potential games. Games Econ Behav 14(1):124–143MathSciNetCrossRef

Rosenthal RW (1973) A class of games possessing pure-strategy nash equilibria. Int J Game Theory 2(1):65–67MathSciNetCrossRef

Skopalik A, Vöcking B (2008) Inapproximability of pure Nash equilibria. In Proceedings of the fortieth annual ACM symposium on theory of computing. pp 355–364. STOC ’08, ACM, New York, NY, USA

Titel: Congestion games with mixed objectives
verfasst von: Matthias Feldotto
Lennart Leder
Alexander Skopalik
Publikationsdatum: 20.10.2017
Verlag: Springer US
Erschienen in: Journal of Combinatorial Optimization / Ausgabe 4/2018
Print ISSN: 1382-6905
Elektronische ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-017-0189-y

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 4/2018

Scheduling with interjob communication on parallel processors

The mixed evacuation problem

The capture time of a planar graph

Safe sets in graphs: Graph classes and structural parameters

The w-centroids and least w-central subtrees in weighted trees

The mixed center location problem