Stochastic multiplayer games : theory and algorithms

Ummels, Michael; Grädel, Erich

doi:30465

Stochastic multiplayer games : theory and algorithms = Stochastische Mehrpersonenspiele : Theorie und Algorithmen

Ummels, Michael (Author)

2010 & 2011

Verantwortlichkeitsangabevorgelegt von Michael Ummels

ImpressumAmsterdam : Pallas Publ. 2010

Umfang174 S. : graph. Darst.

ISBN978-90-8555-040-2

Zugl.: Aachen, Techn. Hochsch., Diss., 2010

Druckausgabe: 2010. - Onlineausgabe: 2011

Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter
Grädel, Erich (Thesis advisor)

Tag der mündlichen Prüfung/Habilitation
2010-01-27

Online
URN: urn:nbn:de:hbz:82-opus-34512
URL: https://publications.rwth-aachen.de/record/63898/files/3451.pdf

Einrichtungen

Inhaltliche Beschreibung (Schlagwörter)
Stochastisches Spiel (Genormte SW) ; Unendliches Spiel (Genormte SW) ; Nash-Gleichgewicht (Genormte SW) ; Komplexitätstheorie (Genormte SW) ; Unentscheidbarkeit (Genormte SW) ; Informatik (frei) ; Teilspiel-perfektes Gleichgewicht (frei) ; stochastic game (frei) ; infinite game (frei) ; Nash equilibrium (frei) ; subgame-perfect equilibrium (frei) ; complexity theory (frei)

Thematische Einordnung (Klassifikation)
DDC: 004
msc: 68Q10 * 68Q1

Kurzfassung
Stochastische Spiele werden von mehreren Spielern auf einem gerichteten Graphen gespielt. Intuitiv wird ein Spielstein entlang der Kanten des Graphen bewegt. Jeder Knoten des Graphen wird entweder von einem der Spieler kontrolliert oder er ist stochastisch. Im ersten Fall ist es die Aufgabe des jeweiligen Spielers den Spielstein zu bewegen. Im zweiten Fall bestimmt eine feste Wahrscheinlichkeitsverteilung zu welchem Knoten der Spielstein als nächstes gelangt. Eine Partie eines stochastischen Spiels ist also ein im allgemeinen unendlicher Pfad durch den Graphen. Am Ende einer Partie enthält jeder Spieler eine Auszahlung. Im einfachsten Fall, den wir hier betrachten, ist die Auszahlung für jeden Spieler entweder 0 oder 1. Eine Partie wird von einem Spieler also entweder gewonnen oder verloren. Aufgrund des Vorkommens von stochastischen Knoten kann die erwartete Auszahlung für einen Spieler, also seine Wahrscheinlichkeit zu gewinnen, jedoch eine beliebige Zahl zwischen 0 und 1 sein. Diese Dissertation entwickelt die algorithmische Theorie stochastischer Mehrpersonen-Spiele. Insbesondere beschäftigt sich diese Arbeit mit der Berechnungskomplexität von Nash-Gleichgewichten in solchen Spielen. Traditionell wird diese Komplexität als der Aufwand angesehen, ein beliebiges Nash-Gleichgewicht zu berechnen. Hier verstehen wir darunter jedoch auch die Komplexität ein Gleichgewicht zu finden, dessen Auszahlung gewisse Eigenschaften erfüllt. Dieses Problem entspricht dem folgenden Entscheidungsproblem, welches wir NE nennen: Gegeben ein Spiel sowie eine obere und untere Schranke für die Auszahlung, entscheide ob das Spiel ein Gleichgewicht hat, dessen erwartete Auszahlung innerhalb der Schranken liegt. Das Hauptergebnis dieser Arbeit ist, dass NE unentscheidbar ist, unabhängig davon ob man sich bei der Suche nach Gleichgewichten auf solche in reinen Strategien beschränkt oder randomisierte Strategien zulässt. In der Praxis wird man eher nach Gleichgewichten in einfacheren Strategien suchen als in solchen, deren Verhalten von der ganzen bisher gesehenen Knotenfolge abhängen können. Eine besonders attraktive Form von Strategien sind etwa (reine oder randomisierte) Strategien, deren Verhalten nur vom aktuellen Knoten abhängt, so genannte stationäre Strategien. Wir zeigen, dass für typische Auszahlungsfunktionen NE mit randomisierten stationären Strategien in der Komplexitätsklasse PSPACE liegt, während das Problem für reine stationäre Strategien NP-vollständig ist. Komplettiert wird unsere Analyse durch Algorithmen für einige Einschränkungen von NE. Zum Beispiel zeigen wir, dass NE entscheidbar wird, wenn man nach Gleichgewichten sucht, in denen für jeden Spieler die erwartete Auszahlung 0 oder 1 beträgt, oder wenn man nach Gleichgewichten sucht, in denen alle Spieler bis auf einen mit Wahrscheinlichkeit 1 gewinnen. Für die Komplexität dieser Probleme präsentieren wir obere und untere Schranken, die in den meiste Fällen übereinstimmen.

Stochastic games provide a versatile model for reactive systems that are affected by random events. Intuitively, a play of such a game evolves by moving a token along the edges of a directed graph. Each vertex of the graph is either controlled by one of the players, or it is a stochastic vertex. Whenever the token arrives at a non-stochastic vertex, the player who controls this vertex must move the token to a successor vertex; when the token arrives at a stochastic vertex, a fixed probability distribution determines the next vertex. At the end of a play, every player receives a payoff. In our case, the possible payoffs of a single play for one player are just 0 and 1: each player either wins or loses a play. However, due to the presence of stochastic vertices, a player's expected payoff, i.e. her probability of winning, can be an arbitrary number between 0 and 1. This dissertation develops the algorithmic theory of stochastic multiplayer games. In particular, we analyse the computational complexity of finding Nash equilibria in these games. On the conceptual side, we argue that the computational complexity of equilibria should not only be measured by the complexity of finding an arbitrary equilibrium, but also by the complexity of finding equilibria with certain payoffs. Specifically, we single out the following decision problem, which we call NE, as a yardstick for the complexity of equilibria: Given a game as well as an upper and a lower threshold on the payoff, decide whether the game has an equilibrium whose payoff lies in-between the given thresholds. The main result of this thesis is that NE is undecidable, regardless whether one looks for an equilibrium in pure or randomised strategies. In practice, equilibria in simpler strategies are more desirable than equilibria in arbitrary pure or randomised strategies, whose behaviour may depend on the whole sequence of vertices seen so far. In particular, strategies that only depend on the current vertex, so-called stationary strategies (which might again be pure or randomised) are very appealing. We prove that, for many typical payoff functions, NE with respect to stationary strategies is both NP-hard and contained in PSPACE, whereas NE with respect to pure stationary strategies is NP-complete. Our analysis is completed by providing algorithms for several fragments of NE. For instance, we show that NE becomes decidable when one searches for an equilibrium where the expected payoff for each player is either 0 or 1, or when one searches for an equilibrium where all but one player receive expected payoff 1. Our algorithms are accompanied by hardness proofs, which provide (almost always matching) lower bounds on the complexities of the problems we consider.

Fulltext:
PDF