Games through nested fixpoints

Thomas Martin Gawlitza, Helmut Seidl

Publikation: Beitrag in Buch/Bericht/KonferenzbandKonferenzbeitragBegutachtung

14 Zitate (Scopus)

Abstract

In this paper we consider two-player zero-sum payoff games on finite graphs, both in the deterministic as well as in the stochastic setting. In the deterministic setting, we consider total-payoff games which have been introduced as a refinement of mean-payoff games [10, 18]. In the stochastic setting, our class is a turn-based variant of liminf-payoff games [4, 15, 16]. In both settings, we provide a non-trivial characterization of the values through nested fixpoint equations. The characterization of the values of liminf-payoff games moreover shows that solving liminf-payoff games is polynomial-time reducible to solving stochastic parity games. We construct practical algorithms for solving the occurring nested fixpoint equations based on strategy iteration. As a corollary we obtain that solving deterministic total-payoff games and solving stochastic liminf-payoff games is in UP ∩ co- UP.

OriginalspracheEnglisch
TitelComputer Aided Verification - 21st International Conference, CAV 2009, Proceedings
Seiten291-305
Seitenumfang15
DOIs
PublikationsstatusVeröffentlicht - 2009
Veranstaltung21st International Conference on Computer Aided Verification, CAV 2009 - Grenoble, Frankreich
Dauer: 26 Juni 20092 Juli 2009

Publikationsreihe

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Band5643 LNCS
ISSN (Print)0302-9743
ISSN (elektronisch)1611-3349

Konferenz

Konferenz21st International Conference on Computer Aided Verification, CAV 2009
Land/GebietFrankreich
OrtGrenoble
Zeitraum26/06/092/07/09

Fingerprint

Untersuchen Sie die Forschungsthemen von „Games through nested fixpoints“. Zusammen bilden sie einen einzigartigen Fingerprint.

Dieses zitieren