Dokument: Beyond Intractability: A Computational Complexity Analysis of Various Types of Influence and Stability in Cooperative Games

Titel:	Beyond Intractability: A Computational Complexity Analysis of Various Types of Influence and Stability in Cooperative Games
URL für Lesezeichen:	https://docserv.uni-duesseldorf.de/servlets/DocumentServlet?id=39369
URN (NBN):	urn:nbn:de:hbz:061-20160914-091329-3
Kollektion:	Dissertationen
Sprache:	Englisch
Dokumententyp:	Wissenschaftliche Abschlussarbeiten » Dissertation
Medientyp:	Text
Autor:	Rey, Anja [Autor]
Dateien:	[Dateien anzeigen] Adobe PDF [Details] 887,7 KB in einer Datei [ZIP-Datei erzeugen] Dateien vom 31.08.2016 / geändert 31.08.2016
Beitragende:	Prof. Dr. Rothe, Jörg [Betreuer/Doktorvater] Prof. Dr. Woeginger, Gerhard [Gutachter] Prof. Dr. Ågotnes, Thomas [Gutachter]
Stichwörter:	Komplexitätstheorie, Spieltheorie
Dewey Dezimal-Klassifikation:	000 Informatik, Informationswissenschaft, allgemeine Werke
Beschreibungen:	Diese Arbeit beschäftigt sich mit der Berechnungskomplexität unterschiedlicher Problemstellungen aus der kooperativen Spieltheorie. Zum einen betrachten wir Existenz und Verifizierung von Stabilitätskonzepten in kooperativen Spielen mit übertragbarem Nutzen und in hedonischen Spielen; zum anderen wenden wir uns der Einflussnahme auf den Ausgang eines Spiels durch Manipulation, Kontrolle und Bestechung zu. Wir widmen uns manipulativem Verhalten im Sinne von strategischem Zusammenschluss von Spielern oder unter Angabe falscher Identitäten sowie struktureller Kontrolle durch Hinzufügen oder Entfernen von Spielern in gewichteten Wahlspielen. Betrachtete Lösungskonzepte hier sind der probabilistische Penrose--Banzhaf-Index und der Shapley--Shubik-Index, die die Manipulatoren beabsichtigen, zu ihrem Vorteil zu verbessern. Wir zeigen unter anderem für das Problem, ob ein Zusammenschluss einer gegebenen Koalition in einem gegebenen Spiel vorteilhaft ist, Vollständigkeit für probabilistische Polynomialzeit. Außerdem verallgemeinern wir ein formales Modell für Manipulation auf beliebige Klassen von kooperativen Spielen und untersuchen allgemeine Eigenschaften sowie beispielhaft einzelne Klassen wie Einstimmigkeitsspiele. Darüber hinaus betrachten wir Bestechung in Pfad-Unterbrechungs-Spielen, wobei ein Gegenspieler versucht, durch ein Netzwerk von einem Start- zu einem Zielknoten zu gelangen und dabei ausgewählte Agenten für die Freigabe ihrer Knoten zu bezahlen, sodass es sich für übrige Koalitionen nicht mehr lohnt oder unmöglich ist, alle Wege zu blockieren. Für mehrere Gegenspieler und Kosten zur Knotenblockierung zeigen wir, dass das Bestechungsproblem vollständig für die zweite Stufe der Polynomialzeithierarchie ist. Wir erweitern diese Spiele auf ein probabilistisches Modell, in dem das genaue Ziel des Gegenspielers unbekannt ist, und untersuchen es im Hinblick auf bekannte Stabilitätskonzepte wie den Kern. Hier kann beobachtet werden, dass sich der allgemeinere Fall bezüglich Komplexität nicht anders verhält als der speziellere. Fragen der Stabilität analysieren wir ebenfalls in hedonischen Spielen. Dabei gehen wir zunächst auf wundervolle Stabilität in feind-orientierten hedonischen Spielen ein. Wir heben die untere Schranke des Problems, ob es im Graphen eines zugrunde liegenden gegebenen Spiels eine wundervoll stabile Aufteilung gibt, auf DP an, also auf die zweite Stufe der booleschen Hierarchie. Auf dem Weg zur exakten Komplexität zeigen wir, dass coDP-Härte ausreichen würde, um Vollständigkeit für parallelen Zugriff auf NP zu beweisen. Des Weiteren führen wir ein neues Modell hedonischer Spiele mit ordinalen Präferenzen und Schwellenwerten ein, in dem Spieler ihre Mitspieler in Freunde, Feinde und neutrale Spieler unterteilen und gleichzeitig eine schwache Ordnung über die ersten beiden Mengen angeben. Erweitert wird diese Relation auf eine Menge möglicher Präferenzen, sodass es sinnvoll ist, Begriffe der möglichen und notwendigen Stabilität zu definieren. Hierfür prüfen wir die Komplexität unterschiedlicher Konzepte wie Nash-Stabilität und ermitteln axiomatische Spieleigenschaften. Zuletzt stellen wir eine weitere Variante hedonischer Spiele mit altruistischen Einflüssen vor. Bisher bekannte Darstellungen hedonischer Spiele gehen von eigennützigen Agenten aus, deren Präferenzen nur von ihrer Meinung abhängen. Basierend auf freund-orientierten Erweiterungen, lassen wir nun Einflüsse von Freunden auf die Präferenzrelation eines Spielers zu, indem wir in drei Graden der Selbstlosigkeit die durchschnittliche Meinung der Freunde in einer Koalition miteinbeziehen. Auch hier behandeln wir neben sinnvoll hierfür modellierten Eigenschaften die Komplexität von Stabilitätskonzepten wie strikte Popularität beim direkten Vergleich von Koalitionsstrukturen. This thesis deals with the computational complexity of various problems from cooperative game theory. On the one hand we examine the existence and verification of stability concepts in cooperative games with transferable utility and in hedonic games; on the other hand we look into several forms of influence on the output of a game via manipulation, control and bribery. We turn to manipulative action in the sense of strategically merging players or splitting a player into false identities as well as structural control by adding or deleting players in weighted voting games. In this setting, considered solution concepts are the probabilistic Penrose--Banzhaf index and the Shapley--Shubik index which the manipulators intend to improve to their advantage. Amongst others, we show that the problem of whether merging a given coalition in a given game is beneficial, is complete for probabilistic polynomial time. Additionally, we generalize a framework for manipulation to arbitrary classes of cooperative games and reflect on properties in general and examplarily in classes like unanimity games. Moreover, we consider bribery in path-disruption games, where an adversary tries to travel from a source vertex to a target vertex and pays selected agents in order for them to unblock their vertices. The corruption is successful if it is not profitable or impossible for the remaining coalitions to prevent the adversary from reaching the target via an open path. For several adversarial players and costs for blocking a vertex, we show that the bribery problem is complete for the second level of the polynomial hierarchy. We expand these games to a probabilistic model where the target of the adversary is uncertain, and inspect them with respect to common stability concepts such as the core. Here, it can be observed that the more general case does not behave differently from the more special case in terms of complexity. Furthermore, we study questions of stability likewise in hedonic games. Firstly, we inquire into wonderful stability in enemy-oriented hedonic games. We raise the lower bound of the problem of whether there exists a wonderfully stable partition in the graph of an underlying game, to DP, that is, to the second level of the Boolean hierarchy. On the way towards its exact complexity, we show that coDP-hardness would be sufficient to prove completeness for parallel access to NP. Secondly, we introduce a new model of hedonic games with ordinal preferences and thresholds in which players partition their co-players into the sets of friends, enemies, and neutral players while at the same time they specify a weak order over the former two sets. This relation is extended to a set of possible preferences over coalitions such that it is reasonable to define the notions of possible and necessary stability. We analyse the complexity of various concepts such as Nash stability and establish axiomatic properties of these games. Finally, we propose a further variant of hedonic games with altruistic influences. In representations known in the literature so far, agents are assumed to be selfish and their preferences only depend on their own opinion. Based on friend-oriented extensions, we now allow influences of friends on a player's preference relation by incorporating the average opinion among friends within a coalition in three degrees of altruism. Besides properties reasonably modelled for this environment, we investigate the complexity of stability concepts such as strict popularity when comparing coalition structures.
Lizenz:	Urheberrechtsschutz
Fachbereich / Einrichtung:	Mathematisch- Naturwissenschaftliche Fakultät » WE Informatik
Dokument erstellt am:	14.09.2016
Dateien geändert am:	14.09.2016
Promotionsantrag am:	16.09.2015
Datum der Promotion:	21.04.2016