Stochastic multiplayer games : theory and algorithms

• Stochastische Mehrpersonenspiele : Theorie und Algorithmen

Ummels, Michael; Grädel, Erich (Thesis advisor)

Amsterdam : Pallas Publ. (2010, 2011)
Doktorarbeit

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

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.

Einrichtungen

• Lehr- und Forschungsgebiet Mathematische Grundlagen der Informatik (Logik und Komplexität) [117220]
• Fachgruppe Mathematik [110000]