Games with winning conditions of high Borel complexity

We first consider infinite two-player games on pushdown graphs. In previous work, Cachat et al. [Solving pushdown games with a Σ3-winning condition, in: Proc. 11th Annu. Conf. of the European Association for Computer Science Logic, CSL 2002, Lecture Notes in Computer Science, Vol. 2471, Springer, Berlin, 2002, pp. 322–336] have presented a winning decidable condition that is Σ3-complete in the Borel hierarchy. This was the first example of a decidable winning condition of such Borel complexity. We extend this result by giving a family of decidable winning conditions of arbitrary finite Borel complexity. From this family, we deduce a family of decidable winning conditions of arbitrary finite Borel complexity for games played on finite graphs. The problem of deciding the winner for these conditions is shown to be non-elementary.