[en] We study zero-sum turn-based games on graphs. In this note, we show the
existence of a game objective that is $\Pi^0_3$-complete for the Borel
hierarchy and that is positional, i.e., for which positional strategies suffice
for the first player to win over arenas of arbitrary cardinality. To the best
of our knowledge, this is the first known such objective; all previously known
positional objectives are in $\Sigma^0_3$. The objective in question
is a qualitative variant of the well-studied total-payoff objective, where the
goal is to maximise the sum of weights.
Research center :
CREMMI - Modélisation mathématique et informatique
ANR - Agence Nationale de la Recherche NCN - National Science Centre Poland
Funding text :
Antonio Casares is funded by the Polish National Science Centre (NCN) grant Polynomial finite state computation (2022/46/A/ST6/00072). Pierre Vandenhove is funded by ANR project G4S (ANR-21-CE48-0010-01).