h1

000063898 001__ 63898
000063898 005__ 20220422220746.0
000063898 020__ $$a978-90-8555-040-2
000063898 0247_ $$2Laufende Nummer$$a30465
000063898 0247_ $$2URN$$aurn:nbn:de:hbz:82-opus-34512
000063898 0247_ $$2HSB$$a999910026103
000063898 0247_ $$2OPUS$$a3451
000063898 037__ $$aRWTH-CONV-125305
000063898 041__ $$aEnglish
000063898 082__ $$a004
000063898 0847_ $$2msc$$a68Q10 * 68Q1
000063898 1001_ $$0P:(DE-82)017696$$aUmmels, Michael$$b0$$eAuthor
000063898 245__ $$aStochastic multiplayer games : theory and algorithms$$cvorgelegt von Michael Ummels$$honline, print
000063898 246_3 $$aStochastische Mehrpersonenspiele : Theorie und Algorithmen$$yGerman
000063898 260__ $$aAmsterdam$$bPallas Publ.$$c2010
000063898 260__ $$c2011
000063898 300__ $$a174 S. : graph. Darst.
000063898 3367_ $$0PUB:(DE-HGF)11$$2PUB:(DE-HGF)$$aDissertation / PhD Thesis$$bphd$$mphd
000063898 3367_ $$02$$2EndNote$$aThesis
000063898 3367_ $$2DRIVER$$adoctoralThesis
000063898 3367_ $$2BibTeX$$aPHDTHESIS
000063898 3367_ $$2DataCite$$aOutput Types/Dissertation
000063898 3367_ $$2ORCID$$aDISSERTATION
000063898 500__ $$aDruckausgabe: 2010. - Onlineausgabe: 2011
000063898 502__ $$aZugl.: Aachen, Techn. Hochsch., Diss., 2010$$gFak01$$o2010-01-27
000063898 520__ $$aStochastic 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.$$leng
000063898 5203_ $$aStochastische 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.$$lger
000063898 591__ $$aGermany
000063898 650_7 $$2SWD$$aStochastisches Spiel
000063898 650_7 $$2SWD$$aUnendliches Spiel
000063898 650_7 $$2SWD$$aNash-Gleichgewicht
000063898 650_7 $$2SWD$$aKomplexitätstheorie
000063898 650_7 $$2SWD$$aUnentscheidbarkeit
000063898 653_7 $$aInformatik
000063898 653_7 $$2ger$$aTeilspiel-perfektes Gleichgewicht
000063898 653_7 $$2eng$$astochastic game
000063898 653_7 $$2eng$$ainfinite game
000063898 653_7 $$2eng$$aNash equilibrium
000063898 653_7 $$2eng$$asubgame-perfect equilibrium
000063898 653_7 $$2eng$$acomplexity theory
000063898 7001_ $$0P:(DE-82)IDM00039$$aGrädel, Erich$$b1$$eThesis advisor
000063898 8564_ $$uhttps://publications.rwth-aachen.de/record/63898/files/3451.pdf
000063898 909CO $$ooai:publications.rwth-aachen.de:63898$$pVDB$$pdriver$$purn$$popen_access$$popenaire$$pdnbdelivery
000063898 915__ $$0StatID:(DE-HGF)0510$$2StatID$$aOpenAccess
000063898 9201_ $$0I:(DE-82)117220_20140620$$k117220$$lLehr- und Forschungsgebiet Mathematische Grundlagen der Informatik (Logik und Komplexität)$$x0
000063898 9201_ $$0I:(DE-82)110000_20140620$$k110000$$lFachgruppe Mathematik$$x1
000063898 961__ $$c2013-10-25$$x2011-02-09$$z2012-02-20
000063898 970__ $$aHT016691437
000063898 980__ $$aphd
000063898 980__ $$aI:(DE-82)117220_20140620
000063898 980__ $$aI:(DE-82)110000_20140620
000063898 980__ $$aVDB
000063898 980__ $$aUNRESTRICTED
000063898 980__ $$aConvertedRecord
000063898 980__ $$aFullTexts
000063898 9801_ $$aFullTexts