  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.
