Quantitative Games with Interval Objectives

Hunter, Paul; Raskin, Jean-Francois

doi:10.4230/LIPIcs.FSTTCS.2014.365

File

LIPIcs.FSTTCS.2014.365.pdf

Filesize: 0.53 MB
13 pages

Document Identifiers

DOI: 10.4230/LIPIcs.FSTTCS.2014.365
URN: urn:nbn:de:0030-drops-48569

Author Details

Paul Hunter

Jean-Francois Raskin

Cite AsGet BibTex

Paul Hunter and Jean-Francois Raskin. Quantitative Games with Interval Objectives. In 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 29, pp. 365-377, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)
https://doi.org/10.4230/LIPIcs.FSTTCS.2014.365

Abstract

Traditionally quantitative games such as mean-payoff games and discount sum games have two players - one trying to maximize the payoff, the other trying to minimize it. The associated decision problem, "Can Eve (the maximizer) achieve, for example, a positive payoff?" can be thought of as one player trying to attain a payoff in the interval (0,infinity). In this paper we consider the more general problem of determining if a player can attain a payoff in a finite union of arbitrary intervals for various payoff functions (liminf/limsup, mean-payoff, discount sum, total sum). In particular this includes the interesting exact-value problem, "Can Eve achieve a payoff of exactly (e.g.) 0?"

Keywords

Quantitative games
Mean-payoff games
Discount sum games

Metrics

Access Statistics
Total Accesses (updated on a weekly basis)

0

PDF Downloads

0

Metadata Views

References

U. Boker and T. A. Henzinger. Determinizing discounted-sum automata. In CSL, pages 82-96, 2011.
U. Boker and J. Otop. Personal communcation, 2014.
T. Brázdil, P. Jancar, and A. Kucera. Reachability games on extended vector addition systems with states. In ICALP (2), pages 478-489, 2010.
L. Brim, J. Chaloupka, L. Doyen, R. Gentilini, and J.-F. Raskin. Faster algorithms for mean-payoff games. Formal Methods in System Design, 38(2):97-118, 2011.
K. Chatterjee, L. Doyen, and T. A. Henzinger. A survey of partial-observation stochastic parity games. Formal Methods in System Design, 43(2):268-284, 2013.
K. Chatterjee, L. Doyen, T. A. Henzinger, and J.-F. Raskin. Generalized mean-payoff and energy games. In Proc. of FSTTCS, pages 505-516, 2010.
K. Chatterjee, V. Forejt, and D. Wojtczak. Multi-objective discounted reward verification in graphs and mdps. In LPAR, pages 228-242, 2013.
A. Ehrenfeucht and J. Mycielski. Positional strategies for mean payoff games. International Journal of Game Theory, 8:109-113, 1979.
J. Fearnley and M. Jurdzinski. Reachability in two-clock timed automata is pspace-complete. In ICALP, volume 2, pages 212-223, 2013.
T. Gawlitza and H. Seidl. Games through nested fixpoints. In CAV, pages 291-305, 2009.
H. Gimbert and W. Zielonka. When can you play positionally? In MFCS, pages 686-697, 2004.
P. Hunter. Reachability in succinct one-counter games. Available at http://arxiv.org/abs/1407.1996, 2014.
E. Kopczynski. Omega-regular half-positional winning conditions. In CSL, pages 41-53, 2007.
J. Reichert. On the complexity of counter reachability games. In RP, pages 196-208, 2013.
S. Schewe. Solving parity games in big steps. In FSTTCS, pages 449-460, 2007.
O. Serre. Parity games played on transition graphs of one-counter processes. In FoSSaCS, pages 337-351, 2006.
W. Zielonka. Infinite games on finitely coloured graphs with applications to automata on infinite trees. Theoretical Computer Science, 200:135-183, 1998.
U. Zwick and M. Paterson. The complexity of mean payoff games on graphs. Theoretical Computer Science, 158(1):343-359, 1996.