Cost sharing and clustering under distributed competition

Abstract

In dieser Arbeit werden zwei grundlegende Modelle für nicht-kooperative Spiele vorgestellt, mit denen sich verteilt geplante Netzwerke analysieren lassen. Das Ziel ist ein verbessertes Verständnis der Konflikte und Dynamiken, die durch wirtschaftliche Interessen und Einflüsse sozialer Netzwerke auf Entscheidungen von Akteuren entstehen. Aspekte wie Existenz, Berechenbarkeit und soziale Güte stabiler Zustände wie reiner und approximativer Nash Gleichgewichte stehen bei der Analyse der Modelle im Vordergrund.Im ersten Teil der Arbeit werden Spiele betrachtet, in denen Spieler eine Menge von Rohstoffeinheiten kaufen und deren Kosten aufteilen müssen. Jeder Spieler hat eine bestimmte Anforderung an die Art und Menge der gekauften Einheiten. Die Spieler können Beiträge für den Kauf von Rohstoffen anbieten. Eine Einheit gilt als gekauft wenn der Gesamtbeitrag aller Spieler ihre Kosten übersteigt. Ein Spieler möchte seine Anforderung mit möglichst geringem eigenen Kostenbeitrag erfüllen. Dieser abstrake Ansatz wird auf mehrere Probleme aus dem Bereich Service Installation, Facility Location und Netzwerkdesign angewendet. Daraus entstehen einfache Modelle für fundamentale Fragestellungen im Internet. Generell gibt es schon für sehr kleine Instanzen der Spiele keine oder nur sehr teuere reine Nash Gleichgewichte. Dagegen gibt es für einige Teilklassen der Spiele approximative Nash Gleichgewichte mit kleinen konstanten Gütegarantien. Diese Zustände können auch effizient berechnet werden. In den Algorithmen werden bestehende Techniken aus der linearen Optimierung sowie neue kombinatorische Ansätze verwendet.Im zweiten Teil der Arbeit wird Clustering von Graphen spieltheoretisch untersucht. Jeder Spieler ist ein Knoten im Graph und entscheidet, welchem von mehreren möglichen Clustern er angehört. Der Wert einer Entscheidung für den Spieler hängt dabei von der Entscheidung der anderen Spieler und der Struktur des Netzwerkes ab. Die betrachteten Spiele sind Polymatrix- und Potenzialspiele, in denen die Bewertungen eines Zustands bekannte Indizes für Clusterings nachbilden. Der Schwerpunkt der Analyse liegt auf der Dauer von better-response Dynamiken und der Berechenbarkeit von guten Nash Gleichgewichten und sozial optimalen Zuständen. Zuerst werden Spiele untersucht, die sich aus zwei Teilspielen zusammensetzen, einem für verbundene und einem für nicht verbundene Spieler. Für eine Klasse von Spielen mit 2 Strategien können das beste Nash Gleichgewicht und sozial optimale Zustände einfach charakterisiert und effizient berechnet werden. Danach werden Spiele auf Basis des populären Index Modularity betrachtet. Das Hauptresultat ist ein Beweis der NP-Härte für das Finden des besten Nash Gleichgewichts und des sozial optimalen Zustands. Dies liefert die ersten grundlegenden theoretischen Einsichten in die Modularity-Optimierung und bestätigt eine zuvor in der Literatur formulierte Vermutung über den Komplexitätsstatus.