Fixed-dimensional energy games are in pseudo-polynomial time

DOI10.1007/978-3-662-47666-6_21MaRDI QIDQ3449481zbMATH OpenOpenAlexFDO

Authors Marcin Jurdziński, Ranko Lazić, Sylvain Schmitz

Publication date 4 November 2015

Published in Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1502.06875

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Applications of game theory (91A80)

Abstract: We generalise the hyperplane separation technique (Chatterjee and Velner, 2013) from multi-dimensional mean-payoff to energy games, and achieve an algorithm for solving the latter whose running time is exponential only in the dimension, but not in the number of vertices of the game graph. This answers an open question whether energy games with arbitrary initial credit can be solved in pseudo-polynomial time for fixed dimensions 3 or larger (Chaloupka, 2013). It also improves the complexity of solving multi-dimensional energy games with given initial credit from non-elementary (Br'azdil, Janv{c}ar, and Kuv{c}era, 2010) to 2EXPTIME, thus establishing their 2EXPTIME-completeness.

Recommendations

• Faster algorithms for mean-payoff games
• Generalized mean-payoff and energy games
• A faster deterministic exponential time algorithm for energy games and mean payoff games

Cites work

• Alternating vector addition systems with states
• Energy games in multiweighted automata
• Generalized mean-payoff and energy games
• Hyperplane Separation Technique for Multidimensional Mean-Payoff Games
• Infinite-state energy games
• Optimal bounds for multiweighted and parametrised energy games
• Reachability games on extended vector addition systems with states
• Solving parity games on integer vectors
• The covering and boundedness problems for vector addition systems
• Z-reachability problem for games on 2-dimensional vector addition systems with states is in P

Cited in

(22)

• Efficient Algorithms for Omega-Regular Energy Games
• Simple stochastic games with almost-sure energy-parity objectives are in NP and conp
• Bounding Average-Energy Games
• scientific article; zbMATH DE number 7447732 (Why is no real title available?)
• Deciding fast termination for probabilistic VASS with nondeterminism
• The fixed initial credit problem for partial-observation energy games is \textsc{Ack}-complete
• Controlling a population
• scientific article; zbMATH DE number 7559480 (Why is no real title available?)
• Perfect half space games
• Model checking and synthesis for branching multi-weighted logics
• Energy mean-payoff games
• Games where you can play optimally with arena-independent finite memory
• State of the Art in Logics for Verification of Resource-Bounded Multi-Agent Systems
• Strategic reasoning with a bounded number of resources: the quest for tractability
• scientific article; zbMATH DE number 7089067 (Why is no real title available?)
• Reachability games with relaxed energy constraints
• Reachability games with relaxed energy constraints
• On the complexity of resource-bounded logics
• Extending Finite-Memory Determinacy by Boolean Combination of Winning Conditions
• Synthesis for multi-weighted games with branching-time winning conditions
• Hyperplane separation technique for multidimensional mean-payoff games
• On decidability and complexity of low-dimensional robot games

This page was built for publication: Fixed-dimensional energy games are in pseudo-polynomial time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3449481)