Bounding Average-Energy Games

DOI10.1007/978-3-662-54458-7_11zbMATH Open1392.68115arXiv1610.07858OpenAlexW2546285752MaRDI QIDQ2988367FDOQ2988367

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)

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.

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

Recommendations

• Average-energy games
• Average-energy games
• Generalized mean-payoff and energy games
• scientific article; zbMATH DE number 7649929
• 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
• scientific article; zbMATH DE number 7453074
• Reachability games with relaxed energy constraints

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)

Cites Work

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

Cited In (13)

• Title not available (Why is that?)
• Perfect half space games
• Average-energy games
• On decidability and complexity of low-dimensional robot games
• Bounding Average-Energy Games
• Average-energy games
• Title not available (Why is that?)
• Title not available (Why is that?)
• The robot routing problem for collecting aggregate stochastic rewards
• Reachability games with relaxed energy constraints
• Extending Finite-Memory Determinacy by Boolean Combination of Winning Conditions
• Optimal bounds for multiweighted and parametrised energy games
• Title not available (Why is that?)

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)