TY  - THES
AB  - 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.
AU  - Feldotto, Matthias
CY  - Paderborn
DA  - 2019
DO  - 10.17619/UNIPB/1-588
DP  - Universität Paderborn
LA  - eng
N1  - Tag der Verteidigung: 21.12.2018
N1  - Universität Paderborn, Dissertation, 2018
PB  - Veröffentlichungen der Universität
PY  - 2019
SP  - 1 Online-Ressource (x, 171 Seiten)
T2  - Institut für Informatik
TI  - Approximate pure nash equilibria in congestion, opinion formation and facility location games
UR  - https://nbn-resolving.org/urn:nbn:de:hbz:466:2-33455
Y2  - 2025-01-21T04:07:25
ER  -