Textdokument
Exponentielle untere Schranken zur Lösung infinitärer Auszahlungsspiele und linearer Programme
Vorschaubild nicht verfügbar
Volltext URI
Dokumententyp
Dateien
Zusatzinformation
Datum
Autor:innen
Zeitschriftentitel
ISSN der Zeitschrift
Bandtitel
Verlag
Gesellschaft für Informatik
Zusammenfassung
Wir betrachten die Strategieverbesserungstechnik zur Lösung infinitärer Auszahlungsspiele sowie den Simplexalgorithmus zur Lösung damit assoziierter linearer Programme. Unser Beitrag zur Strategieverbesserung und zum Simplexverfahren besteht in der Konstruktion exponentieller unterer Schranken für mehrere Verbesserungs- bzw. Pivotregeln. Für jede Verbesserungsregel, die wir in dieser Arbeit unter die Lupe nehmen, konstruieren wir Zweispieler-Paritätsspiele, zu deren Lösung der entsprechend parametrisierte Strategieverbesserungsalgorithmus eine exponentielle Anzahl an Iterationen benötigt. Anschließend übersetzen wir diese Spiele in Einspieler-Markov-Entscheidungsprozesse, die wiederum beinahe direkt in konkrete lineare Programme überführt werden können, zu deren Lösung der entsprechende parametrisierte Simplexalgorithmus dieselbe Anzahl an Iterationen benötigt. Zusätzlich zeigen wir, wie sich die unteren Schranken auf expressivere Spieleklassen wie Auszahlungs- und stochastische Auszahlungsspiele übertragen lassen.