Selfishness in strategic resource allocation problems

Ravindran Vijayalakshmi, Vipin; Peis, Britta (Thesis advisor); Woeginger, Gerhard (Thesis advisor); Skopalik, Alexander (Thesis advisor)

Aachen : RWTH Aachen University (2021, 2022)
Doktorarbeit

Dissertation, RWTH Aachen University, 2021

Kurzfassung

Die kontinuierlichen Entwicklungen innerhalb der Kommunikation- sowie Transportindustrie führten zur einer stetigen Zunahme der Nutzer in den letzten Jahrzehnten. Aufgrund der damit einhergehenden Steigerung des Bedarfs an modernen Applikationen und Szenarios sind zentralisierte Lösungen heute kein zufriedenstellendes Konzept mehr diese Anwendungen umzusetzen. Moderne Infrastruktur-Systeme sind daher so entwickelt, dass viele strategische Nutzer eigenständig Entscheidungen tätigen können. Diese Eigenständigkeit hat jedoch die Folge, dass die jeweiligen Entscheidungen nur ihren persönlichen Nutzen maximieren. Dieser Tatsache geschuldet entwickelte sich die Nicht-kooperative Spieltheorie, in der die Ausgänge dieser dezentralen Systeme analysiert und vorhergesagt werden. In der vorliegenden Arbeit studieren wir verschiedene algorithmische Fragestellungen, die sich aus der Existenz von nicht-kooperativen Spielern in Auslastungsspielen ergeben. Hierzu nutzen wir insbesondere Techniken aus der Spieltheorie sowie der Komplexitätstheorie. Die untersuchte Klasse der strategischen Spiele beschreibt zuverlässig diverse sozioökonomische Szenarien, die im Zusammenhang mit Dezentralisierung entstehen. Zuerst betrachten wir Congestion-Games, die häufig in Modellen genutzt werden in denen eine gewisse Anzahl an Ressourcen auf nicht-kooperative Spieler aufgeteilt werden. Hier präsentieren wir einen Algorithmus, der approximative Nash-Gleichgewichte in Congestion-Games berechnet und dessen Approximationsgüte bekannte Resultate in der Literatur stark verbessert. Darüber hinaus betrachten wir eine Erweiterung des Spieles, in der die Spieler durch finanzielle Anreize zu besseren Entscheidungen für die Allgemeinheit bewogen werden sollen. Hier präsentieren wir Kostenfunktionen für die Ressourcen, die von der jeweiligen Belegung der Ressourcen abhängen. Diese Kosten erweisen sich als robust gegenüber Veränderungen in der Anzahl der Spieler als auch der Ressourcen des Spiels. Darüber hinaus untersuchen wir eine weitere Abwandlung von Congestion-Games, indem wir eine zeitliche Komponente hinzufügen. Die einzelen Resourcen werden nicht mehr simultan von allen Spielern genutzt, sondern nacheinander entsprechend einer Prioritätsliste der Ressource. In diesem Modell studieren wir die Frage der Existenz und der Effizienz von Nash-Gleichgewichten. Zudem untersuchen wir algorithmische Fragestellungen in den sogenannten Scheduling-Games. Zuletzt untersuchen wir den Einfluss von nicht-kooperativen Benutzern in distributiven Kommunikationsnetzwerken, wie zum Beispiel in Peer-to-Peer Netzwerken, in denen die Existenz von nicht vertrauenswürdigen Nutzern angenommen werden muss. Unter Berücksichtigung dieser Unsicherheit für das System präsentieren wir einen Algortihmus, der Stabilität im Netzwerk garantieren kann, selbst wenn eine große Anzahl von nicht-kooperativen Spielern existiert.