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.

Download full text files

Export metadata

Additional Services

Search Google Scholar
Metadaten
Author:Thomas L. Werth, Heike Sperber, Sven O. Krumke
URN:urn:nbn:de:hbz:386-kluedo-16829
Series (Serial Number):Report in Wirtschaftsmathematik (WIMA Report) (134)
Document Type:Report
Language of publication:German
Year of Completion:2011
Year of first Publication:2011
Publishing Institution:Technische Universität Kaiserslautern
Date of the Publication (Server):2011/02/10
Faculties / Organisational entities:Kaiserslautern - Fachbereich Mathematik
DDC-Cassification:5 Naturwissenschaften und Mathematik / 510 Mathematik
Licence (German):Standard gemäß KLUEDO-Leitlinien vor dem 27.05.2011