Energy and meanpayoff games with imperfect information

Abstract. We consider two-player games with imperfect information and quan-titative objective. The game is played on a weighted graph with a state space partitioned into classes of indistinguishable states, giving players partial knowl-edge of the state. In an energy game, the weights represent resource consumption and the objective of the game is to maintain the sum of weights always nonnega-tive. In a mean-payoff game, the objective is to optimize the limit-average usage of the resource. We show that the problem of determining if an energy game with imperfect information with fixed initial credit has a winning strategy is decidable, while the question of the existence of some initial credit such that the game has a winning strategy is undecidable. This undecidability result carries over to mean-payoff games with imperfect information. On the positive side, using a simple restriction on the game graph (namely, that the weights are visible), we show that these problems become EXPTIME-complete.