Bounding Average-Energy Games

Bouyer, Patricia, Hofman, Piotr, Markey, Nicolas, Randour, Mickael and Zimmermann, Martin ORCID: 0000-0002-8038-2453 (2017) Bounding Average-Energy Games. .

Text main.pdf - Author Accepted Manuscript Download (395kB) | Preview

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 prove 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.

Item Type:	Conference or Workshop Item (Unspecified)
Depositing User:	Symplectic Admin
Date Deposited:	15 Jul 2019 13:11
Last Modified:	19 Jan 2023 00:37
DOI:	10.1007/978-3-662-54458-7_11
Related URLs:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3050019