Bounding Average-Energy Games

DOI10.1007/978-3-662-54458-7_11MaRDI QIDQ2988367zbMATH OpenOpenAlexFDO

Authors Patricia Bouyer, Piotr Hofman, Nicolas Markey, Mickael Randour, Martín G. Zimmermann

Publication date 19 May 2017

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Applications of game theory (91A80) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Abstract: We consider average-energy games, where the goal is to minimize the long-run average of the accumulated energy. While several results have been obtained on these games recently, decidability of average-energy games with a lower-bound constraint on the energy level (but no upper bound) remained open; in particular, so far there was no known upper bound on the memory that is required for winning strategies. By reducing average-energy games with lower-bounded energy to infinite-state mean-payoff games and analyzing the density of low-energy configurations, we show an almost tight doubly-exponential upper bound on the necessary memory, and that the winner of average-energy games with lower-bounded energy can be determined in doubly-exponential time. We also prove EXPSPACE-hardness of this problem. Finally, we consider multi-dimensional extensions of all types of average-energy games: without bounds, with only a lower bound, and with both a lower and an upper bound on the energy. We show that the fully-bounded version is the only case to remain decidable in multiple dimensions.

Recommendations

• Average-energy games
• Average-energy games
• Generalized mean-payoff and energy games
• Energy mean-payoff games
• Optimal bounds for multiweighted and parametrised energy games
• Energy and mean-payoff timed games
• Energy and mean-payoff games with imperfect information
• Infinite-state energy games
• Reachability games with relaxed energy constraints
• Reachability games with relaxed energy constraints

Cites work

• A characterization of the minimum cycle mean in a digraph
• Automatic Synthesis of Robust and Optimal Controllers – An Industrial Case Study
• Average-energy games
• Better Quality in Synthesis through Quantitative Objectives
• Bounding Average-Energy Games
• Energy parity games
• Faster algorithms for mean-payoff games
• Fixed-dimensional energy games are in pseudo-polynomial time
• Infinite Runs in Weighted Timed Automata with Energy Constraints
• Looking at mean-payoff and total-payoff through windows
• Markov decision processes and stochastic games with total effective payoff
• Mean-payoff pushdown games
• Optimal bounds for multiweighted and parametrised energy games
• Positional strategies for mean payoff games
• Pushdown processes: Games and model-checking
• Reachability in succinct one-counter games
• Reachability in two-clock timed automata is PSPACE-complete
• The bad match; a total reward stochastic game
• The complexity of mean payoff games on graphs
• The complexity of multi-mean-payoff and multi-energy games
• Undecidability of two-dimensional robot games

Cited in

(12)

• Average-energy games
• Average-energy games
• Bounding Average-Energy Games
• The robot routing problem for collecting aggregate stochastic rewards
• scientific article; zbMATH DE number 7559480 (Why is no real title available?)
• Perfect half space games
• Energy mean-payoff games
• Optimal bounds for multiweighted and parametrised energy games
• Reachability games with relaxed energy constraints
• Reachability games with relaxed energy constraints
• Extending Finite-Memory Determinacy by Boolean Combination of Winning Conditions
• On decidability and complexity of low-dimensional robot games

This page was built for publication: Bounding Average-Energy Games

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