TY - GEN
T1 - Games through nested fixpoints
AU - Gawlitza, Thomas Martin
AU - Seidl, Helmut
PY - 2009
Y1 - 2009
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=70350244863&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-02658-4_24
DO - 10.1007/978-3-642-02658-4_24
M3 - Conference contribution
AN - SCOPUS:70350244863
SN - 3642026575
SN - 9783642026577
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 291
EP - 305
BT - Computer Aided Verification - 21st International Conference, CAV 2009, Proceedings
T2 - 21st International Conference on Computer Aided Verification, CAV 2009
Y2 - 26 June 2009 through 2 July 2009
ER -