Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-14461
For citation please use:
Main Title: Computing Pure Nash and Strong Equilibria in Bottleneck Congestion Games
Author(s): Harks, Tobias
Hoefer, Martin
Klimm, Max
Skopalik, Alexander
Type: Research Paper
URI: https://depositonce.tu-berlin.de/handle/11303/15688
http://dx.doi.org/10.14279/depositonce-14461
License: http://rightsstatements.org/vocab/InC/1.0/
Abstract: Bottleneck congestion games properly model the properties of many real-world network routing applications. They are known to possess strong equilibria - a strengthening of Nash equilibrium to resilience against coalitional deviations. In this paper, we study the computational complexity of pure Nash and strong equilibria in these games. We provide a generic centralized algorithm to compute strong equilibria, which has polynomial running time for many interesting classes of games such as, e.g., matroid or single-commodity bottleneck congestion games. In addition, we examine the more demanding goal to reach equilibria in polynomial time using natural improvement dynamics. Using unilateral improvement dynamics in matroid games pure Nash equilibria can be reached efficiently. In contrast, computing even a single coalitional improvement move in matroid and single-commodity games is strongly NP-hard. In addition, we establish a variety of hardness results and lower bounds regarding the duration of unilateral and coalitional improvement dynamics. They continue to hold even for convergence to approximate equilibria.
Subject(s): congestion games
bottleneck
algorithm
pure Nash equilibrium
strong Nash equilibrium
matroid
Issue Date: 2010
Date Available: 17-Dec-2021
Language Code: en
DDC Class: 510 Mathematik
Series: Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin
Series Number: 2010, 16
ISSN: 2197-8085
TU Affiliation(s): Fak. 2 Mathematik und Naturwissenschaften » Inst. Mathematik
Appears in Collections:Technische Universität Berlin » Publications

Files in This Item:
Report-016-2010.pdf
Format: Adobe PDF | Size: 141.03 kB
DownloadShow Preview
Thumbnail

Item Export Bar

Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.