2016/10/25 by Patricia Bouyer, Bouyer, Patricia, Piotr Hofman +7
Engineering · Physics and Astronomy · #Advanced Thermodynamics and Statistical Mechanics #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Logic in Computer Science (cs.LO) #Low-power high-performance VLSI design
paper · doi:10.48550/arxiv.1610.07858
openalex publication_date 2016/10/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.