Title: Perfect Half Space Games,
Abstract: We introduce perfect half space games, in which the goal of Player 2 is to
make the sums of encountered multi-dimensional weights diverge in a direction
which is consistent with a chosen sequence of perfect half spaces (chosen
dynamically by Player 2). We establish that the bounding games of Jurdziński
et al. (ICALP 2015) can be reduced to perfect half space games, which in turn
can be translated to the lexicographic energy games of Colcombet and
Niwiński, and are positionally determined in a strong sense (Player 2 can
play without knowing the current perfect half space). We finally show how
perfect half space games and bounding games can be employed to solve
multi-dimensional energy parity games in pseudo-polynomial time when both the
numbers of energy dimensions and of priorities are fixed, regardless of whether
the initial credit is given as part of the input or existentially quantified.
This also yields an optimal 2-EXPTIME complexity with given initial credit,
where the best known upper bound was non-elementary.