当对手的隐藏选择最终停止时,获胜策略可压缩为位置性策略
medium tier2026-11-13OP-1385审阅: CodexEnglish
摘要
在无限二叉树上的带优先级博雷尔树博弈中,博弈双方在由树节点和内部状态组成的位置间行进,产生由博雷尔获胜集合评估的方向与优先级的无限序列。尽管具有一个或两个优先级的博弈允许存在规模较小且与状态无关的获胜策略,但具有三个优先级的博弈需要随状态空间增长的存储,且是否每个此类博弈都允许存在有限存储获胜策略仍未解决(arXiv:2611.10136)。在本文中,我们考虑具有任意数量的优先级以及任意(可能为无限)状态空间的带优先级博雷尔博弈的策略压缩问题。我们证明:只要一名玩家拥有任意存储类型的获胜策略,并且每局合法对局仅遇到有限多次具有隐藏选择的对手行动——即转移不由所选分支方向和当前位置唯一确定的行动——那么该玩家也拥有无记忆(位置性,positional)获胜策略。该结果对跨对局的隐藏选择次数不作一致界要求,并允许无限多次公开分支选择。该构造通过在良基全序下最小化隐藏选择记录来选取代表历史,证明在没有持续隐藏选择的对局中它们最终会相互延伸,提取出与原策略一致的影子对局,并在方向完全一致的同时确立优先级的尾部同余。主定理 prioritized_borel_finite_hidden_opponent_choices_positional 已在 Lean 4 中完成机械形式化和验证。
1. 引言
在 arXiv:2611.10136(第 5.2.2 节)中引入的带优先级博雷尔树博弈,对配备内部状态空间与优先级机制的无限二叉树上的两人零和博弈进行建模。这些博弈中的位置是二元组 $(v, q) \in 2^* \times Q$,其中 $v$ 是二叉树 $2^*$ 中的节点,$q$ 是状态空间 $Q$ 中的状态。在每一步中,控制当前位置的玩家选择一条出边转移,使博弈推进到子节点 $v \cdot d$(其中 $d \in \{0, 1\}$),产生一个优先级 $p \in \{0, \dots, k-1\}$,并转移到新状态 $q' \in Q$。一局无限对局追踪通过树的无限分支 $b \in 2^\omega$ 并产生无限优先级序列。结果由无限次出现的最大优先级 $p^*$ 决定:玩家 Eve 获胜当且仅当所追踪的分支 $b$ 属于指定的博雷尔获胜集合 $W_{p^*} \subseteq 2^\omega$,否则玩家 Adam 获胜。
带优先级博雷尔树博弈中获胜策略的复杂度对优先级数量 $k$ 极为敏感。根据 arXiv:2611.10136:
- 对于具有 $k = 1$ 个优先级的博弈,无记忆(位置性)策略对获胜玩家始终足够(命题 23)。
- 对于具有 $k = 2$ 个优先级的博弈,始终存在具有 2 状态存储的获胜策略,且独立于状态空间 $Q$ 的大小或结构(命题 24)。
- 对于具有 $k = 3$ 个优先级的博弈,这种一致的简洁性不再成立。arXiv:2611.10136 的命题 41 证明了不存在独立于状态数 $|Q|$ 的获胜策略所需存储大小的常数界。
arXiv:2611.10136 的猜想 19 询问是否每个带优先级博雷尔树博弈都允许存在有限存储获胜策略,且存储由状态数和优先级数的可计算函数所界定。$k = 3$ 的情形仍未解决。在该论文的设定下,博雷尔确定性给出了无限制的获胜策略,但有限存储确定性是一个独立的问题。
早先对带优先级树博弈结构的研究确立了若干基础事实:
- 三个优先级上的交替接受模式无法重标记为两个优先级(
prioritized_borel_alternating_priority_no_two_relabel),反映了优先级计数中的内在层级。 - 当所有由 Adam 控制的位置都是确定性的(至多拥有一条合法出边)时,博弈双方之一始终拥有使用单个存储状态的获胜策略(
prioritized_borel_deterministic_opponent_memoryless),而无需 $Q$ 的有限性或一般的博雷尔确定性。 - 在每局对局中的所有转移最终都由当前位置和公开分支方向决定的已确定博弈中,存在无记忆获胜者(
prioritized_borel_eventually_visible_determined_positional)。 - 有限博弈历史可以通过对手分支选择被唯一追踪和重构(
prioritized_borel_record_replay与prioritized_borel_record_injective)。 - 在具有 $k$ 个优先级的有限状态博弈中,从任意位置出发的合法出边数至多为 $2k |Q|$(
prioritized_borel_outgoing_edge_card_bound)。
在本文中,我们给出了一个在 Lean 4 中形式化的通用策略压缩定理:prioritized_borel_finite_hidden_opponent_choices_positional。我们证明,如果一名玩家在具有任意状态类型 $Q$ 和任意数量优先级 $k$ 的带优先级博雷尔博弈中拥有任意存储类型的获胜策略,并且每局合法对局仅遇到有限多次具有隐藏选择的对手行动——即目标状态或优先级不由公开方向和当前位置唯一固定的行动——那么该玩家也拥有无记忆(位置性)获胜策略。
重要的是,我们的定理允许对手在二叉树中做出无限多次分支选择:沿每局对局,只有给定方向背后的隐藏转移才必须最终停止。此外,不需要对不同对局之间的隐藏选择次数设定一致界,且状态空间 $Q$ 可以是无限的。因此,如果获胜者缺少位置性策略,则某局合法对局必定包含无限多次对手隐藏选择。反之则并未断言。
2. 预备知识
我们遵循材料中的 Lean 定义形式化带优先级博雷尔树博弈。
定义 1(BorelGamePlayer)。博弈竞技场中的两名玩家为 Eve 和 Adam,形式化为带有构造子 Eve 和 Adam 的归纳类型。
注:Eve 代表试图满足博雷尔获胜条件的存在性玩家,而 Adam 是全称性玩家。
定义 2(TreeGameEdge)。具有状态空间 $Q$ 和 $k \in \mathbb{N}$ 个优先级的带优先级二叉树竞技场中的一条边是 TreeGameEdge 的一个元素,包含:
- 类型为 $\text{List Bool}$ 的 source_node,表示二叉树 $2^*$ 中的当前顶点;
- 类型为 $Q$ 的 source_state,表示当前内部状态;
- 类型为 $\text{Bool}$ 的 dir,表示树中的子节点方向;
- 类型为 $\text{Fin } k$ 的 prio,表示沿转移产生的优先级;
- 类型为 $Q$ 的 target_state,表示后续内部状态。
注:在 Lean 中,二叉树字母表的类型为 $\text{Bool}$,其中 true 和 false 表示两个分支方向。优先级 prio 属于 $\text{Fin } k$,因此优先级被索引为 $\{0, 1, \dots, k-1\}$。
定义 3(PrioritizedBorelGame)。具有状态空间 $Q$ 和 $k$ 个优先级的带优先级博雷尔博弈是包含以下内容的结构体 PrioritizedBorelGame:
- 类型为 $\text{List Bool} \times Q \to \text{BorelGamePlayer}$ 的 owner,将每个位置分配给一名玩家;
- 类型为 $Q$ 的 init_state,即根节点 $[]$ 处的初始内部状态;
- edges,类型为
TreeGameEdge的边的集合; - edges_outgoing,断言每个位置 $(v, q)$ 在 edges 中都至少有一条源节点为 $v$ 且源状态为 $q$ 的出边;
- winning_sets,为每个优先级 $i \in \text{Fin } k$ 分配一个类型为 $\text{Set } (\mathbb{N} \to \text{Bool})$ 的目标分支集合;
- winning_measurable,断言每个获胜集合都是博雷尔可测的。
注:条件 edges_outgoing 确保博弈不会终止且不会发生死锁。获胜集合是康托尔空间 $\mathbb{N} \to \text{Bool}$ 的子集,且要求每个集合在标准博雷尔乘积 $\sigma$-代数下是可测的。
定义 4(FiniteMemoryStrategy)。在博弈 $G$ 中玩家 $pl$ 具有存储类型 $M$ 的策略是包含以下内容的结构体 FiniteMemoryStrategy:
- 类型为 $M$ 的 init_mem,即初始存储状态;
- 类型为 $M \to \text{TreeGameEdge} \to M$ 的 update,在观察到转移时更新存储;
- 类型为 $M \to \text{List Bool} \to Q \to \text{TreeGameEdge}$ 的 choice,选择一条出边转移;
- choice_edge,断言对于由 $pl$ 拥有的任意存储 $m$ 和位置 $(v, q)$,choice 在 edges 中产生一条源节点为 $v$ 且源状态为 $q$ 的合法出边。
注:在此定义中存储类型 $M$ 是任意的。当 $M = \text{Unit}$ 时策略是位置性的(无记忆的)。choice 函数仅被要求在由玩家 $pl$ 拥有的位置处返回合法出边。
定义 5(PrioritizedBorelStrategyWins)。一局无限对局是一个序列 $\pi : \mathbb{N} \to \text{TreeGameEdge}$。如果对所有 $n$ 都有 $\pi(n) \in G.\text{edges}$,$(\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}$,且存在从 $\sigma.\text{init\_mem}$ 开始、由 $\sigma.\text{update}$ 更新的存储序列 $\text{mem} : \mathbb{N} \to M$,使得每当 $pl$ 拥有该位置时都有 $\pi(n) = \sigma.\text{choice}(\text{mem}(n), (\pi(n)).\text{source\_node}, (\pi(n)).\text{source\_state})$,则对局 $\pi$ 是合法的且与策略 $\sigma$ 一致。如果每局一致的合法对局都满足: $$ \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). $$ 则策略 $\sigma$ 对 Eve 满足 PrioritizedBorelStrategyWins。如果没有任何一致的合法对局满足 Eve 的获胜条件,则策略 $\sigma$ 对 Adam 满足 PrioritizedBorelStrategyWins。
注:获胜条件评估类似奇偶博弈的循环性:无限次出现的最大优先级决定了哪个博雷尔集合必须包含该无限分支 $(n \mapsto (\pi(n)).\text{dir})$。在 Lean 中,循环性使用自然数上的余有限集滤子沿滤子量词来定义。
定义 6(PrioritizedBorelStrategyHistory)。归纳关系 PrioritizedBorelStrategyHistory 表征与 $\sigma$ 一致的有限执行轨迹 $h : \text{List } (\text{Bool} \times Q \times \text{Fin } k)$:
- root:空历史 $[]$ 达到存储 $\sigma.\text{init\_mem}$、节点 $[]$ 以及状态 $G.\text{init\_state}$;
- step:通过边 $e$ 延伸历史 $h$ 会将 $(e.\text{dir}, e.\text{target\_state}, e.\text{prio})$ 追加到 $h$,将存储更新为 $\sigma.\text{update}(m, e)$,将节点推进到 $v ++ [e.\text{dir}]$,将状态更新为 $e.\text{target\_state}$,并在每当 $pl$ 拥有 $(v, q)$ 时要求 $e = \sigma.\text{choice}(m, v, q)$。
注:单步特征签名对方向、目标状态和优先级进行编码。在每一步中都会验证树节点和内部状态。
定义 7(TotalPreorder 与 LinearOrder.toTotalPreorder)。全预序 TotalPreorder 是比较关系为全关系(total)的预序:对所有的 $a$ 和 $b$,要么 $a \le b$,要么 $b \le a$。每个线性序都通过 LinearOrder.toTotalPreorder 导出一个全预序。
注:全预序不要求反对称性,允许不同的元素相互有界。在我们的构造中,特征签名列表上被赋予了一个良基全序,以选取唯一的代表历史。
3. 主要结果
主要结果是策略压缩定理 prioritized_borel_finite_hidden_opponent_choices_positional。
定理(由对手隐藏选择的最终唯一性得出位置性策略)。设 $Q$ 为任意类型且 $k \in \mathbb{N}$。设 $G$ 为带优先级博雷尔博弈 PrioritizedBorelGame,$pl \in \text{BorelGamePlayer}$,且 $\sigma$ 为具有任意存储类型 $M$ 的策略 FiniteMemoryStrategy,使得 PrioritizedBorelStrategyWins 对 $G$、$pl$ 和 $\sigma$ 成立。假设沿从初始位置 $([], G.\text{init\_state})$ 出发的每局合法对局 $\pi : \mathbb{N} \to \text{TreeGameEdge}$,除了有限多步之外所有对手行动在该方向背后都没有隐藏选择: $$ \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)). $$ 则玩家 $pl$ 拥有一个存储类型为 $\text{Unit}$ 的 FiniteMemoryStrategy 类型的无记忆(位置性)获胜策略 $\tau$,满足: $$ \text{PrioritizedBorelStrategyWins } G\ pl\ \tau. $$
在 Lean 陈述中,prioritized_borel_finite_hidden_opponent_choices_positional 对任意状态类型 $Q$、优先级界 $k$、博弈 $G$、玩家 $pl$、存储类型 $M$ 以及获胜策略 $\sigma$ 进行全称量化,假定沿每局合法对局除了有限多步之外所有对手行动在方向背后都没有隐藏选择的假设,并得出存在玩家 $pl$ 的存储类型为 $\text{Unit}$ 的获胜策略 $\tau$ 这一存在性陈述,且对 $Q$ 没有施加任何有限性假设,对 $k$ 也没有任何限制。
该开发工作中的若干相关定理确立了带优先级树博弈中存储与确定性的附加性质:
- 确定性对手无记忆确定性(
prioritized_borel_deterministic_opponent_memoryless):如果由 Adam 控制的每个位置都至多有一条合法出边,则博弈双方之一拥有使用单个存储状态的获胜策略,而无需 $Q$ 的有限性或一般的博雷尔确定性。 - 最终可见的已确定博弈(
prioritized_borel_eventually_visible_determined_positional):在已确定的带优先级树博弈中,如果沿每局合法对局,除有限多步外所有行动都由当前位置和公开分支方向唯一确定,则存在无记忆获胜者。 - 反向确定性唯一性(
prioritized_borel_reverse_state_histories_unique):如果在每个固定的父节点和子方向处树博弈边关于状态是反向确定性的,则至多只有一个状态历史能到达任意给定的固定节点和最终状态。 - 历史重放与单射性(
prioritized_borel_record_replay与prioritized_borel_record_injective):兼容的有限历史可以从其长度和对手控制的分支位置处的选择序列中唯一重构,从而证明共享这些记录的历史是相同的。 - 出边基数界(
prioritized_borel_outgoing_edge_card_bound):在具有 $k$ 个优先级的有限状态博弈中,任意固定位置处的合法出边数至多为 $2k |Q|$。 - 最终隐藏影子(
prioritized_borel_eventual_hidden_shadow):在其兼容性、可见性和单调性假设下,隐藏选择记录趋于稳定,且历史最终通过实际边相互延伸。 - 收益的尾部同余(
prioritized_borel_payoff_tail_congr):只要两局带优先级博弈对局的方向处处一致且优先级最终一致,它们就具有相同的收益。
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. 证明
证明思路: 策略 $\sigma$ 使用沿对局更新的存储 $M$ 来选择出边。为了构造无记忆策略 $\tau$,玩家 $pl$ 必须在任意位置 $(v, q)$ 处选择一条边,而不依赖于过去的对局。我们为可达位置定义规范代表历史。我们在类型为 $\text{Bool} \times Q \times \text{Fin } k$ 的边特征签名列表上固定一个良基全序。一条历史拥有一个由对手行动处的特征签名组成的隐藏选择记录,其中公开方向不能唯一确定该边。对于每个可达位置 $(v, q)$,选择一条在该序下其隐藏选择记录最小的一致历史。然后,位置性策略 $\tau$ 选择 $\sigma$ 在该规范历史之后所做出的行动。
当与 $\tau$ 进行对局 $\pi$ 时,第 $n$ 步的规范代表历史不一定与 $\pi$ 的实际历史相符。然而,由于对手的隐藏选择在第 $N$ 步之后停止,存在一个步数 $K$,使得在此之后每个代表历史都通过实际的边特征签名延伸其前驱。我们从这个嵌套序列中提取出边特征签名的无限序列 $f$。这定义了一条完全与原策略 $\sigma$ 一致的无限影子对局 $\rho$。由于 $\sigma$ 是获胜策略,$pl$ 赢得 $\rho$。因为方向处处一致且优先级在尾部 $n \ge K$ 处一致,prioritized_borel_payoff_tail_congr 保证了 $pl$ 赢得 $\pi$。
辅助引理:
引理 1(规范代表的可达性与规约)。 设 $\pi$ 是与从 $\sigma$ 构造的规范位置性策略 $\tau$ 一致的对局。则对所有 $n \in \mathbb{N}$,位置 $((\pi(n)).\text{source\_node}, (\pi(n)).\text{source\_state})$ 在 $\sigma$ 下是可达的,且存在存储状态 $m \in M$,使得第 $n$ 步的规范代表历史以存储 $m$、节点 $(\pi(n)).\text{source\_node}$ 和状态 $(\pi(n)).\text{source\_state}$ 满足 PrioritizedBorelStrategyHistory。 证明:可达性通过对 $n$ 进行归纳得出:在第 $0$ 步,根位置通过 PrioritizedBorelStrategyHistory 的根构造子可达。对于归纳步,在由 $pl$ 拥有的位置处,$\tau$ 选择由 $\sigma$ 从代表历史所规定的边。在对手位置处,任意合法边都可以一致地延伸该历史。随后代表函数的规约给出了证明该历史的存储状态 $m$。
引理 2(规范历史的长度与可见投影)。 设 $h$ 是具有节点 $v$ 且满足 PrioritizedBorelStrategyHistory 的历史。则通过投影 $h$ 的第一个分量得到的方向列表等于 $v$。此外,对于对局 $\pi$,$(\pi(n)).\text{source\_node}$ 的长度为 $n$,且由第 $n$ 步之前 $\pi$ 的方向序列组成。因此,第 $n$ 步的代表历史的长度为 $n$,且其可见方向投影等于 $\pi$ 长度为 $n$ 的实际方向前缀。 证明:通过对 PrioritizedBorelStrategyHistory 的归纳定义进行归纳,每一步都将 $e.\text{dir}$ 追加到节点,并将 $(e.\text{dir}, e.\text{target\_state}, e.\text{prio})$ 追加到历史。对于对局 $\pi$,节点拼接 $(\pi(n+1)).\text{source\_node} = (\pi(n)).\text{source\_node} ++ [(\pi(n)).\text{dir}]$ 意味着 $(\pi(n)).\text{source\_node}$ 是前 $n$ 个方向的列表。对比长度和投影即可得出断言。
引理 3(代表历史的稳定性)。 设 $\pi$ 是遵循 $\tau$ 的合法对局。假设存在 $N$,使得对所有 $n \ge N$,要么 $pl$ 拥有该位置,要么对手的行动由方向唯一确定: $$ \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)). $$ 则存在 $K \ge N$,使得规范代表历史趋于稳定:对所有 $n \ge K$,第 $n+1$ 步的代表历史是第 $n$ 步的代表历史后面附加上第 $n$ 步的实际边特征签名。 证明:在可达位置处,代表历史可以通过实际边与 $\sigma$ 一致地延伸:在 $pl$ 的位置处,这是 $\tau$ 的定义;在对手位置处,允许任意合法边。在 $N$ 之后,该延伸不会给隐藏选择记录增加任何内容。下一个代表在下一个位置处使记录最小化,因此其记录至多为前一个记录。良基全序中的非递增序列最终常值。具有相同可见方向和隐藏选择记录的兼容历史是相等的,因为该玩家的策略和对手的每条非隐藏边都是确定的。将这种唯一性应用于下一个代表和已延伸的前一个代表,便给出了所主张的等式。这就是 prioritized_borel_eventual_hidden_shadow 的作用。
引理 4(可见影子序列提取)。 设 $\text{histories} : \mathbb{N} \to \text{List } (\text{Bool} \times Q \times \text{Fin } k)$ 与 $\text{actual} : \mathbb{N} \to (\text{Bool} \times Q \times \text{Fin } k)$ 满足: 1. 对所有 $n$,$\text{histories}(n)$ 的长度为 $n$; 2. 对所有 $n$,$\text{histories}(n)$ 的方向投影与 $\text{actual}$ 的前 $n$ 个方向匹配; 3. 对所有 $n \ge K$,$\text{histories}(n+1)=\text{histories}(n) ++ [\text{actual}(n)]$。 则存在无限序列 $f : \mathbb{N} \to (\text{Bool} \times Q \times \text{Fin } k)$ 使得: - 对所有 $n \ge K$,$f$ 的长度为 $n$ 的前缀是 $\text{histories}(n)$ 的前缀; - 对所有 $n \ge K$,$f(n) = \text{actual}(n)$; - 对所有 $n \in \mathbb{N}$,$f(n)$ 的方向等于 $\text{actual}(n)$ 的方向。 证明:利用 $K$ 之前 $\text{histories}(K)$ 的项以及从 $K$ 开始的 $\text{actual}(n)$ 来定义 $f$。逐次延伸条件证明了对每个 $n \ge K$,其长度为 $n$ 的前缀等于 $\text{histories}(n)$。方向的一致性在 $K$ 之前由条件 2 保证,在此之后由定义保证。
引理 5(影子对局的合法性与策略兼容性)。 设 $f : \mathbb{N} \to (\text{Bool} \times Q \times \text{Fin } k)$ 为引理 4 中的序列。则 $f$ 的每个有限前缀都是 $\sigma$ 的满足 PrioritizedBorelStrategyHistory 的有效策略历史,且由 $f$ 构造的边序列 $\rho$ 定义了一条从 $([], G.\text{init\_state})$ 出发、与 $\sigma$ 一致的合法无限对局。 证明:对于任意长度 $m$,选取 $n = \max(m, K)$ 可确保 $f$ 的长度为 $m$ 的前缀是 $\text{histories}(n)$ 的前缀。由于 $\text{histories}(n)$ 满足 PrioritizedBorelStrategyHistory,其每个前缀亦然。这些一致的有限前缀的无限极限定义了一条合法对局 $\rho$,其中每一步的存储更新和选择都与 $\sigma$ 匹配。
引理 6(prioritized_borel_payoff_tail_congr)。 设 $\pi, \rho : \mathbb{N} \to \text{TreeGameEdge}$ 为 $G$ 中的两局合法对局。假设: 1. 对所有 $n \in \mathbb{N}$,$(\pi(n)).\text{dir} = (\rho(n)).\text{dir}$; 2. 存在 $K$ 使得对所有 $n \ge K$,$(\pi(n)).\text{prio} = (\rho(n)).\text{prio}$。 则 $\pi$ 满足 Eve 的获胜条件当且仅当 $\rho$ 满足 Eve 的获胜条件。 证明:由于对所有 $n$ 都有 $(\pi(n)).\text{dir} = (\rho(n)).\text{dir}$,两局对局追踪相同的无限分支 $b \in 2^\omega$。由于对所有 $n \ge K$ 都有 $(\pi(n)).\text{prio} = (\rho(n)).\text{prio}$,优先级序列的尾部是相同的。对于每个优先级 $p \in \text{Fin } k$,断言 $p$ 出现无限多次的谓词仅取决于序列的尾部,这在有限前缀下是不变的。因此 $\pi$ 与 $\rho$ 拥有相同的循环优先级集合以及相同的最大循环优先级 $p^*$。由于 $b \in G.\text{winning\_sets}(p^*)$ 在相同的分支和优先级上求值,获胜条件对 $\pi$ 成立当且仅当对 $\rho$ 成立。由 prioritized_borel_payoff_tail_congr 得证。
引理的详细结合: 我们现在逐步遵循 prioritized_borel_finite_hidden_opponent_choices_positional 的 Lean 证明。
1. 序与位置性策略: 我们在特征签名列表 $\text{List } (\text{Bool} \times Q \times \text{Fin } k)$ 上获得一个良基全序。在到达每个可达位置的一致历史中,我们使隐藏选择记录最小化,选取具有该记录的历史,并由此定义位置性策略 $\tau$。其存储类型为 $\text{Unit}$。
2. 对局 $\pi$ 的假设: 设 $\pi : \mathbb{N} \to \text{TreeGameEdge}$ 为满足合法性、初始条件、转移关系以及与 $\tau$ 的存储一致性的对局。 由于 $\tau$ 使用存储类型 $\text{Unit}$,存储序列对所有 $n$ 满足 $\text{mem}(n) = ()$。因此策略选择条件简化为: $$ \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}. $$ 我们将此性质记录为 $\pi$ 遵循 $\tau$ 的选择的条件。
3. 代表历史的稳定性: 根据定理假设,存在 $N$ 使得当 $n \ge N$ 时对手隐藏选择停止。将引理 3 应用于遵循选择的条件、$N$ 以及无隐藏选择假设,我们得到 $K \ge N$,使得每个后续代表历史都是前一个代表历史由实际边特征签名延伸而来。
4. 代表历史与长度: 我们定义 $\text{histories}(n)$ 为到达第 $n$ 步位置的规范代表历史,并将 $\text{actual}(n)$ 定义为边 $\pi(n)$ 的特征签名。 由引理 1,每个 $\text{histories}(n)$ 是可达的且满足 PrioritizedBorelStrategyHistory。由引理 2,$\text{histories}(n)$ 的节点投影等于 $(\pi(n)).\text{source\_node}$。由于 $\pi$ 拼接方向,$\text{histories}(n)$ 的长度为 $n$,且其可见方向投影与 $\text{actual}$ 匹配。
5. 影子对局构造: 应用引理 4 于长度、方向投影以及在 $K$ 处的稳定性,我们得到满足前缀、尾部和方向匹配条件的无限特征签名序列 $f$。 由引理 5,$f$ 定义了一条与 $\sigma$ 一致的合法对局 $\rho$。
6. 收益同余与结论: 由于 $\sigma$ 对 $pl$ 是获胜的,玩家 $pl$ 赢得 $\rho$。 我们验证引理 6 的两个条件: - 关于方向一致:对所有 $n$,$(\pi(n)).\text{dir} = (\rho(n)).\text{dir}$ 成立,因为 $f$ 的方向处处与 $\text{actual}$ 匹配。 - 关于优先级一致:$(\pi(n)).\text{prio} = (\rho(n)).\text{prio}$ 对所有 $n \ge K$ 成立,因为对所有 $n \ge K$ 都有 $f(n) = \text{actual}(n)$。 由引理 6(prioritized_borel_payoff_tail_congr),Eve 赢得 $\pi$ 当且仅当 Eve 赢得 $\rho$。 我们对 $pl \in \text{BorelGamePlayer}$ 进行分情况讨论得出结论: - 若 $pl = \text{Eve}$,等价性表明 Eve 赢得 $\pi$。 - 若 $pl = \text{Adam}$,Eve 未赢得 $\rho$,因此等价性表明 Eve 未赢得 $\pi$,即 Adam 赢得 $\pi$。 在这两种情况下,$pl$ 都赢得 $\pi$。因此,$\tau$ 是 $pl$ 的获胜位置性策略,证明完毕。
5. 讨论
适用范围与边界: 定理 prioritized_borel_finite_hidden_opponent_choices_positional 确立了:只要沿每局合法对局对手的隐藏转移最终停止,由任意存储类型表示的获胜策略都可以压缩为位置性策略。阐明该定理未涵盖的内容至关重要:
- 持续隐藏选择:该定理的关键要求是,在每局合法对局中,除了有限多步之外,所有对手转移都由其公开分支方向和当前位置唯一确定。如果对手可以反复做出隐藏的非确定性选择——例如在共享相同分支方向 $d \in \{0, 1\}$ 的多个目标状态或优先级之间进行选择——稳定性论证便不再适用;该定理并不判定是否存在位置性获胜者。
- 确定性:该定理假定存在初始获胜策略 $\sigma$,其存储类型不必是有限的。它并不从零开始确立获胜策略的存在性(博弈确定性),后者需要博雷尔确定性论证。
- 任意状态空间:尽管 arXiv:2611.10136 的猜想 19 是针对有限状态空间 $Q$ 表述的,但我们的结果对 $Q$ 不作任何有限性或可数性假设。该定理对任意类型 $Q$ 和任意数量的优先级 $k \in \mathbb{N}$ 均成立。
与猜想 19 的关系: arXiv:2611.10136 的猜想 19 探讨了一般带优先级博雷尔博弈中的有限存储获胜者和可计算存储界。第 5.2.2 节指出三个优先级的情形仍未解决。 该论文确立了一个显著的转变: 1. 具有 $k = 1$ 个优先级的博弈允许存在无记忆获胜策略(命题 23)。 2. 具有 $k = 2$ 个优先级的博弈允许存在具有 2 个存储状态的获胜策略,且独立于 $|Q|$(命题 24)。 3. 具有 $k = 3$ 个优先级的博弈需要随 $|Q|$ 增长的存储(命题 41)。
我们的定理为命题 41 中确定的存储需求提供了结构性见解。它表明,位置性获胜策略的缺失必然导致存在具有无限多次对手隐藏选择的合法对局。在所述的最终唯一性假设下,无论 $k = 3$ 还是更大,也无论 $Q$ 的基数如何,任何获胜策略都可以压缩为存储类型为 $\text{Unit}$ 的位置性策略。
未决问题: 该未决问题条目以及 arXiv:2611.10136 提出了若干自然的未决问题: - 当对手做出无限多次隐藏选择时,每个具有 $k = 3$ 个优先级的带优先级博雷尔树博弈是否都允许存在有限存储获胜策略? - 在隐藏选择持续存在的一般情形下,$k = 3$ 博弈所需的存储大小是否由 $|Q|$ 的可计算函数所界定? - 策略压缩能否在附加限制(例如反向确定性状态结构,prioritized_borel_reverse_state_histories_unique)下推广到具有持续隐藏选择的博弈?
为什么是研究级成果
- 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 声明
- prioritized_borel_finite_hidden_opponent_choices_positionalFix a winning strategy in a prioritized tree game, with an arbitrary state type. Suppose that on every legal play, all but finitely many…
- prioritized_borel_alternating_priority_no_two_relabelThe alternating acceptance pattern false, true, false on three priorities cannot be represented for all recurrent-priority sets by any…
- prioritized_borel_deterministic_opponent_memorylessIf every position controlled by Adam in a prioritized Borel game has at most one legal outgoing edge, then one of the players has a…
- prioritized_borel_eventually_visible_determined_positionalA determined prioritized tree game has a memoryless winner if, along every legal play, all but finitely many moves are uniquely determined…
- prioritized_borel_record_replayA compatible finite history can be reconstructed from its length and the sequence of choices at opponent-controlled branching positions.
- prioritized_borel_record_injectiveCompatible finite histories with equal length and equal records of opponent branching choices are identical.
- prioritized_borel_outgoing_edge_card_boundAt any fixed position in a finite-state game with k priorities there are at most 2k times the number of states legal outgoing edges.
- prioritized_borel_reverse_state_histories_uniqueIf a tree-game edge is reverse-deterministic in the state at each fixed parent node and child direction, then at most one state history…
- prioritized_borel_eventual_hidden_shadowCompatible finite histories whose hidden-choice records eventually do not increase and whose extensions add no hidden choices eventually…
- prioritized_borel_payoff_tail_congrTwo prioritized-game plays have the same payoff when their directions agree everywhere and their priorities agree eventually.
Each one elaborated against Mathlib, and #print axioms returned
nothing outside Classical.choice · Quot.sound · propext.
参考文献
- arXiv:2611.10136 — Automata for MSO over Infinite Trees with Quantification over Borel Sets of Branches
由 gemini-3.8-flash 根据知识库起草,经过检查并由 Codex 审阅英文版;中文版由模型翻译并对照英文检查。只有 Lean 部分经过验证,文字是对它的解读。