A positional

Π⁰ 3-complete objective

Antonio Casares, Pierre Ohlmann, Pierre Vandenhove

► To cite this version:

Antonio Casares, Pierre Ohlmann, Pierre Vandenhove. A positional Π⁰ 3-complete objective. 2025. hal-05408804

HAL Id: hal-05408804

https://amu.hal.science/hal-05408804v1

Preprint submitted on 10 Dec 2025

**HAL** is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# A positional $\Pi_3^0$-complete objective

Antonio Casares ⬒

University of Warsaw, Poland

Pierre Ohlmann ☐

CNRS, Laboratoire d'Informatique et des Systèmes, Marseille, France

Pierre Vandenhove ☐

LaBRI, Université de Bordeaux, France

## Abstract

We study zero-sum turn-based games on graphs. In this note, we show the existence of a game objective that is $\Pi_3^0$-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_3^0$. 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.

**2012 ACM Subject Classification** Theory of computation → Logic and verification

**Keywords and phrases** Infinite-duration games, positionality, Borel hierarchy, total-payoff objectives

**Funding** 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).

## 1 Context and contribution

We consider infinite-duration zero-sum two-player games played on (potentially infinite) graphs [6]. In this context, two players, Eve and Adam, take turns in moving a token along the edges of an edge-labelled directed game graph. This interaction produces an infinite path inducing an infinite word $x$ in $C^\omega$, where $C$ is the (potentially infinite, but assumed countable) alphabet of labels. An *objective W* $\subseteq C^\omega$ is specified in advance; Eve wins the game if the word $x$ belongs to W, otherwise Adam wins.

A strategy is called *positional* (or *memoryless*) if it chooses the next move only according to the current vertex of the graph containing the token, regardless of past moves. An objective is called *positional*<fnref n="1" /> if for any game graph (of arbitrary cardinality), Eve has a positional strategy winning from every vertex from which she has a winning strategy.

To the best of our knowledge, all previously known positional objectives belong to $\Sigma_3^0$, the (existential) third level of the Borel hierarchy in the usual product topology<fnref n="2" /> over $C^\omega$. For instance, the positionality of the $\omega$-regular languages is well-understood [4], but they all lie in $\Delta_3^0 = \Sigma_3^0 \cap \Pi_3^0$ (as shown in [3]). There are additional examples stemming for characterizations for objectives in $\Sigma_1^0$, $\Pi_1^0$, and $\Sigma_2^0$ (see, respectively, [2], [5] and [10]). The following natural $\Sigma_3^0$-complete objective is also shown to be positional in [6]: $\text{InfOcc} = \{x \in \mathbb{N}^\omega \mid \exists c \in \mathbb{N}, |x|_c = \infty\}$, where $|x|_c$ denotes the number of occurrences of $c$ in $x$ ($\text{InfOcc}$ is thus the set of words in which some number occurs infinitely often). However, its complement, which is a $\Pi_3^0$-complete objective, is not positional — to see it, consider a game graph with a single vertex where Eve has to choose among infinitely many self-loops, each labelled with a different number

<footnote n="1">¹ The literature sometimes uses “half-positional” for this notion, since there is a requirement on Eve’s strategy complexity, but not on Adam’s.</footnote>

<footnote n="2">² We recall that the open sets of this topology are those of the form $LC^\omega$, for $L \subseteq C^*$ a set of finite words.</footnote>
## 2 A positional $\Pi_3^0$-complete objective

$c \in \mathbb{N}$. This leads to the following question: does there exist a positional objective that does not belong to $\Sigma_3^0$?

We answer this question positively, by showing that the following $\Pi_3^0$-complete objective over $C = \mathbb{Z}$ is positional:

$$ \text{SumTolInfinity} = \{w_0 w_1 \dots \in \mathbb{Z}^\omega \mid \lim_{k \to \infty} \sum_{i=0}^{k-1} w_i = +\infty\}. $$

This objective is a qualitative variant of a total-payoff objective (also called total-reward objective), where the goal is to maximise the (limsup or liminf of the) sum of weights. Total-payoff objectives are positional over finite arenas [7]. However, over infinite arenas, they are in general not positional, with various classes of strategies needed depending on the variant considered (limsup or liminf, and with a rational, $+\infty$, or $-\infty$ threshold) and the class of arenas [10, 1]. Objective SumTolInfinity is a specific natural variant which turns out to have a remarkably low strategy complexity even over the most general class of arenas. Our results fill a gap in the understanding of quantitative objectives [1].

Note that SumTolInfinity is prefix-independent (i.e., for all $x \in \mathbb{Z}^*$ and $x' \in \mathbb{Z}^\omega$, $x' \in \text{SumTolInfinity}$ if and only if $xx' \in \text{SumTolInfinity}$).

### ▶ Theorem 1. The objective SumTolInfinity is $\Pi_3^0$-complete and positional.

The rest of the note is devoted to the proof of Theorem 1. We quickly show in Section 2 that SumTolInfinity is $\Pi_3^0$-complete; our main contribution, in Section 3, is a positionality proof based on constructing (almost)-universal graphs for SumTolInfinity, and applying [9, Theorem 3.2].

Naturally, a follow-up open question is whether every level of the Borel hierarchy admits a complete objective that is positional.

## 2 $\Pi_3^0$-completeness of SumTolInfinity

We refer to [8] for definitions on the Borel hierarchy.

To show that SumTolInfinity is in $\Pi_3^0$, observe that

$$ \text{SumTolInfinity} = \bigcap_{n \in \mathbb{N}} \bigcup_{j \in \mathbb{N}} \bigcap_{k \ge j} \{w_0 w_1 \dots \in \mathbb{Z}^\omega \mid \sum_{i=0}^{k-1} w_i \ge n\}, $$

where the inner sets $\{w_0 w_1 \dots \in \mathbb{Z}^\omega \mid \sum_{i=0}^{k-1} w_i \ge n\}$ are clopen.

To show that SumTolInfinity is $\Pi_3^0$-hard, we reduce the following $\Pi_3^0$-hard objective [8, Ex. 23.2] to it:

$$ \text{FinOcc} = \{x \in \mathbb{N}^\omega \mid \forall c \in \mathbb{N}, |x|_c \text{ is finite}\}. $$

This objective is the complement of objective InfOcc discussed above. We recall that for a reduction, we need to show a continuous mapping $f: \mathbb{N}^\omega \to \mathbb{Z}^\omega$ such that $f^{-1}(\text{SumTolInfinity}) = \text{FinOcc}$. Such a mapping is defined by:

$$ f(c_0 c_1 \dots) = w_0 w_1 \dots, \quad \text{with } w_i = c_{i+1} - c_i. $$

The function $f$ is continuous, as if $x, x' \in \mathbb{N}^\omega$ are two words with a common prefix of size $k$, then $f(x)$ and $f(x')$ have a common prefix of size $k-1$.

Let us show that $f^{-1}(\text{SumTolInfinity}) = \text{FinOcc}$. Note that $\sum_{i=0}^{k-1} (c_{i+1} - c_i) = c_k - c_0$. If $c_0 c_1 \dots \notin \text{FinOcc}$, then $c_k - c_0$ takes infinitely often a constant value $c \in \mathbb{N}$. Therefore, $\sum_{i=0}^{k-1} (c_{i+1} - c_i) \to +\infty$. Conversely, if $c_0 c_1 \dots \in \text{FinOcc}$, then, for all $c \in \mathbb{N}$, $c_k - c_0 > c$ for all sufficiently large $k$, so $\sum_{i=0}^{k-1} (c_{i+1} - c_i) \to +\infty$.
3 Positionality of SumTolInfinity

To keep this note short, we include only the crucial formal definitions; we refer the reader to [9] for additional context.

In what follows, the word graph stands for a directed graph with edges labelled by elements of C. The set of vertices of a graph G is written V(G), and its edges E(G) ⊆ V(G) × C × V(G).

**Almost-universality.** A tree is a graph with a root $t_0$ such that all vertices admit a unique path from $t_0$. A graph morphism from $G$ to $H$ is a map $f: V(G) \to V(H)$ such that for each edge $v \stackrel{c}{\to} v'$ in $G$, $f(v) \stackrel{c}{\to} f(v')$ is an edge in $H$. We write $G \to H$ if there exists such a morphism. A well-ordered graph is a graph whose vertices are well-ordered by an ordering $\leq$. An ordered graph is monotone if $u \geq v \stackrel{c}{\to} v' \geq u'$ implies $u \stackrel{c}{\to} u'$. A graph satisfies an objective $W$ if the labelling of any infinite path on it belongs to $W$. For a prefix-independent objective $W$ and a cardinal $\kappa$, a graph $U$ is said to be $(\kappa, W)$-almost-universal if

■ $U$ satisfies $W$, and

■ for all trees $T$ of size $< \kappa$ satisfying $W$, there is a vertex $v_0$ such that $T[v_0] \to U$, where $T[v_0]$ is the restriction of $T$ to vertices reachable from $v_0$. We will rely on the following result:

**► Lemma 2 ([9, Theorem 3.2 and Lemma 4.5]).** Let $W$ be a prefix-independent objective. If, for all cardinals $\kappa$, there exists a well-ordered monotone $(\kappa, W)$-almost-universal graph, then $W$ is positional.

Objective SumTolInfinity is prefix-independent. To prove that it is positional, it therefore suffices, for every cardinal $\kappa$, to build a $(\kappa, \text{SumTolInfinity})$-almost-universal graph $U$. In what follows, let $C = \mathbb{Z}$ and let $\kappa$ be a cardinal.

**Definition of $U$.** We will manipulate finite tuples of ordinals. For such a tuple $u$, we write $u_{<i}$ for the restriction of $u$ to its first $i$ coordinates:

$$ (u_0, \dots, u_n)_{<i} = (u_0, \dots, u_{i-1}). $$

We let $|u|$ denote the length of $u$; for instance, $|(0,1)| = 2$. Recall the lexicographic ordering:

$$ u >_{\text{lex}} u' \iff u' \text{ is a prefix of } u \text{ or } \exists i, [u_{<i} = u'_{<i} \text{ and } u_i > u'_i]. $$

Consider the graph $U$ defined over $V(U) = \bigcup_{n<\omega} \kappa^n$ by

$$ E(U) = \{u \stackrel{w}{\to} u' \mid |u| + w \geq |u'| \text{ and } [|u| + w = |u'| \implies u >_{\text{lex}} u'] \}. $$

Intuitively, the length of the tuples in $U$ encodes an underapproximation of the sum of weights in a given path: an edge either tracks precisely the sum of weights (when $|u| + w = |u'|$), or it underestimates it (when $|u| + w > |u'|$). In the former case, there is an additional requirement on $u'$, which is that it decreases for $<_{\text{lex}}$. In the latter case, the tuple can have any value. These rules prevent in particular the existence of cycles with sum of weight 0 in $U$; to go back to the same vertex, some underestimating of the sum of weights is necessary.

The order over $U$ is then defined by

$$ u > u' \iff |u| > |u'| \text{ or } [|u| = |u'| \text{ and } u >_{\text{lex}} u'|]. $$

We raise the reader's attention on the fact that the order over $U$ does not coincide with the lexicographic order: for instance, $(0,0) > (1)$ in $U$.
4 A positional $\Pi_3^0$-complete objective

<figure><img src="image_2.png" /><figcaption>■ **Figure 1** Tree $T$ used in Example 4. Remember that the weights (in black) label edges. This tree satisfies SumTolInfinity (as any infinite path ends with $1^\omega$). The value in red inside each vertex is the value $n(\cdot)$ defined in the proof of Lemma 7. The top vertex $v_0$ is such that $n(v_0) = -1 < 0$, so we can assume it is the vertex given by Claim 7.1. Every path from $v_0$ not reaching another vertex with value $-1$ is tight. Observe that there is exactly one infinite tight path from $v_0$ (staying on the left branch), indeed satisfying the property of Claim 7.2. The tuples in blue next to vertices correspond to the morphism to $U$ built in the proof of Claim 7.3.</figcaption></figure>

**▶ Lemma 3.** The graph $(U, \leq)$ is a well-ordered monotone graph.

*Proof.* It is immediate that the order over $U$ is well-founded and total. Let us check that $U$ is monotone. Let $u \geq v \xrightarrow{w} v' \geq u'$ in $U$. Then, $|u| + w \geq |v| + w \geq |v'| \geq |u'|$. If one of these inequalities is strict, then, $|u| + w > |u'|$. Otherwise, $|u| + w = |u'|$ and $u \geq_{\text{lex}} v >_{\text{lex}} v' \geq_{\text{lex}} u'$. We conclude that $u \xrightarrow{w} u'$.

◀

**▶ Example 4.** Before proving the $(\kappa, \text{SumTolInfinity})$-almost-universality of $U$, we give one example of a morphism of a tree into $U$. We consider the tree $T$ from Figure 1. The blue tuples next to each vertex indicate a possible morphism from $T$ to $U$. The morphism given is exactly the one built by our proof of almost-universality below; we incite the reader to come back to this example as an illustration of the upcoming proof.

▶

**Almost-universality of U.** We now prove the following.

**▶ Theorem 5.** The graph $U$ is $(\kappa, \text{SumTolInfinity})$-almost-universal.

We prove the two conditions for almost-universality in two separate lemmas.

**▶ Lemma 6.** The graph $U$ satisfies SumTolInfinity.

*Proof.* Take an infinite path $u^0 \xrightarrow{w_0} u^1 \xrightarrow{w_1} \dots$ in $U$. For all $i$, let

$$b_i = \begin{cases} 0 & \text{if } |u^i| + w_i = |u^{i+1}|, \\ 1 & \text{otherwise.} \end{cases}$$
For each $i$, we have $|u^i| + w_i \ge |u^{i+1}| + b_i$. Therefore, for all $k$,

$$ \sum_{i=0}^{k-1} w_i \ge |u^k| - |u^0| + \sum_{i=0}^{k-1} b_i \ge \sum_{i=0}^{k-1} b_i - |u^0|. $$

If $\sum_{i=0}^{k-1} b_i$ goes to $+\infty$, then by the above it also holds that $\sum_{i=0}^{k-1} w_i \to +\infty$, as wanted. So we assume otherwise: there is $i_0$ such that for $i \ge i_0$, $b_i = 0$. Then, for all $i \ge i_0$, we have $|u^i| + w_i = |u^{i+1}|$ and thus $u^i >_{\text{lex}} u^{i+1}$; this contradicts the well-foundedness of $<_{\text{lex}}$. ◀

**Lemma 7.** For all trees $T < \kappa$ satisfying SumTolInfinity, there exists a vertex $v_0$ of $T$ such that $T[v_0] \to U$.

**Proof.** Let $T < \kappa$ be a tree satisfying SumTolInfinity. Given a finite path $\pi$, we let $w(\pi)$ denote the sum of the weights appearing on $\pi$. For all $v \in T$, define

$$ n(v) = -\inf\{w(\pi) \mid \pi \text{ is a non-empty finite path from } v\} \in \mathbb{Z} \cup \{+\infty\}. $$

We note that for all edges $v \xrightarrow{w} v'$, it holds that $n(v) + w \ge n(v')$.

**Claim 7.1.** There exists a vertex $v_0$ such that $n(v_0) < 0$.

**Proof.** Assume towards a contradiction that for all vertices $v$, $n(v) \ge 0$. In other words, from all vertices, there is a non-empty path of weight $\le 0$. By concatenating such paths, we get a path whose weight does not converge to $+\infty$, which contradicts the fact that $T$ satisfies SumTolInfinity. ◁

Using the above claim, let $v_0$ be a vertex such that $n(v_0) < 0$. We will construct a mapping $\phi: T[v_0] \to U$. The following claim will be useful for the definition of this morphism. We say that an edge $v \xrightarrow{w} v'$ of $T$ is tight if $n(v) + w = n(v')$, and that a (finite or infinite) path is tight if it is comprised only of tight edges.

**Claim 7.2.** Let $\pi$ be an infinite tight path from $v_0$. For each $k \ge 0$, there are finitely many vertices $v$ on $\pi$ satisfying $n(v) \le k$.

**Proof.** Denote $\pi = v_0 \xrightarrow{w_0} v_1 \xrightarrow{w_1} \dots$; since all edges are tight, we have

$$ n(v_i) = n(v_0) + \sum_{j<i} w_j. $$

Since $\pi$ satisfies SumTolInfinity, $\sum_{j<i} w_j$ converges to $+\infty$; therefore, so does $n(v_i)$. The result follows. ◁

We now define a morphism $\phi: T[v_0] \to U$. First, notice that all vertices $v$ in $T[v_0]$ are such that $n(v) < +\infty$; otherwise, we would also have $n(v_0) = +\infty$. For $v$ in $T[v_0]$, we define the length of the tuple $\phi(v)$ to be $\max\{n(v) + 1, 0\} \in \mathbb{N}$ (in particular, if $n(v) < 0$, then $\phi(v)$ is the empty tuple). For a vertex $v$ in $T[v_0]$ with $n(v) \ge 0$ and $0 \le k \le n(v)$, the $k$-th coordinate of $\phi(v)$ is defined as follows. Informally, we count the number of vertices $v'$ with $n(v') \le k$ on a tight path starting in $v$. Formally, define $T_{v,k}$ to be the graph with vertices

$$ V(T_{v,k}) = \{v' \in V(T) \mid \text{there is a tight path from } v \text{ to } v' \text{ and } n(v') \le k\}, $$

and edges

$$ E(T_{v,k}) = \{v'_1 \xrightarrow{w} v'_2 \mid \begin{array}{l} w \text{ is the weight of a tight path from } v'_1 \text{ to } v'_2 \\ \text{whose inner vertices } v' \text{ satisfy } n(v') > k \end{array} \}. $$
# 6 A positional $\Pi_3^0$-complete objective

The graph $T_{v,k}$ is actually a tree with root $v$ when $k = n(v)$, but is in general a disjoint union of trees.

Claim 7.2 implies that $T_{v,k}$ is well-founded (it does not admit any infinite path). The rank of a vertex in a well-founded disjoint union of trees is an ordinal number defined to be 0 for leaves, and one plus the supremum rank of its successors for non-leaves. The rank of $T_{v,k}$, written rk($T_{v,k}$), is the supremum rank of its vertices (note that it is < $\kappa$).

We set the $k$-th coordinate of $\phi(v)$ to be the rank of $T_{v,k}$, thus

$$ \phi(v) = (\mathrm{rk}(T_{v,0}), \mathrm{rk}(T_{v,1}), \dots, \mathrm{rk}(T_{v,n(v)})). $$

▷ Claim 7.3. The map $\phi: V(T[v_0]) \to V(U)$ defines a morphism from $T[v_0]$ to $U$.

Proof. Consider an edge $v \xrightarrow{w} v'$; we show that $\phi(v) \xrightarrow{w} \phi(v')$ is an edge in $U$.

First, notice that we have in general that $n(v) + w \ge 0$: indeed, $\pi = v \xrightarrow{w} v'$ is a non-empty path from $v$ so, by definition of $n(v)$, $-n(v) \le w$.

If $n(v') < 0$, then

$$ |\phi(v)| + w = \max(n(v) + 1, 0) + w \ge n(v) + 1 + w \ge 1 > 0 = |\phi(v')|, $$

thus $\phi(v) \xrightarrow{w} \phi(v')$ is an edge in $U$.

We now assume in the rest of the proof that $n(v') \ge 0$. We reason according to whether the edge $v \xrightarrow{w} v'$ is tight.

First, assume that edge $v \xrightarrow{w} v'$ is not tight, i.e., that $n(v) + w > n(v')$. Then the argument is similar to the previous one:

$$ |\phi(v)| + w \ge n(v) + 1 + w > n(v') + 1 = |\phi(v')|, $$

where the last equality uses that $n(v') \ge 0$.

Second, assume $v \xrightarrow{w} v'$ is tight, i.e., $n(v) + w = n(v')$. Therefore,

$$ |\phi(v)| + w \ge n(v) + 1 + w = n(v') + 1 = |\phi(v')|, $$

so it suffices to show that $\phi(v) >_{\mathrm{lex}} \phi(v')$.

Let $k \le \min\{n(v), n(v')\}$. As $v'$ is reachable from $v$, $T_{v',k}$ is a subgraph of $T_{v,k}$. Therefore, rk($T_{v,k}$) $\ge$ rk($T_{v',k}$). If $n(v) > n(v')$, we deduce that $\phi(v) >_{\mathrm{lex}} \phi(v')$ ($\phi(v)$ is a longer tuple and starts with values at least as large). If $n(v) \le n(v')$, with $k = n(v)$, since $v$ is a vertex (in fact, the root) of $T_{v,n(v)}$ but not of $T_{v',n(v)}$, we get rk($T_{v,n(v)}$) $>$ rk($T_{v',n(v)}$). We also conclude that $\phi(v) >_{\mathrm{lex}} \phi(v')$, as required. △

This ends the proof of positionality of SumToInfinity.

# References

1. Sougata Bose, Rasmus Ibsen-Jensen, David Purser, Patrick Totzke, and Pierre Vandenhove. The power of counting steps in quantitative games. In CONCUR 2024, volume 311 of LIPIcs, pages 13:1–13:18. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024. doi: 10.4230/LIPICS.CONCUR.2024.13.

2. Patricia Bouyer, Nathanaël Fijalkow, Mickael Randour, and Pierre Vandenhove. How to play optimally for regular objectives? In ICALP 2023, volume 261 of LIPIcs, pages 118:1–118:18. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023. doi:10.4230/LIPICS.ICALP.2023.118.

3. J. Richard Büchi and Lawrence H. Landweber. Definability in the monadic second-order theory of successor. J. Symb. Log., 34(2):166–170, 1969. doi:10.2307/2271090.
4 Antonio Casares and Pierre Ohlmann. Positional ω-regular languages. In *LICS 2024*, pages 21:1–21:14. ACM, 2024. doi:10.1145/3661814.3662087.

5 Thomas Colcombet, Nathanaël Fijalkow, and Florian Horn. Playing safe, ten years later. *Log. Methods Comput. Sci.*, 20(1), 2024. doi:10.46298/LMCS-20(1:10)2024.

6 Nathanaël Fijalkow, Nathalie Bertrand, Patricia Bouyer-Decitre, Romain Brenguier, Arnaud Carayol, John Fearnley, Hugo Gimbert, Florian Horn, Rasmus Ibsen-Jensen, Nicolas Markey, Benjamin Monmege, Petr Novotný, Mickael Randour, Ocan Sankur, Sylvain Schmitz, Olivier Serre, and Mateusz Skomra. *Games on Graphs*. Cambridge University Press, 2024. To Appear.

7 Hugo Gimbert and Wiesław Zielonka. When can you play positionally? In *MFCS 2004*, volume 3153 of *Lecture Notes in Computer Science*, pages 686–697. Springer, 2004. doi:10.1007/978-3-540-28629-5_53.

8 Alexander Kechris. *Classical Descriptive Set Theory*. Graduate Texts in Mathematics. Springer New York, 1995. doi:10.1007/978-1-4612-4190-4.

9 Pierre Ohlmann. Characterizing Positionality in Games of Infinite Duration over Infinite Graphs. *TheoretiCS*, Volume 2, January 2023. doi:10.46298/theoretics.23.3.

10 Pierre Ohlmann and Michał Skrzypczak. Positionality in $\Sigma_2^0$ and a completeness result. In *STACS 2024*, volume 289 of *LIPICS*, pages 54:1–54:18. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024. doi:10.4230/LIPICS.STACS.2024.54.