Efficient Computation of Equilibria in Bottleneck Games via Game Transformation

  • We study the efficient computation of Nash and strong equilibria in weighted bottleneck games. In such a game different players interact on a set of resources in the way that every player chooses a subset of the resources as her strategy. The cost of a single resource depends on the total weight of players choosing it and the personal cost every player tries to minimize is the cost of the most expensive resource in her strategy, the bottleneck value. To derive efficient algorithms for finding Nash equilibria in these games, we generalize a tranformation of a bottleneck game into a special congestion game introduced by Caragiannis et al. [1]. While investigating the transformation we introduce so-called lexicographic games, in which the aim of a player is not only to minimize her bottleneck value but to lexicographically minimize the ordered vector of costs of all resources in her strategy. For the special case of network bottleneck games, i.e., the set of resources are the edges of a graph and the strategies are paths, we analyse different Greedy type methods and their limitations for extension-parallel and series-parallel graphs.

Volltext Dateien herunterladen

Metadaten exportieren

  • Export nach Bibtex
  • Export nach RIS

Weitere Dienste

Teilen auf Twitter Suche bei Google Scholar
Metadaten
Verfasserangaben:Thomas L. Werth, Heike Sperber, Sven O. Krumke
URN (Permalink):urn:nbn:de:hbz:386-kluedo-16829
Schriftenreihe (Bandnummer):Report in Wirtschaftsmathematik (WIMA Report) (134)
Dokumentart:Bericht
Sprache der Veröffentlichung:Deutsch
Jahr der Fertigstellung:2011
Jahr der Veröffentlichung:2011
Veröffentlichende Institution:Technische Universität Kaiserslautern
Datum der Publikation (Server):10.02.2011
Fachbereiche / Organisatorische Einheiten:Fachbereich Mathematik
DDC-Sachgruppen:5 Naturwissenschaften und Mathematik / 51 Mathematik / 510 Mathematik
Lizenz (Deutsch):Standard gemäß KLUEDO-Leitlinien vor dem 27.05.2011

$Rev: 13581 $