Details

Autor(en) / Beteiligte

• Feldotto, Matthias
• Skopalik, Alexander[Akademischer Betreuer]
• Gairing, Martin[Akademischer Betreuer]
• Meyer auf der Heide, Friedhelm[Akademischer Betreuer]
• Haake, Claus-Jochen[Akademischer Betreuer]
• Feldmann, Rainer[Akademischer Betreuer]

Titel

Approximate pure nash equilibria in congestion, opinion formation and facility location games

Ort / Verlag

Paderborn

Erscheinungsjahr

2019

Link zum Volltext

• Hochschulschriften Visual Library - Scan2Web Hochschulschriften UB Paderborn (s2w-hsspadubpb)
• Hochschulschriften Visual Library - Scan2Web Hochschulschriften UB Paderborn (s2w-hsspadubpb)

Link zu anderen Inhalten

• Volltext
• Volltext

Verknüpfte Titel

Beschreibungen/Notizen

• Tag der Verteidigung: 21.12.2018
• Open Access
• ger: 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.
• eng: 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.