Name
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. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1007/978-3-642-02658-4_24 | CAV |
Keywords | Field | DocType |
non-trivial characterization,stochastic liminf-payoff game,deterministic setting,deterministic total-payoff game,stochastic parity game,total-payoff game,liminf-payoff game,nested fixpoints,nested fixpoint,stochastic setting,nested fixpoint equation,polynomial time | Hierarchical control system,Graph,Mathematical optimization,Algebra,Computer science,Theoretical computer science,Optimality equation,Fixed point,Corollary,Stochastic game | Conference |
Volume | ISSN | Citations |
5643 | 0302-9743 | 4 |
PageRank | References | Authors |
0.41 | 11 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Thomas Martin Gawlitza | 1 | 88 | 6.37 |
| Helmut Seidl | 2 | 1468 | 103.61 |