Selfishness in strategic resource allocation problems

Ravindran Vijayalakshmi, Vipin; Woeginger, Gerhard; Skopalik, Alexander; Peis, Britta

doi:40880

Selfishness in strategic resource allocation problems

Ravindran Vijayalakshmi, Vipin^RWTH*

2021 & 2022

Verantwortlichkeitsangabevorgelegt von Vipin Ravindran Vijayalakshmi, M.Sc.

ImpressumAachen : RWTH Aachen University 2021

Umfang1 Online-Ressource : Illustrationen, Diagramme

Dissertation, RWTH Aachen University, 2021

Veröffentlicht auf dem Publikationsserver der RWTH Aachen University 2022

Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter
Peis, Britta (Thesis advisor)^RWTH* ; Woeginger, Gerhard (Thesis advisor)^RWTH* ; Skopalik, Alexander (Thesis advisor)

Tag der mündlichen Prüfung/Habilitation
2021-09-06

Online
DOI: 10.18154/RWTH-2021-11656
URL: https://publications.rwth-aachen.de/record/836875/files/836875.pdf

Einrichtungen

Inhaltliche Beschreibung (Schlagwörter)
approximate equilibrium (frei) ; congestion games (frei) ; game theory (frei) ; overlay networks (frei) ; scheduling games (frei)

Thematische Einordnung (Klassifikation)
DDC: 004

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.

The advent of modern technology in the communication and the transportation industry encouraged the proliferation of its consumer base. Due to the rising demand on many of these modern applications and scenarios, centralization was no longer deemed a viable approach for managing their operations. These days, many modern infrastructures are designed to allow for multiple strategic users who make decisions that suit their individual utility. Consequently, non-cooperative game theory has emerged as an essential tool in analyzing and predicting the outcome of decentralized systems. We study various algorithmic aspects arising due to strategic behavior among multiple non-cooperative users in several classes of resource allocation problems using a game theoretic approach. The classes of strategic games we study, succinctly represent many of the socio-economic scenarios arising due to decentralization. At first, we consider congestion games which are often used to model various scenarios of resource allocation by non-cooperative users. In these games, the resources could possibly correspond to edges in a road or communication network, machines in distributed systems, etc., and have cost functions with a diseconomy of scale. The players in a congestion game then iteratively pick feasible subsets of resources that maximize their individual utility. The players continue to strategically deviate, if necessary, until the game converges to a widely studied solution concept known as the pure Nash equilibrium. The hardness of computing a pure Nash equilibrium in congestion games has been of significant interest in the scientific community over the past two decades. As computing an exact pure Nash equilibrium is known to be hard, we study a weaker notion of pure Nash equilibrium called an approximate pure Nash equilibrium and to that extend, analyze an efficient algorithm that computes approximate pure Nash equilibria in congestion games with an approximation guarantee that is by far the best known in the literature. The impact of non-coordination among the users on the self emerging solutions of a congestion game are provably bad. One of the many approaches used to alleviate the effects of non-cooperativeness is the introduction of taxes. Economic incentives have provably shown to influence the users to induce solutions that are significantly closer to the optimal solution. We present a mechanism to compute load dependent taxes for congestion games that are robust against the changes in the number of users and resources in the game.In spite of being the predominant class of games to model resource allocation problems involving different users, congestion games lack an element of time dependence, especially in certain application scenarios such as the road transportation network. It is quite unnatural to assume that all users of a road section experience the same congestion. A cost sharing mechanism must also take into account the order in which a resource processes the users assigned to it. We extend congestion games with resource dependent priority list to model the impact of fixed order scheduling on the strategic behavior of users. We then study the question of existence and inefficiency of pure Nash equilibria in the extended model. It is quite natural to then consider a scheduling game on parallel machines, in which jobs try to minimize their completion time by choosing a machine to be processed on. Each machine uses an individual priority list to decide on the order according to which the jobs on the machine are processed. Here, we study the existence of a pure Nash equilibrium and characterize classes of instances in which a pure Nash equilibrium is guaranteed to exist. For each of these classes, we settle algorithmic questions such as tractability and the inefficiency of pure Nash equilibria. Finally, we study the impact of non-cooperative users in a large scale distributed communication network such as the peer-to-peer overlay network, where the existence of non-cooperative and malicious users is considered as a rule rather than an exception. Due to its distributed architecture, users or peers are allowed to join and leave without admission control. A necessary condition to maintain the stability of a distributed overlay network that allows for efficient storage and retrieval of information is to have certain degree of commitment and coordination among the peers in the network. Moreover, the lack of a centralized mechanism entails that the peers in the network coordinate among themselves. However, peers joining and leaving the network in a non-coordinated manner leads to instability and loss of information. We model this scenario using an adversary and present an algorithm that is able to ensure stability in the network in the presence of large fraction of non-cooperative peers.

OpenAccess:
PDF
(additional files)