💻 computer science

A positional $\mathbf{\Pi}^0_3$ -complete objective

This paper introduces the first known positional game objective that is $\mathbf{\Pi}^0_3$ -complete in the Borel hierarchy, specifically a qualitative variant of the total-payoff objective, thereby demonstrating that positional strategies suffice for winning over arbitrary game graphs despite the objective's high complexity.

Original authors: Antonio Casares, Pierre Ohlmann, Pierre Vandenhove

Published 2026-08-05

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Antonio Casares, Pierre Ohlmann, Pierre Vandenhove

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a world where two players, let's call them Eve and Adam, are locked in an endless game of tag played on a giant, infinite map. They take turns moving a token along the paths of this map, leaving a trail of colored stickers behind them. The goal isn't just to run forever; it's to create a specific, infinite pattern of stickers that satisfies a secret rule. If the pattern matches the rule, Eve wins. If it doesn't, Adam wins. This isn't just a parlor trick; it's a fundamental way computer scientists study how software behaves over time, checking if a program will eventually crash, get stuck, or run perfectly forever.

The big question in this field is about "memory." Can a player win by just looking at where they are right now and making a decision, or do they need to remember every single step they've taken since the game began? A strategy that only looks at the current spot is called "positional" (or memoryless). It's the simplest, most elegant way to play. For a long time, scientists knew that for many complex rules, you could win with just a positional strategy. However, there was a weird gap in the map of knowledge. All the known rules that allowed for such simple strategies belonged to a specific "easy" category of complexity. But there was a much harder category of rules, known as $\Pi^0_3$ , where everyone assumed you needed a massive memory to win. The burning question was: Is there a rule in this super-hard category that still lets you win with zero memory?

This paper says, "Yes, there is." The authors, Antonio Casares, Pierre Ohlmann, and Pierre Vandenhove, have discovered a specific game rule called SumToInfinity that is incredibly complex (mathematically speaking, it's $\Pi^0_3$ -complete) but surprisingly simple to play. They proved that even though the rule is hard to describe, a player can always win it by just looking at their current location, no matter how huge or weird the game map is. They didn't just guess this; they built a rigorous mathematical proof to show it's true.

The Game of Infinite Sums

To understand their discovery, let's look at the game they invented. Imagine the map is made of cities connected by roads. Every road has a number on it, like a score: $+5$ , $-2$, or $+100$ . As the token moves, you add up these numbers. The rule for SumToInfinity is simple: Eve wins if, as the game goes on forever, the total sum of the numbers keeps getting bigger and bigger, heading toward positive infinity. If the sum gets stuck, goes down, or bounces around without growing, Adam wins.

Before this paper, we knew that if the map was small and finite, you could win this game with a simple strategy. But if the map was infinite (which is allowed in these theoretical games), everyone thought you'd need a super-computer brain to remember the history of the game to know which way to turn. The authors showed that this isn't true. Even on an infinite map, Eve can win by just asking, "Where am I?" and picking the right road.

The Magic Map (Universal Graphs)

How did they prove this? They didn't just try to find a strategy; they built a "magic map" to prove one exists. Think of it like this: Imagine you want to prove that a specific type of maze is solvable. Instead of solving every possible maze, you build one giant, perfect "master maze" that contains the solution to every smaller maze of that type. If you can show that any small maze can be folded into this master maze without breaking the rules, then the master maze holds the secret to winning them all.

The authors built this master map, which they call a "graph." It's a bit abstract. The "cities" in this map aren't just dots; they are lists of numbers (tuples) that get longer and longer. The rules for moving between these cities are strict. To move from one city to another, you have to follow a specific pattern:

The length of your list of numbers must change in a way that matches the score on the road you took.
If the score on the road exactly matches the change in length, the new list of numbers must be "smaller" than the old one in a very specific, strict ordering (like a dictionary order).

This structure is the key. It's designed so that if you try to loop around in a circle without the total score going up, the rules of the map force you to break the loop. You can't stay in the same place forever unless your score is rising. Because the map is built this way, it acts as a universal guide. If a game map satisfies the "SumToInfinity" rule, it can be mapped onto this master map. And because the master map is so well-organized, it turns out that a simple, memoryless strategy works perfectly on it. Since any winning game can be mapped to this master map, the simple strategy works there too.

Why This Matters

This finding is a big deal because it fills a hole in our understanding of complexity. For years, we thought that if a game rule was in the "hard" $\Pi^0_3$ category, it had to be complex to play. The authors showed that complexity in the rule doesn't always mean complexity in the strategy. They found a rule that is mathematically "hard" to define but "easy" to play.

It's like finding a lock that looks terrifyingly complicated, with thousands of tumblers and weird shapes, but turns out to have a single, simple key that works every time. This changes how we think about the relationship between how hard a problem is to describe and how hard it is to solve. The paper proves this isn't just a lucky guess for one specific game; it's a solid mathematical fact. They didn't simulate it on a computer or suggest it might be true; they proved it with logic that holds up for any size of game map, no matter how infinite.

So, the next time you're playing a game where the goal is to keep your score climbing forever, remember: even if the rules seem impossibly complex, there might be a simple, memoryless way to win, hiding in plain sight. The authors found that way, and they showed us exactly how it works.

Technical Summary: A Positional $\Pi^0_3$ -Complete Objective

Problem Statement
The paper investigates zero-sum, turn-based, infinite-duration games played on graphs (potentially of arbitrary cardinality). The central question concerns the complexity of positional strategies (strategies that depend only on the current vertex, not the history of the play) for specific game objectives.

While it is well-established that many objectives, including $\omega$ -regular ones, are positional, these known objectives generally reside within the class $\Sigma^0_3$ of the Borel hierarchy. A significant gap existed in the literature regarding the existence of a positional objective that is complete for the class $\Pi^0_3$ . Specifically, while the complement of the "InfOcc" objective (where some number appears infinitely often) is $\Pi^0_3$ -complete, it is known not to be positional. The authors address the open question: Does there exist a positional objective that does not belong to $\Sigma^0_3$ ?

Methodology
To answer this, the authors analyze the objective SumToInfinity, defined over the alphabet $\mathbb{Z}$ as the set of infinite words $w_0w_1\dots$ such that the limit of the partial sums of weights diverges to positive infinity:
$\text{SumToInfinity} = \left\{ w \in \mathbb{Z}^\omega \mid \lim_{k \to \infty} \sum_{i=0}^{k-1} w_i = +\infty \right\}$

The proof of positionality relies on the theory of universal graphs, specifically the framework established in [10]. The authors utilize the following logical reduction:

Prefix Independence: They observe that SumToInfinity is prefix-independent.
Universal Graph Construction: They invoke a theorem (Lemma 2, derived from [10]) stating that if a prefix-independent objective admits a well-ordered monotone $(\kappa, W)$ -almost-universal graph for every cardinal $\kappa$ , then the objective is positional.
Graph Construction: The core of the methodology involves constructing a specific graph $U$ $U$ for any cardinal $\kappa$ $κ$ .
- Vertices: The vertices of $U$ are finite tuples of ordinals below $\kappa$ (elements of $\bigcup_{n<\omega} \kappa^n$ ).
- Edges: An edge $u \xrightarrow{w} u'$ exists if the weight $w \in \mathbb{Z}$ satisfies specific constraints relating the lengths of the tuples ( $|u| + w \ge |u'|$ ) and, in the case of equality, requires a strict decrease in the lexicographic order ( $u >_{lex} u'$ ).
- Ordering: The graph is equipped with a well-order $\le$ defined by tuple length first, then lexicographic order. This ordering is crucial for ensuring monotonicity.

Key Contributions and Results

$\Pi^0_3$ -Completeness:
The authors prove that SumToInfinity is $\Pi^0_3$ -complete.
- Membership: They show the objective can be expressed as a countable intersection of countable unions of clopen sets, placing it in $\Pi^0_3$ .
- Hardness: They provide a continuous reduction from the known $\Pi^0_3$ -hard objective FinOcc (words where every number appears finitely often) to SumToInfinity. The reduction maps a sequence of natural numbers to a sequence of differences, transforming the condition of "finite occurrences" into "divergence to $+\infty$ ."
Positionality:
The primary contribution is the proof that SumToInfinity is positional.
- Graph Satisfaction: They prove that the constructed graph $U$ satisfies the SumToInfinity objective (Lemma 6). Any infinite path in $U$ must have partial sums diverging to $+\infty$ because cycles with zero or negative weight are structurally impossible due to the lexicographic decrease requirement on "precise" steps.
- Almost-Universality: They prove that for any tree $T$ $T$ of size $<\kappa$ $< κ$ satisfying SumToInfinity, there exists a vertex $v_0$ $v_{0}$ and a morphism from the subtree $T[v_0]$ $T [v_{0}]$ into $U$ $U$ (Lemma 7).
  - The morphism construction maps a vertex $v$ in the tree to a tuple in $U$ . The length of the tuple corresponds to the accumulated weight from a specific root $v_0$ (guaranteed to have positive weight for all finite paths by Claim 7.1).
  - The ordinal coordinates of the tuple are defined using the rank of well-founded forests of descendants with bounded accumulated weight. This encoding ensures that the morphism preserves the edge structure and the lexicographic ordering required by $U$ .

Significance and Claims
The paper claims to provide the first known example of a positional objective that is $\Pi^0_3$ -complete. This result is significant because:

It resolves the question of whether the class of positional objectives is strictly contained within $\Sigma^0_3$ . The answer is negative; positional objectives exist at higher levels of the Borel hierarchy.
It fills a gap in the understanding of quantitative objectives. While total-payoff objectives are known to be positional over finite arenas, they generally fail to be positional over infinite arenas. SumToInfinity is a qualitative variant of the total-payoff objective that retains positionality even over the most general class of arenas (arbitrary cardinality).
The work demonstrates that the strategy complexity for this objective is remarkably low (positional) despite its high descriptive complexity ( $\Pi^0_3$ -complete).

The authors conclude by noting that a natural open question remains: whether every level of the Borel hierarchy admits a complete objective that is positional.

The Game of Infinite Sums

The Magic Map (Universal Graphs)

Why This Matters

Technical Summary: A Positional Π30\Pi^0_3Π30​-Complete Objective

More like this

Technical Summary: A Positional $\Pi^0_3$ -Complete Objective