Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-3388
Main Title: Competition for Resources: The Equilibrium Existence Problem in Congestion Games
Translated Title: Wettbewerb um Ressourcen: Die Existenz von Gleichgewichten in Auslastungsspielen
Author(s): Klimm, Max
Advisor(s): Harks, Tobias
Granting Institution: Technische Universität Berlin, Fakultät II - Mathematik und Naturwissenschaften
Type: Doctoral Thesis
Language: English
Language Code: en
Abstract: Gewichtete Auslastungsspiele sind ein elegantes Modell der Nutzung einer endlichen Menge von Ressourcen durch eine endliche Menge selbstständig und eigennützig handelnder Spieler. In einem solchen Spiel verfügt jeder Spieler über einen strikt positiven Bedarf und eine Menge zulässiger Allokationen, wobei jede Allokation eine Teilmenge der Ressourcen ist. Die Spieler wählen strategisch eine zulässige Allokation mit dem Ziel die Summer der Kosten der in der Allokation enthaltenen Ressourcen zu minimieren. Die Kosten jeder Ressource hängen dabei vom aggregierten Bedarf der sie benutzenden Spieler ab und sind durch eine auslastungs- und ressourcenabhängige Kostenfunktion gegeben. Ein Allokationsvektor ist ein reines Nash-Gleichgewicht falls für jeden Spieler die gewählte Allokation optimal ist, also keine kostengünstigere Allokation existiert. Es ist bekannt, dass Spiele, in denen entweder alle Kostenfunktionen affin-linear sind oder alle Kostenfunktionen exponentiell sind, stets ein reines Nash-Gleichgewicht besitzen. Diese Resultate lassen jedoch die nahe liegende Frage offen, ob es noch weitere Klassen von Kostenfunktionen gibt, die die Existenz eines reinen Nash-Gleichgewichts in allen gewichteten Auslastungsspielen garantieren. In dieser Arbeit geben wir eine vollständige Anwtort auf diese Frage indem wir zeigen, dass es keine weiteren Mengen solcher Funktionen gibt. Unser Resultat impliziert insbesondere, dass es für jede Kostenfunktion c, die weder affin-linear noch exponentiell ist, ein gewichtetes Auslastungsspiel gibt, in dem alle Kosten gleich c sind und das kein reines Nash-Gleichegewicht besitzt. Anschließend charakterisieren wir die Existenz reiner Nash-Gleichgewichte ebenfalls für zwei wichtige Erweiterungen gewichteter Auslastungsspiele. In der ersten Erweiterung erlauben wir, dass die Bedarfe der Spielers von den Ressourcen abhängen. Wir zeigen, dass in diesem Modell ausschließlich affin-lineare Kostenfunktionen die Existenz eines Gleichgewichts garantieren. Anschließend untersuchen wir Spiele, in denen die Spieler ihren Bedarf strategisch der Auslastung der Ressourcen anpassen können. In einem solchen Spiel wählt jeder Spieler sowohl einen nicht-negativen Bedarf als auch eine zulässige Allokation mit dem Ziel die Differenz aus dem von der Befriedigung des Bedarfs gewonnenen Nutzen und den Kosten der Ressourcen zu maximieren. Wir zeigen, dass die einzigen Mengen von Kostenfunktionen, die in solchen Spielen die Existenz eines Gleichgewichts garantieren entweder nur homogen exponentiell Funktionen oder nur affin-lineare Funktionen enthalten. Darüber hinaus betrachten wir Spiele, in denen die Spieler anstelle der Summe der Kosten der von ihnen gewählten Resourcen das Maximum der Kosten minimieren wollen. Es zeigt sich, dass für diese Spiele die Existenz eines reinen Nash-Gleichgewichts unter wesentlich geringeren Anforderungen an die Kostenfunktionen bewiesen werden kann. Selbst unter der sehr allgemeinen Annahme, dass die Kosten jeder Ressource von der Menge der sie benutzenden Spieler abhängt, können wir die Existenz eines starken Gleichewichts zeigen, falls alle Kostenfunktionen monoton nicht-fallend sind. Starke Gleichgewichte sind eine Verfeinerung des Konzepts reiner Nash-Gleichgewichte, die sogar stabil gegenüber Abweichungen einer Menge von Spielern sind. Unser Resultat impliziert also insbesondere die Existenz reiner Nash-Gleichgewichte in diesen Spielen. Abschließend wird die Berechenbarkeit starker Gleichgewichte in diesen Spielen untersucht.
Weighted congestion games are an elegant model to study the effects of selfish resource usage by a finite number of players. In such a game, each player is associated with a strictly positive demand and a set of feasible allocations where each allocation is a subset of the resources. Each player chooses an allocation so as to minimize the sum of the costs of all resources used. The costs of a resource depend on the aggregated demand of all players using that resources and is given as a resource-specific function of the aggregated demand. An allocation vector constitutes a pure Nash equilibrium if no play can decrease her costs by a unilateral deviation. It is known that games with affine or exponential cost functions always possess a pure Nash equilibrium. However, it has been an open question whether there are further sets of cost functions that guarantee the existence of a pure Nash equilibrium in all weighted congestion games. In this thesis, we give a complete answer to this question as we show that there are no further sets of such functions. Our result implies in particular that for every cost function c that is neither affine nor exponential there is a weighted congestion game in which the cost of each resource is determined by c and that does not possess a pure Nash equilibrium. We also explore the existence of pure Nash equilibria for two important extensions of weighted congestion games. In the first extension, we allow that the demand of a player may depend on the resource used. For this class of games we show that only the set of affine functions always gives rise to a pure Nash equilibrium for all congestion games with resource-dependent demands. Moreover, we examine a class of games, termed congestion games with elastic demands, in which each player may adapt her demand strategically on the congestion on the resources. More formally, in such a game each player chooses both a non-negative demand and an allocation so as to maximize the utility derived from her demand minus the congestion costs of the chosen resources. We show that the unique maximal sets of cost functions that guarantee the existence of a pure Nash equilibria in these games are the set of homogeneously exponential functions and the set of affine functions. Next, we consider games, in which the players strive to minimize the maximum of the costs of the resources costs (instead of the sum). It turns out that for such games the existence of a pure Nash equilibrium can be shown under much weaker conditions as in the previous games. Even when we allow that the cost of each resource is a non-decreasing function depending on the set of players using it, the existence of a strong equilibrium can be proven. Strong equilibria are a strengthening of the pure Nash equilibrium concept that is even resilient to coordinated deviations of a coalition of players. As each strong equilibrium is a pure Nash equilibrium, our positive result implies in particular the existence of a pure Nash equilibrium in such games. Finally, we explore the complexity of computing strong equilibria in such games.
URI: urn:nbn:de:kobv:83-opus-37198
http://depositonce.tu-berlin.de/handle/11303/3685
http://dx.doi.org/10.14279/depositonce-3388
Exam Date: 17-Sep-2012
Issue Date: 26-Oct-2012
Date Available: 26-Oct-2012
DDC Class: 510 Mathematik
Subject(s): Algorithmus
Auslastungsspiel
Kostenfunktion
Nash-Gleichgewicht
Spieltheorie
Algorithm
Congestion game
Cost function
Game theory
Nash equilibrium
Usage rights: Terms of German Copyright Law
Appears in Collections:Technische Universität Berlin » Fakultäten & Zentralinstitute » Fakultät 2 Mathematik und Naturwissenschaften » Institut für Mathematik » Publications

Files in This Item:
File Description SizeFormat 
Dokument_4.pdf1.27 MBAdobe PDFThumbnail
View/Open


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