Diese Dissertation untersucht approximative reine Nash-Gleichgewichte in verschiedenen spieltheoretischen Modellen. In einem solchen Zustand kann sich kein Spieler durch Veränderung seiner Strategie um einen gegebenen Faktor verbessern. Im ersten Teil der Arbeit beschäftigen wir uns mit zwei Varianten von Congestion Games. In diesen Modellen ist die Existenz von reinen Nash-Gleichgewichten durch Potentialfunktionen garantiert, jedoch kann deren Berechnung schwierig sein. Wir analysieren Approximationsalgorithmen zur Berechnung von Zuständen mit kleinen Approximationsfaktoren. Für die Analyse benutzen wir Teilspiele, wir beweisen Schranken für die Potentialfunktion eines beliebigen Zustandes und zeigen eine Relation zwischen Shapley und proportionalen Kostenaufteilungen. Zusätzlich wenden wir Sampling-Methoden zur Approximation von Shapley-Werten in verschiedenen Szenarien an. Im zweiten Teil konzentrieren wir uns auf die Existenz von approximativen reinen Nash-Gleichgewichten in Spielen, in denen im Allgemeinen keine reinen Gleichgewichte existieren. In einem Coevolving Opinion Formation Game können wir niedrige Approximationsgarantien für zwei natürliche Zustände zeigen, die unabhängig von der Definition der Nachbarschaft sind. Hierzu wenden wir ein Konzept von virtuellen Kosten an. Für den Spezialfall nur eines Nachbarn zeigen wir noch stärkere Approximationsfaktoren für einen Zustand, der durch eine natürliche Strategie entsteht. Des Weiteren untersuchen wir ein zweiseitiges Facility Location Game zwischen Facilities und Clients, die als Zielfunktion eine Kombination von Distanz und Auslastung haben. Hier zeigen wir scharfe Schranken für das Szenario mit drei Facilities und unendlich vielen Clients. Für das generelle Szenario mit einer beliebigen Anzahl an Facilities zeigen wir Approximationsfaktoren für zwei Zustände.
Bibliographic Metadata
- TitleApproximate pure nash equilibria in congestion, opinion formation and facility location games / submitted by Matthias Feldotto ; [Advisor: Assistant Professor Dr. Alexander Skopalik, Reviewers: Assistant Professor Dr. Alexander Skopalik, Senior Lecturer Dr. Martin Gairing, Members of the Doctoral Panel: Prof. Dr. Friedhelm Meyer auf der Heide, Assistant Professor Dr. Alexander Skopalik, Senior Lecturer Dr. Martin Gairing, Prof. Dr. Claus-Jochen Haake, Dr. Rainer Feldmann]
- Author
- Participants
- Published
- Description1 Online-Ressource (x, 171 Seiten) : Diagramme
- Institutional NoteUniversität Paderborn, Dissertation, 2018
- AnnotationTag der Verteidigung: 21.12.2018
- Defended on2018-12-21
- LanguageEnglish
- Document TypesDissertation (PhD)
- URN
- DOI
- Social MediaShare
- Reference
- IIIF
This thesis investigates approximate pure Nash equilibria in different game-theoretic models. In such an outcome, no player can improve her objective by more than a given factor through a deviation to another strategy. In the first part, we investigate two variants of Congestion Games in which the existence of pure Nash equilibria is guaranteed through a potential function argument. However, the computation of such equilibria might be hard. We construct and analyze approximation algorithms that enable the computation of states with low approximation factors in polynomial time. To show their guarantees we use sub games among players, bound the potential function values of arbitrary states and exploit a connection between Shapley and proportional cost shares. Furthermore, we apply and analyze sampling techniques for the computation of approximate Shapley values in different settings. In the second part, we concentrate on the existence of approximate pure Nash equilibria in games in which no pure Nash equilibria exist in general. In the model of Coevolving Opinion Formation Games, we bound the approximation guarantees for natural states nearly independent of the specific definition of the players' neighborhoods by applying a concept of virtual costs. For the special case of only one influential neighbor, we even show lower approximation factors for a natural strategy. Then, we investigate a two-sided Facility Location Game among facilities and clients on a line with an objective function consisting of distance and load. We show tight bounds on the approximation factor for settings with three facilities and infinitely many clients. For the general scenario with an arbitrary number of facilities, we bound the approximation factor for two promising candidates, namely facilities that are uniformly distributed and which are paired.
- The PDF-Document has been downloaded 195 times.