AFTD Auto-Formalizing Theoretical Domains

Research Blogs

Winning Strategies Compress to Positional Strategies When Hidden Opponent Choices Eventually Cease

medium tier2026-11-13OP-1385reviewed by Codex中文版

Abstract

In prioritized Borel tree games on the infinite binary tree, players navigate positions composed of a tree node and an internal state, producing an infinite sequence of directions and priorities evaluated by Borel winning sets. While games with one or two priorities admit small, state-independent winning strategies, games with three priorities require memory growing with the state space, and whether every such game admits a finite-memory winning strategy remains open (arXiv:2611.10136). In this paper, we consider the question of strategy compression for prioritized Borel games with an arbitrary number of priorities and an arbitrary, possibly infinite, state space. We prove that whenever a player has a winning strategy, with any memory type, and every legal play encounters only finitely many opponent moves with hidden choices—moves where the transition is not uniquely determined by the chosen branch direction and current position—that player also has a memoryless (positional) winning strategy. The result imposes no uniform bound on the number of hidden choices across plays and allows infinitely many public branch choices. The construction selects representative histories by minimizing their hidden-choice records under a well-founded linear order, proves they eventually extend one another along plays without persistent hidden choices, extracts a shadow play consistent with the original strategy, and establishes tail congruence of priorities alongside exact agreement of directions. The main theorem, prioritized_borel_finite_hidden_opponent_choices_positional, has been mechanically formalized and verified in Lean 4.

1. Introduction

Prioritized Borel tree games, introduced in arXiv:2611.10136 (Section 5.2.2), model two-player zero-sum interactions on infinite binary trees equipped with internal state spaces and priority mechanisms. Positions in these games are pairs $(v, q) \in 2^* \times Q$, where $v$ is a node in the binary tree $2^*$ and $q$ is a state in the state space $Q$. At each step, the player controlling the current position selects an outgoing transition that advances the game to a child node $v \cdot d$ for $d \in \{0, 1\}$, emits a priority $p \in \{0, \dots, k-1\}$, and transitions to a new state $q' \in Q$. An infinite play traces an infinite branch $b \in 2^\omega$ through the tree and produces an infinite sequence of priorities. The outcome is determined by the highest priority $p^*$ occurring infinitely often: player Eve wins if and only if the traced branch $b$ belongs to a designated Borel winning set $W_{p^*} \subseteq 2^\omega$, while player Adam wins otherwise.

The complexity of winning strategies in prioritized Borel tree games depends sensitively on the number of priorities $k$. According to arXiv:2611.10136:

  • For games with $k = 1$ priority, memoryless (positional) strategies always suffice for the winning player (Proposition 23).
  • For games with $k = 2$ priorities, winning strategies with a 2-state memory always exist, independently of the size or structure of the state space $Q$ (Proposition 24).
  • For games with $k = 3$ priorities, this uniform simplicity breaks down. Proposition 41 of arXiv:2611.10136 proves that there is no constant bound on the memory size required for winning strategies independent of the number of states $|Q|$.

Conjecture 19 of arXiv:2611.10136 asks whether every prioritized Borel tree game admits a finite-memory winning strategy, with memory bounded by a computable function of the number of states and priorities. The case $k = 3$ remains open. Borel determinacy gives unrestricted winning strategies in the setting of the paper, but finite-memory determinacy is a separate question.

Earlier investigations into the structure of prioritized tree games have established several foundational facts:

In this post, we present a general strategy compression theorem formalized in Lean 4: prioritized_borel_finite_hidden_opponent_choices_positional. We prove that if a player possesses a winning strategy with any memory type in a prioritized Borel game with an arbitrary state type $Q$ and any number of priorities $k$, and every legal play encounters only finitely many opponent moves with hidden choices—moves where the target state or priority is not uniquely fixed by the public direction and current position—then that player also has a memoryless (positional) winning strategy.

Importantly, our theorem allows the opponent to make infinitely many branch choices in the binary tree: only hidden transitions behind a given direction must eventually cease along each play. Furthermore, no uniform bound on the number of hidden choices across different plays is required, and the state space $Q$ may be infinite. Consequently, if a winner lacks a positional strategy, some legal play must contain infinitely many hidden opponent choices. The converse is not asserted.

2. Preliminaries

We formalize prioritized Borel tree games following the Lean definitions in the material.

Definition 1 (BorelGamePlayer). The two players in a game arena are Eve and Adam, formalized as an inductive type with constructors Eve and Adam.

Remark: Eve represents the existential player attempting to satisfy the Borel winning conditions, while Adam is the universal player.

Definition 2 (TreeGameEdge). An edge in a prioritized binary tree arena with state space $Q$ and $k \in \mathbb{N}$ priorities is an element of TreeGameEdge, containing:

  • source_node of type $\text{List Bool}$, representing the current vertex in the binary tree $2^*$;
  • source_state of type $Q$, representing the current internal state;
  • dir of type $\text{Bool}$, representing the child direction in the tree;
  • prio of type $\text{Fin } k$, representing the priority emitted along the transition;
  • target_state of type $Q$, representing the subsequent internal state.

Remark: In Lean, the binary tree alphabet is typed as $\text{Bool}$, where true and false represent the two branch directions. The priority prio belongs to $\text{Fin } k$, so priorities are indexed as $\{0, 1, \dots, k-1\}$.

Definition 3 (PrioritizedBorelGame). A prioritized Borel game with state space $Q$ and $k$ priorities is a structure PrioritizedBorelGame comprising:

  • owner of type $\text{List Bool} \times Q \to \text{BorelGamePlayer}$, assigning each position to a player;
  • init_state of type $Q$, the initial internal state at the root node $[]$;
  • edges, a set of edges of type TreeGameEdge;
  • edges_outgoing, asserting that every position $(v, q)$ has at least one outgoing edge in edges with source node $v$ and source state $q$;
  • winning_sets, assigning to each priority $i \in \text{Fin } k$ a target branch set of type $\text{Set } (\mathbb{N} \to \text{Bool})$;
  • winning_measurable, asserting that each winning set is Borel measurable.

Remark: The condition edges_outgoing ensures the game is non-terminating and no deadlock can occur. Winning sets are subsets of Cantor space $\mathbb{N} \to \text{Bool}$, each required to be measurable under the standard Borel product $\sigma$-algebra.

Definition 4 (FiniteMemoryStrategy). A strategy with memory type $M$ for player $pl$ in game $G$ is a structure FiniteMemoryStrategy comprising:

  • init_mem of type $M$, the initial memory state;
  • update of type $M \to \text{TreeGameEdge} \to M$, updating memory upon observing a transition;
  • choice of type $M \to \text{List Bool} \to Q \to \text{TreeGameEdge}$, selecting an outgoing transition;
  • choice_edge, asserting that for any memory $m$ and position $(v, q)$ owned by $pl$, choice produces a legal outgoing edge in edges with source node $v$ and source state $q$.

Remark: The memory type $M$ is arbitrary in this definition. A strategy is positional (memoryless) when $M = \text{Unit}$. The choice function is only required to return a legal outgoing edge at positions owned by player $pl$.

Definition 5 (PrioritizedBorelStrategyWins). An infinite play is a sequence $\pi : \mathbb{N} \to \text{TreeGameEdge}$. A play $\pi$ is legal and consistent with strategy $\sigma$ if $\pi(n) \in G.\text{edges}$ for all $n$, $(\pi(0)).\text{source\_node} = []$, $(\pi(0)).\text{source\_state} = G.\text{init\_state}$, $(\pi(n+1)).\text{source\_node} = (\pi(n)).\text{source\_node} ++ [(\pi(n)).\text{dir}]$, $(\pi(n+1)).\text{source\_state} = (\pi(n)).\text{target\_state}$, and there exists a memory sequence $\text{mem} : \mathbb{N} \to M$ starting at $\sigma.\text{init\_mem}$, updated by $\sigma.\text{update}$, such that $\pi(n) = \sigma.\text{choice}(\text{mem}(n), (\pi(n)).\text{source\_node}, (\pi(n)).\text{source\_state})$ whenever $pl$ owns the position. The strategy $\sigma$ satisfies PrioritizedBorelStrategyWins for Eve if every consistent legal play satisfies: $$ \exists p \in \text{Fin } k,\ (\exists^\infty n,\ (\pi(n)).\text{prio} = p) \land (\forall q > p,\ \neg (\exists^\infty n,\ (\pi(n)).\text{prio} = q)) \land (n \mapsto (\pi(n)).\text{dir}) \in G.\text{winning\_sets}(p). $$ The strategy $\sigma$ satisfies PrioritizedBorelStrategyWins for Adam if no consistent legal play satisfies Eve's winning condition.

Remark: The winning condition evaluates parity-like recurrence: the highest priority occurring infinitely often determines which Borel set must contain the infinite branch $(n \mapsto (\pi(n)).\text{dir})$. In Lean, recurrence is defined using the filter quantifier along the filter of cofinite sets on the natural numbers.

Definition 6 (PrioritizedBorelStrategyHistory). The inductive relation PrioritizedBorelStrategyHistory characterizes finite execution traces $h : \text{List } (\text{Bool} \times Q \times \text{Fin } k)$ consistent with $\sigma$:

  • root: The empty history $[]$ reaches memory $\sigma.\text{init\_mem}$, node $[]$, and state $G.\text{init\_state}$;
  • step: Extending history $h$ by edge $e$ appends $(e.\text{dir}, e.\text{target\_state}, e.\text{prio})$ to $h$, updates memory to $\sigma.\text{update}(m, e)$, advances the node to $v ++ [e.\text{dir}]$, updates the state to $e.\text{target\_state}$, and requires $e = \sigma.\text{choice}(m, v, q)$ whenever $pl$ owns $(v, q)$.

Remark: The step signature encodes direction, target state, and priority. The tree node and internal state are verified at each step.

Definition 7 (TotalPreorder and LinearOrder.toTotalPreorder). A total preorder TotalPreorder is a preorder whose comparison relation is total: for all $a$ and $b$, either $a \le b$ or $b \le a$. Every linear order induces a total preorder via LinearOrder.toTotalPreorder.

Remark: A total preorder does not require antisymmetry, allowing distinct elements to be mutually bounded. In our construction, a well-founded linear order is placed on lists of signatures to select unique representative histories.

3. Main result

The main result is the strategy compression theorem prioritized_borel_finite_hidden_opponent_choices_positional.

Theorem (Positional Strategy from Eventual Unique Hidden Opponent Choices). Let $Q$ be any type and $k \in \mathbb{N}$. Let $G$ be a prioritized Borel game PrioritizedBorelGame, $pl \in \text{BorelGamePlayer}$, and $\sigma$ a strategy FiniteMemoryStrategy with arbitrary memory type $M$, such that PrioritizedBorelStrategyWins holds for $G$, $pl$, and $\sigma$. Suppose that along every legal play $\pi : \mathbb{N} \to \text{TreeGameEdge}$ from the initial position $([], G.\text{init\_state})$, all but finitely many opponent moves have no hidden choices behind the direction: $$ \exists N \in \mathbb{N},\ \forall n \ge N,\ G.\text{owner}((\pi(n)).\text{source\_node}, (\pi(n)).\text{source\_state}) = pl \quad \lor \quad (\forall e \in G.\text{edges},\ e.\text{source\_node} = (\pi(n)).\text{source\_node} \land e.\text{source\_state} = (\pi(n)).\text{source\_state} \land e.\text{dir} = (\pi(n)).\text{dir} \implies e = \pi(n)). $$ Then player $pl$ has a positional (memoryless) winning strategy $\tau$ of type FiniteMemoryStrategy with memory type $\text{Unit}$ such that: $$ \text{PrioritizedBorelStrategyWins } G\ pl\ \tau. $$

In the Lean statement, prioritized_borel_finite_hidden_opponent_choices_positional universally quantifies over the arbitrary state type $Q$, the priority bound $k$, the game $G$, the player $pl$, the memory type $M$, and the winning strategy $\sigma$, assumes the hypothesis that along every legal play all but finitely many opponent moves have no hidden choices behind the direction, and concludes the existential statement that there exists a winning strategy $\tau$ for $pl$ with memory type $\text{Unit}$, without any finiteness hypothesis on $Q$ or restriction on $k$.

Several related theorems in the development establish additional properties of memory and determinacy in prioritized tree games:

  • Deterministic Opponent Memoryless Determinacy (prioritized_borel_deterministic_opponent_memoryless): If every position controlled by Adam has at most one legal outgoing edge, then one of the players has a winning strategy using a single memory state, without requiring finiteness of $Q$ or general Borel determinacy.
  • Eventually Visible Determined Games (prioritized_borel_eventually_visible_determined_positional): A determined prioritized tree game has a memoryless winner if, along every legal play, all but finitely many moves are uniquely determined by the current position and public branch direction.
  • Reverse-Deterministic Uniqueness (prioritized_borel_reverse_state_histories_unique): If a tree-game edge is reverse-deterministic in the state at each fixed parent node and child direction, then at most one state history reaches any fixed node and final state.
  • History Replay and Injectivity (prioritized_borel_record_replay and prioritized_borel_record_injective): Compatible finite histories can be uniquely reconstructed from their length and the sequence of choices at opponent-controlled branching positions, proving that histories sharing these records are identical.
  • Edge Cardinality Bound (prioritized_borel_outgoing_edge_card_bound): At any fixed position in a finite-state game with $k$ priorities, there are at most $2k |Q|$ legal outgoing edges.
  • Eventual Hidden Shadow (prioritized_borel_eventual_hidden_shadow): Under its compatibility, visibility, and monotonicity hypotheses, the hidden-choice records stabilize and the histories eventually extend one another by the actual edge.
  • Tail Congruence of Payoffs (prioritized_borel_payoff_tail_congr): Two prioritized-game plays have identical payoffs whenever their directions agree everywhere and their priorities agree eventually.
Theorem prioritized_borel_finite_hidden_opponent_choices_positional (Lean 4, verified)
theorem prioritized_borel_finite_hidden_opponent_choices_positional {Q : Type} {k : ℕ} (G : PrioritizedBorelGame Q k) (pl : BorelGamePlayer) (M : Type) (σ : FiniteMemoryStrategy G pl M) (hwin : PrioritizedBorelStrategyWins G pl σ) (hfinite : ∀ π : ℕ → TreeGameEdge Q k, (∀ n, π n ∈ G.edges) → (π 0).source_node = [] ∧ (π 0).source_state = G.init_state → (∀ n, (π (n+1)).source_node = (π n).source_node ++ [(π n).dir] ∧ (π (n+1)).source_state = (π n).target_state) → ∃ N, ∀ n ≥ N, G.owner ((π n).source_node, (π n).source_state) = pl ∨ ∀ e ∈ G.edges, e.source_node = (π n).source_node → e.source_state = (π n).source_state → e.dir = (π n).dir → e = π n) : ∃ τ : FiniteMemoryStrategy G pl Unit, PrioritizedBorelStrategyWins G pl τ

4. Proof

Proof Idea: The strategy $\sigma$ uses memory $M$ updated along the play to choose outgoing edges. To construct a memoryless strategy $\tau$, player $pl$ must select an edge at any position $(v, q)$ without reference to the past play. We define canonical representative histories for reachable positions. We fix a well-founded linear order on lists of edge signatures of type $\text{Bool} \times Q \times \text{Fin } k$. A history has a hidden-choice record consisting of the signatures at opponent moves where the public direction does not uniquely determine the edge. For each reachable position $(v, q)$, choose a consistent history whose hidden-choice record is minimal under this order. The positional strategy $\tau$ then chooses the move that $\sigma$ would make after this canonical history.

When a play $\pi$ is played against $\tau$, the canonical representative history at step $n$ does not necessarily match the actual history of $\pi$. However, because hidden opponent choices cease after step $N$, there is a step $K$ after which each representative history extends its predecessor by the actual edge signature. From this nested sequence we extract an infinite sequence of edge signatures $f$. This defines an infinite shadow play $\rho$ that is fully consistent with the original strategy $\sigma$. Since $\sigma$ is winning, $pl$ wins $\rho$. Because directions agree everywhere and priorities agree on the tail $n \ge K$, prioritized_borel_payoff_tail_congr guarantees that $pl$ wins $\pi$.

Supporting Lemmas:

Lemma 1 (Reachability and Specification of Canonical Representatives). Let $\pi$ be a play consistent with the canonical positional strategy $\tau$ constructed from $\sigma$. Then for all $n \in \mathbb{N}$, the position $((\pi(n)).\text{source\_node}, (\pi(n)).\text{source\_state})$ is reachable under $\sigma$, and there exists a memory state $m \in M$ such that the canonical representative history at step $n$ satisfies PrioritizedBorelStrategyHistory with memory $m$, node $(\pi(n)).\text{source\_node}$, and state $(\pi(n)).\text{source\_state}$. Proof: Reachability follows by induction on $n$: at step $0$, the root position is reachable by the root constructor of PrioritizedBorelStrategyHistory. For the inductive step, at a position owned by $pl$, $\tau$ chooses the edge prescribed by $\sigma$ from the representative history. At an opponent position, any legal edge extends that history consistently. The specification of the representative function then yields a memory state $m$ certifying the history.

Lemma 2 (Length and Visible Projection of Canonical Histories). Let $h$ be a history satisfying PrioritizedBorelStrategyHistory with node $v$. Then the list of directions obtained by projecting the first component of $h$ equals $v$. Furthermore, for the play $\pi$, $(\pi(n)).\text{source\_node}$ has length $n$ and consists of the sequence of directions of $\pi$ prior to step $n$. Consequently, the length of the representative history at step $n$ is $n$, and its visible direction projection equals the prefix of actual directions of $\pi$ of length $n$. Proof: By induction on the inductive definition of PrioritizedBorelStrategyHistory, each step appends $e.\text{dir}$ to the node and $(e.\text{dir}, e.\text{target\_state}, e.\text{prio})$ to the history. For the play $\pi$, node concatenation $(\pi(n+1)).\text{source\_node} = (\pi(n)).\text{source\_node} ++ [(\pi(n)).\text{dir}]$ implies that $(\pi(n)).\text{source\_node}$ is the list of first $n$ directions. Equating lengths and projections yields the claims.

Lemma 3 (Stabilization of Representative Histories). Let $\pi$ be a legal play following $\tau$. Suppose there exists $N$ such that for all $n \ge N$, either $pl$ owns the position or the opponent move is uniquely determined by direction: $$ \forall n \ge N,\ G.\text{owner}((\pi(n)).\text{source\_node}, (\pi(n)).\text{source\_state}) = pl \lor (\forall e \in G.\text{edges},\ e.\text{source\_node} = (\pi(n)).\text{source\_node} \to e.\text{source\_state} = (\pi(n)).\text{source\_state} \to e.\text{dir} = (\pi(n)).\text{dir} \to e = \pi(n)). $$ Then there exists $K \ge N$ such that the canonical representative histories stabilize: for all $n \ge K$, the representative history at step $n+1$ is the representative history at step $n$ followed by the actual edge signature at step $n$. Proof: At a reachable position, the representative history can be extended by the actual edge consistently with $\sigma$: at a $pl$ position this is the definition of $\tau$, and at an opponent position any legal edge is allowed. After $N$ this extension adds nothing to the hidden-choice record. The next representative minimizes the record at the next position, so its record is at most the previous one. A nonincreasing sequence in a well-founded linear order is eventually constant. Compatible histories with the same visible directions and hidden-choice record agree, since the player's policy and every non-hidden opponent edge are determined. Applying this uniqueness to the next representative and the extended previous representative gives the claimed equality. This is the role of prioritized_borel_eventual_hidden_shadow.

Lemma 4 (Visible Shadow Sequence Extraction). Let $\text{histories} : \mathbb{N} \to \text{List } (\text{Bool} \times Q \times \text{Fin } k)$ and $\text{actual} : \mathbb{N} \to (\text{Bool} \times Q \times \text{Fin } k)$ satisfy: 1. For all $n$, the length of $\text{histories}(n)$ is $n$; 2. For all $n$, the direction projection of $\text{histories}(n)$ matches the first $n$ directions of $\text{actual}$; 3. For all $n \ge K$, $\text{histories}(n+1)=\text{histories}(n) ++ [\text{actual}(n)]$. Then there exists an infinite sequence $f : \mathbb{N} \to (\text{Bool} \times Q \times \text{Fin } k)$ such that: - For all $n \ge K$, the prefix of $f$ of length $n$ is a prefix of $\text{histories}(n)$; - For all $n \ge K$, $f(n) = \text{actual}(n)$; - For all $n \in \mathbb{N}$, the direction of $f(n)$ equals the direction of $\text{actual}(n)$. Proof: Define $f$ using the entries of $\text{histories}(K)$ before $K$ and $\text{actual}(n)$ from $K$ onward. The successive extension condition proves that its prefix of length $n$ equals $\text{histories}(n)$ for each $n \ge K$. The direction agreement follows from condition 2 before $K$ and from the definition thereafter.

Lemma 5 (Shadow Play Legality and Strategy Compatibility). Let $f : \mathbb{N} \to (\text{Bool} \times Q \times \text{Fin } k)$ be the sequence from Lemma 4. Then every finite prefix of $f$ is a valid strategy history for $\sigma$ satisfying PrioritizedBorelStrategyHistory, and the sequence of edges $\rho$ constructed from $f$ defines a legal infinite play consistent with $\sigma$ from $([], G.\text{init\_state})$. Proof: For any length $m$, choosing $n = \max(m, K)$ ensures that the prefix of $f$ of length $m$ is a prefix of $\text{histories}(n)$. Since $\text{histories}(n)$ satisfies PrioritizedBorelStrategyHistory, so does every prefix. The infinite limit of these consistent finite prefixes defines a legal play $\rho$ where memory updates and choices match $\sigma$ at every step.

Lemma 6 (prioritized_borel_payoff_tail_congr). Let $\pi, \rho : \mathbb{N} \to \text{TreeGameEdge}$ be two legal plays in $G$. Suppose: 1. For all $n \in \mathbb{N}$, $(\pi(n)).\text{dir} = (\rho(n)).\text{dir}$; 2. There exists $K$ such that for all $n \ge K$, $(\pi(n)).\text{prio} = (\rho(n)).\text{prio}$. Then $\pi$ satisfies Eve's winning condition if and only if $\rho$ satisfies Eve's winning condition. Proof: Since $(\pi(n)).\text{dir} = (\rho(n)).\text{dir}$ for all $n$, both plays trace the identical infinite branch $b \in 2^\omega$. Since $(\pi(n)).\text{prio} = (\rho(n)).\text{prio}$ for all $n \ge K$, the tails of the priority sequences are identical. For each priority $p \in \text{Fin } k$, the predicate asserting that $p$ occurs infinitely often depends only on the tail of the sequence, which is invariant under finite prefixes. Hence $\pi$ and $\rho$ have identical sets of recurrent priorities and identical maximal recurrent priorities $p^*$. Since $b \in G.\text{winning\_sets}(p^*)$ is evaluated on the same branch and priority, the winning condition holds for $\pi$ if and only if it holds for $\rho$. Settled by prioritized_borel_payoff_tail_congr.

Detailed Combination of the Lemmas: We now follow the Lean proof of prioritized_borel_finite_hidden_opponent_choices_positional step by step.

1. Ordering and Positional Strategy: We obtain a well-founded linear order on lists of signatures $\text{List } (\text{Bool} \times Q \times \text{Fin } k)$. We minimize the hidden-choice record among consistent histories reaching each reachable position, select a history with that record, and define the positional strategy $\tau$ from it. Its memory type is $\text{Unit}$.

2. Assumptions on Play $\pi$: Let $\pi : \mathbb{N} \to \text{TreeGameEdge}$ be a play satisfying legality, initial conditions, transition relations, and memory consistency with $\tau$. Since $\tau$ uses memory type $\text{Unit}$, the memory sequence satisfies $\text{mem}(n) = ()$ for all $n$. Hence the strategy choice condition simplifies to: $$ \forall n,\ G.\text{owner}((\pi(n)).\text{source\_node}, (\pi(n)).\text{source\_state}) = pl \implies \pi(n) = \tau.\text{choice } ()\ (\pi(n)).\text{source\_node}\ (\pi(n)).\text{source\_state}. $$ We record this property as the condition that $\pi$ follows $\tau$'s choices.

3. Stabilization of Representatives: By the theorem hypothesis, there exists $N$ such that opponent hidden choices cease for $n \ge N$. Applying Lemma 3 with the choice-following condition, $N$, and the no-hidden-choice hypothesis, we obtain $K \ge N$ such that each subsequent representative is the preceding one extended by the actual edge signature.

4. Representative Histories and Lengths: We define $\text{histories}(n)$ to be the canonical representative history reaching the position at step $n$, and $\text{actual}(n)$ to be the signature of the edge $\pi(n)$. By Lemma 1, each $\text{histories}(n)$ is reachable and satisfies PrioritizedBorelStrategyHistory. By Lemma 2, the node projection of $\text{histories}(n)$ equals $(\pi(n)).\text{source\_node}$. Since $\pi$ concatenates directions, the length of $\text{histories}(n)$ is $n$, and its visible direction projection matches $\text{actual}$.

5. Shadow Play Construction: Applying Lemma 4 with the lengths, direction projections, and stabilization at $K$, we obtain an infinite sequence of signatures $f$ satisfying the prefix, tail, and direction matching conditions. By Lemma 5, $f$ defines a legal play $\rho$ consistent with $\sigma$.

6. Payoff Congruence and Conclusion: Since $\sigma$ is winning for $pl$, player $pl$ wins $\rho$. We verify the two conditions of Lemma 6: - For direction agreement: for all $n$, $(\pi(n)).\text{dir} = (\rho(n)).\text{dir}$ holds because the directions of $f$ match $\text{actual}$ everywhere. - For priority agreement: $(\pi(n)).\text{prio} = (\rho(n)).\text{prio}$ holds for all $n \ge K$ because $f(n) = \text{actual}(n)$ for all $n \ge K$. By Lemma 6 (prioritized_borel_payoff_tail_congr), Eve wins $\pi$ if and only if Eve wins $\rho$. We conclude by cases on $pl \in \text{BorelGamePlayer}$: - If $pl = \text{Eve}$, the equivalence shows Eve wins $\pi$. - If $pl = \text{Adam}$, Eve does not win $\rho$, so the equivalence shows Eve does not win $\pi$, meaning Adam wins $\pi$. In both cases, $pl$ wins $\pi$. Therefore, $\tau$ is a winning positional strategy for $pl$, completing the proof.

5. Discussion

Scope and Boundaries: The theorem prioritized_borel_finite_hidden_opponent_choices_positional establishes that any winning strategy represented by a memory type can be compressed to a positional strategy whenever hidden opponent transitions eventually cease along every legal play. It is important to clarify what this theorem does not cover:

  • Persistent Hidden Choices: The theorem crucially requires that on every legal play, all but finitely many opponent transitions are uniquely determined by their public branch direction and current position. If the opponent can repeatedly make hidden non-deterministic choices—for instance, choosing between multiple target states or priorities that share the same branch direction $d \in \{0, 1\}$—the stabilization argument does not apply; the theorem does not decide whether a positional winner exists.
  • Determinacy: The theorem assumes the existence of an initial winning strategy $\sigma$, whose memory type need not be finite. It does not establish the existence of winning strategies from scratch (game determinacy), which requires Borel determinacy arguments.
  • Arbitrary State Spaces: Although Conjecture 19 of arXiv:2611.10136 is formulated for finite state spaces $Q$, our result makes no finiteness or countability assumptions on $Q$. The theorem holds for any type $Q$ and any number of priorities $k \in \mathbb{N}$.

Relation to Conjecture 19: Conjecture 19 of arXiv:2611.10136 asks for finite-memory winners and computable memory bounds in general prioritized Borel games. Section 5.2.2 notes that the case of three priorities remains open. The paper establishes a stark transition: 1. Games with $k = 1$ priority admit memoryless winning strategies (Proposition 23). 2. Games with $k = 2$ priorities admit winning strategies with 2 memory states, independent of $|Q|$ (Proposition 24). 3. Games with $k = 3$ priorities require memory that grows with $|Q|$ (Proposition 41).

Our theorem provides structural insight into the memory requirement identified in Proposition 41. It shows that the absence of a positional winning strategy entails the existence of a legal play with infinitely many hidden opponent choices. Under the stated eventual-uniqueness hypothesis, any winning strategy can be compressed to a positional strategy with memory type $\text{Unit}$, regardless of whether $k = 3$ or larger, and regardless of the cardinality of $Q$.

Open Questions: The open problem entry and arXiv:2611.10136 suggest several natural open questions: - Does every prioritized Borel tree game with $k = 3$ priorities admit a finite-memory winning strategy when the opponent makes infinitely many hidden choices? - Is the memory size required for $k = 3$ games bounded by a computable function of $|Q|$ in the general case where hidden choices persist? - Can strategy compression be extended to games with persistent hidden choices under additional restrictions, such as reverse-deterministic state structures (prioritized_borel_reverse_state_histories_unique)?

Why it is research-level

  • Shows that a winner has a positional strategy whenever every legal play has finitely many opponent choices hidden behind the public direction, without a uniform bound on those choices or any restriction on the state space

Lean declarations

Each one elaborated against Mathlib, and #print axioms returned nothing outside Classical.choice · Quot.sound · propext.

References

  1. arXiv:2611.10136 — Automata for MSO over Infinite Trees with Quantification over Borel Sets of Branches

Drafted by gemini-3.8-flash from the knowledgebase, checked against it, and reviewed by Codex. Only the Lean is verified; the prose is a reading of it.