Loading…
Designing mechanisms for good equilibria
Falkenhausen, Philipp Friedrich Freiherr von
Diese Arbeit untersucht, wie zentrale Stellen (z.B. Gesetzgeber, Marktplatzbetreiber, Netzbetreiber) Einfluss auf die Effizienz von Gleichgewichten in Spielen nehmen können und wie Spieler in Abwesenheit von zentraler Steuerung ein Gleichgewicht finden können.
Zunächst betrachten wir Auslastungsspiele, in denen Spieler Teilmengen einer Menge von Ressourcen als Strategie wählen. Wir nehmen an, dass die möglichen Strategien eines Spielers die Basis eines Matroids bilden, jeder Spieler eine individuelle Last auf alle genutzten Ressourcen ausübt, und dass es für jeden Spieler bei der Nutzung einer Ressource eine spezifische Latenz gibt. Unter der Annahme, dass die von der Last abhängigen Kosten der Ressourcen monetär und damit beliebig aufteilbar sind, untersuchen wir, wie verschiedene Kostenverteilungsprotokolle sich auf die Gleichgewichte des Spiels und deren Effizienz auswirken. Wir betrachten zwei Klassen von solchen Protokollen: einfache Protokolle garantieren die Existenz eines puren Nash Gleichgewichts und separable Protokolle haben zusätzlich die Eigenschaft, dass die Verteilung der Kosten einer Ressource ausschließlich von ihren Nutzern abhängt. Maß für die Effizienz eines Protokolls sind der Preis der Anarchie und der Preis der Stabilität, die für ein gegebenes Spiel die Kosten des teursten bzw. billigsten Gleichgewichts als Verhältnis zu den Kosten ein zentral bestimmten Optimums angeben.
Wir führen optimale einfache und separable Protokolle ein, für die wir zeigen, dass der Preis der Stabilität maximal logarithmisch in der Anzahl der Spieler wächst und der Preis der Anarchie maximal linear.
Zusätzlich untersuchen wir die Komplexität der Berechnung von optimalen Kostenanteilen. Mit einer Reduktion auf das HITTING SET Problem zeigen wir, dass das Problem, für eine gegebene Instanz eine optimale Kostenverteilung zu berechnen, NP-vollständig und nicht auf einen Faktor c log(n) für c<1 approximierbar ist, wobei n die Anzahl der Spieler ist. Für eine eingeschränkte Klasse von Instanzen geben einen Approximationsalgorithmus an, der Kostenverteilungen berechnet, die einen Preis der Anarchie und Preis der Stabilität innerhalb der oben genannten Schranken garantieren.
Im nächsten Kapitel der Arbeit betrachten wir den Effekt, den die Änderung von exogenen Parametern auf die Gleichgewichte eines Spiels haben kann. Wir führen einen Ansatz ein, mit dem sich solche Änderungen quantitativ untersuchen lassen, und nutzen diesen Ansatz, um Preiserhöhungen in Cournot Wettbewerb auf mehreren Märkten zu beobachten. Es ist ein bekanntes Paradox, dass in diesem Modell der Profit eines Monopolisten bei Preiserhöhungen sinken kann. Wir zeigen, dass dabei bis zu 25% des Profits verloren gehen kann. Zusätzlich zeigen wir, dass der Gesamtprofit aller Firmen um bis zu 25% sinken kann und auch der volkswirtschaftliche Überschuss um bis zu 16,7% sinken kann.
Im letzen Kapitel der Arbeit untersuchen wir Lernprozesse in Auslastungsspielen, in denen die Spieler eine festgelegte Flussmenge durch ein Netzwerk schicken und diese dabei über mehrere Pfade aufteilen können. Wir nehmen an, dass die Spieler ihre Strategien mit sogenannten {no-regret} Algorithmen wählen. Wir zeigen, dass in Spielen mit affin-linearen Latenzfunktionen die Strategien der Spieler zu einem Nash Gleichgewicht konvergieren und dass die grob-korrelierten Gleichgewichte (Konvergenzlimit solcher Lernprozesse) quasi mit den puren Nash Gleichgewichten übereinstimmen. Dies steht in Kontrast zu Spielen mit allgmeinen, nicht affin-linearen Latenzfunktionen, für die wir zeigen, dass es grob-korrelierte Gleichgewichte gibt, die signifikant teurer sind als die puren Gleichgewichte, insbesondere auch teurer als für pure Gleichgewichte bekannte Schranken. Für solche allgemeinen Spiele zeigen wir ein Konvergenzresultat, dass diesen unteren Schranken entspricht.
In this dissertation, we analyze how central authorities can have impact on the efficiency of equilibria and how players can reach an equilibrium state in the absence of a central authority.
Three specific settings are considered:
First, cost sharing in games where players jointly use resources and a central authority can enforce a cost sharing protocol to distribute the costs of the resources among the players. Here, we propose protocols that are optimal in terms of the achieved worst-case price of anarchy and worst-case price of stability. We also consider designing protocols that are computable in polynomial time, showing that computing optimal cost shares for a given instance is NP-hard and providing a polynomial time approximation algorithm with worst-case performance guarantees similar to those of our optimal protocols for a restricted setting.
Second, we turn to the effect of price shocks on equilibria in multimarket Cournot competition. We show that positive price shocks (e.g. subsidies) can decrease a firm’s profit by up to 25%, and even welfare can decrease by 25%. Social surplus on the other hand can only decrease by up to 16.7%.
Third, we study the convergence of no-regret learners in atomic splittable routing games. We find that for games with affine-linear latency functions, repeated play converges to quickly to a Nash equilibrium. For general latency functions, such convergence cannot be shown and we give a lower bound proving the the price of anarchy for coarse correlated equilibria in games with cubic cost is higher than the price of anarchy for pure equilibria, that is, bounds for pure equilibria do not carry over to coarse correlated equilibra.
