Lightning talk: 2-dimensional Average-energy Games

18^th February 2020, 11:15
Martin Zimmermann

Abstract

An average-energy game is played in a finite integer-weighted arena. The sum of weights traversed along a play prefix is interpreted as its energy level (think of a battery that is drained or recharged along edges). Player 0 wins a play if the average energy level is bounded by some given threshold.

It is known that solving one-dimensional average-energy games is decidable while solving 3-dimensional average-energy games is undecidable. I will give some informal introduction to energy and average-energy games and then invite you to solve the 2-dimensional case.