LegoNE：LLM 驱动的专家级 Nash 均衡算法发现
超越人类设计范式的神经-符号系统

🎯核心问题：为何 ANE 算法发现如此困难

Nash 均衡（NE）是博弈论的基础解概念，由 Nash 在 1951 年提出。但计算 NE 是一个持续 70 年的计算挑战：经典 Lemke-Howson 算法需要指数时间，PPAD-完全性结果（Daskalakis-Goldberg-Papadimitriou 三人以上、Chen-Deng 二人）确认这一困难是内禀的。

近似 Nash 均衡（ANE）的研究由此兴起：一个策略 profile x 是 ϵ-ANE，如果没有任何玩家能通过单方面偏离获得超过 ϵ 的收益提升。ϵ 越小，保证越好。Lipton-Markakis-Mehta 证明了 ϵ-ANE 可在拟多项式时间内计算（首个次指数算法）；Rubinstein 证明了不存在 PTAS（在 PPAD 的 ETH 假设下），但硬度常数未明确且被认为很小。

论文揭示了一个关键的历史事实：二人博弈的多项式时间保证序列在 2007 年后停滞了 15 年：

• 0.75 — Kontogiannis-Panagopoulou-Spirakis (KPS), 2006
• 0.5 — Daskalakis-Mehta-Papadimitriou (DMP), 2006
• 0.3393 + δ — Tsaknakis-Spirakis (TS), 2007
• 停滞 15 年
• 1/3 + δ — Deligkas-Fasoulakis-Markakis (DFM), 2022

对于三人以上博弈，进展更为有限：唯一已知的多项式时间方法是 extension technique（Bosse-Byrka-Markakis 2010、Hénon-De Rougemont-Santha 2008），它递归地把 r 玩家算法提升为 (r+1) 玩家算法，保证从 ϵ_r 退化为 1/(2−ϵ_r)。应用到最佳二人结果，得到三人 0.6+δ，且保证随玩家数增长趋近 1。

论文的核心问题意识是：LLM 能大规模生成候选算法，但如何自动 certify 其 worst-case 保证？对于欧氏几何，机械化演绎系统已存在数十年；但对于 ANE 算法分析，此前不存在可比较的自动化系统，证明依赖 ad-hoc、逐篇论文的数学论证。LegoNE 正是填补这一空白的领域特定形式系统。

🧱LegoNE 框架：语言 + 自动分析器

LegoNE 由两个互补组件构成。

2.1 领域特定语言

LegoNE 语言是一个 Python 风格的领域特定语言，用于从高层 building blocks 组合 ANE 算法。这些 blocks 来自过去二十年博弈论研究的高层战略概念：

• BestResponse — 计算对对手策略的最优响应
• Random — 生成任意策略
• StationaryPoint — 计算最大 regret 函数的近似驻点及其对偶，返回四个策略（Tsaknakis-Spirakis 2007 的核心）
• ZeroSumNE — 用线性规划计算零和博弈的精确 NE
• EqMix — 两个策略的等概率混合
• MaxPayoff — 最大化给定收益函数
• UniformMixing — 等概率混合
• OptimalMixing — 最优混合（编译器自动应用）

例如 DMP 算法可用几行代码表达：定义 BestResponse1、Random1 等 blocks，然后组合它们返回两个玩家的策略 profile。这种模块化方法把算法设计从"从零推理"转变为"组合已建立的概念"——为 LLM 创造了一个结构化的设计空间。

2.2 自动分析器

分析器是 LegoNE 的核心创新。它把算法分析转化为系统化的机器驱动过程：对任何用 LegoNE 语言表达的算法，分析器计算其最佳可能近似保证 ϵ，并同时生成该保证的计算机证明。

关键洞察：在 LegoNE 中，计算保证等价于证明保证。优化问题的解本身就是构造性证明。

⚙️两步编译：instantiation 与 forgetting

分析器的核心是两步抽象，把无限维证明义务简化为固定规模的数学规划。

3.1 第一步：instantiation——从无限到有限

起点是把算法的过程代码翻译为一组声明式逻辑属性，基于 Floyd-Hoare 语义。例如：

k = BestResponse1(j)
被编码为：∀ s₁, u₁(s₁, j) ≤ u₁(k, j)

这个属性范围覆盖无限维空间（所有策略、所有收益函数）。分析器的关键洞察来自人类证明实践：人类证明不推理所有无限多策略，而是巧妙选择几个关键实例。分析器系统地把全称量化变量替换为算法代码中实际出现的所有具体策略变量。

例如对 DMP 算法，∀ s₁ 被实例化为算法中 player 1 使用的策略 i、k、r₁。这把无限量化简化为有限个实例化约束。

3.2 第二步：forgetting——从函数到变量

实例化后约束数量有限，但 u₁(i, j) 这类项仍依赖任意博弈的未知收益函数。分析器把每个收益值（如 u₁(i, j)）视为单个抽象实变量 v₁,ij——忘记函数 u₁ 的底层结构。不等式 u₁(i, j) ≤ u₁(k, j) 变为 v₁,i,j ≤ v₁,k,j。

3.3 最终形式：约束优化问题

两步后，无限维断言被转化为有限实变量上的代数不等式系统。分析器把它表述为约束优化问题：

maximize g(a₁, a₂, ...)
subject to ϕ₀(a₁, a₂, ...)

其中 g(a₁, a₂, ...) 是原 regret 函数 f(x) 用抽象变量表达的形式，ϕ₀ 是从算法属性导出的不等式集合。最优值就是该算法通过此证明策略可推导出的最紧 worst-case 近似保证 ϵ。

关键性质：变量数和约束数一旦证明策略固定就固定，不随博弈实例规模增长。这个固定规模问题由现成数值求解器（Gurobi 或 Mathematica）求解。论文实现用 C++（Flex/Bison 词法语法分析）+ Mathematica 14.2（AccuracyGoal=10, WorkingPrecision=20, MaxIterations=2000）。

✅实证验证：8 个已知算法全部精确复现

为验证 LegoNE 分析器的正确性，论文把文献中所有已知多项式时间 ANE 算法（覆盖二十余年）实现为 LegoNE 语言，包括复杂算法如 Tsaknakis-Spirakis。结果见论文 Table 1/2：

算法（作者-年份）	原论文保证	LegoNE 计算保证	代码行数	运行时间(s)
KPS, 2006	0.75	0.75000	27	22.55
DMP, 2006	0.5	0.50000	42	4.31
DMP3, 2006	0.38197 + δ	0.38197 + δ	38	31.13
BBM-1, 2007	0.38197	0.38197	46	11.81
CDFFJS, 2016	0.38197	0.38197	48	65.87
BBM-2, 2007	0.36392	0.36392	—	1.38
TS, 2007	0.33933 + δ	0.33933 + δ	31	13.90
DFM, 2022	1/3 + δ	0.33333 + δ	52	79.63
DFM+extension (三人)	0.6 + δ	0.60000 + δ	50	8.34

所有 8 个算法的 LegoNE 计算保证与原论文匹配至 10⁻⁵ 精度。每个算法用 ≤60 行代码表达，≤80 秒完成自动保证计算——这一任务此前需要数年累积人类研究。原证明需要数页到十余页数学论证，LegoNE 把它压缩为机器求解的固定规模优化问题。

4.1 框架扩展性

instantiation + forgetting 原则不限于固定玩家数博弈。论文还应用框架于：

• Polymatrix games：网络博弈，每个玩家收益仅由图中的邻居决定。forgetting 原则抽象掉玩家特定索引，统一分析自动证明保证。
• Vertex cover（LP 松弛+取整）：分析器自动证明 2-近似比，匹配文献已知结果。

这表明框架有潜力成为更广泛计算问题的通用自动算法分析工具——但论文坦承其精确边界仍待刻画。

🔄LLM-LegoNE loop：人机分工与定量反馈

LegoNE 与推理 LLM（DeepSeek-R1）结合形成自动发现 loop。论文明确划分人机角色：

• 人类专家：把领域知识与高层证明策略翻译为 LegoNE 语言的 building blocks。这需要 LLM 尚未达到的概念理解能力。
• LLM：在这些 blocks 的庞大组合空间中导航，以人类难以企及的规模和速度探索潜在算法。
• LegoNE 分析器：对每个候选算法计算可证明正确的近似保证，作为定量反馈返回给 LLM。

这个 loop 的关键设计选择：

• Auto-return with optimal mixing：编译器自动在算法片段末尾应用最优混合操作，让 LLM 专注于构造有效策略，编译器处理最优混合系数。
• 多阶段提示工程：初始 prompt 给出任务描述、设计约束（SSA、类型标注、无 return、强制至少一个 StationaryPoint）、有效/无效代码示例；迭代反馈 prompt 根据上一输出动态调整——无效则给编译器错误信息，有效则给当前最佳 ϵ 并鼓励更小值。
• 过程管理：维护已生成算法记录防重复；重复达阈值则重启交互；聊天历史过长则重启；限制代码行数和构造策略数。

5.1 expert inputs 的诚实清单

为评估专家知识是否偏向 LLM 朝向发现解，论文详细列出了所有专家输入：

提供的 building blocks：标准博弈论操作（BestResponse/StationaryPoint/OptimalMixing 等），定义"可用什么操作"但不规定"如何组合"。

prompt 层约束三类：

1. 结构约束（限制搜索空间）：每玩家至多 3 策略、SSA、类型标注
2. 启发式引导（非限制）：Occam 剃刀、鼓励打破对称、惩罚重复
3. 领域约束：必须包含至少一个 StationaryPoint（因为 TS 2007 以来所有有竞争力的算法都依赖驻点计算；无此块至多 ϵ=0.5）

关键：专家输入不包含——算法整体结构或组合顺序建议、使用或避免 extension technique 的提示、混合系数或收益依赖权重的指定、目标 ϵ 值、算法设计的 few-shot 示例（提供的代码示例仅说明格式，不说明算法策略）。

实证证据表明专家输入未偏向发现解：12 轮中产生的 7 个不同三人算法，仅第 1 个使用 extension technique，其余 6 个独立探索非 extension 结构。最终 0.5+δ 算法的组合模式未被设计 building blocks 的人类专家预见。

⚡二人博弈：2 轮重发现 15 年成果

在二人博弈实验中，DeepSeek-R1 仅被提供 2007 年之前的 building blocks（即 TS 2007 达到 0.3393+δ 时的工具集）。温度设为 0.8。

结果：2 轮交互内，LLM 构造出一个算法，LegoNE 证明其达到 1/3 + δ 保证——匹配 DFM 2022 的当前最佳多项式时间保证。该算法结构与 DFM 2022 不同，但保证相同。

这一结果的意义：人类专家从 0.3393+δ（2007）推进到 1/3+δ（2022）用了 15 年；LLM-LegoNE 系统用 2 轮。这展示了框架加速理论想法生成与验证的潜力。

论文还测试了 DeepSeek-V3-241226（V3）模型：100 轮扩展测试中，V3 未超越最佳保证，但发现了若干文献中未见的组合。这表明推理模型（R1）与基础模型（V3）在此任务上有显著能力差异。

🏆三人博弈：11 轮超越 extension 范式

三人博弈是论文的核心突破场景。此前人类设计方法进展有限，唯一已知的多项式时间方法是 extension technique，把最佳二人算法提升为三人算法，得到 0.6+δ。

使用 LLM-LegoNE 系统，11 轮内发现了一个根本不同的算法，LegoNE 分析证明其近似保证为 0.5 + δ，改进此前最佳的 0.6+δ 达 0.1。

该算法的核心 building block 是 StationaryPoint3：固定 player 3 的混合策略 z，用线性规划执行梯度下降过程，找到局部最小化 player 1 和 2 最大 regret 的驻点 (xs, ys)，关联对偶策略 (w, zdual)。

结构上，extension-technique 构造以 best-response-then-mix 作为最后一步；发现的算法用不同的 building block 组合，交织 BestResponse、EqMix 和 OptimalMixing，方式非平凡。

12 轮共产生 7 个不同算法，保证从 0.5+δ 到 0.8+δ 不等。除第 1 个外都不使用 extension technique——证明自动过程能探索 extension 范式之外的设计空间部分。

💎为何 0.5+δ 是范式突破而非数值改进

三人结果的 significance 远超数值改进。这是论文最深刻的论证，值得完整呈现：

Extension technique 满足 ϵ₃ = 1/(2 − ϵ₂)，其中 ϵ₂ 是二人博弈保证。要通过 extension 达到 ϵ₃ ≤ 0.5，需要 ϵ₂ = 0——即精确 NE，这是 PPAD-hard 的。

因此，发现的算法达到的保证可证明地超越 extension technique 在多项式时间内能交付的任何东西。这建立了——据作者所知——有效的多项式时间多玩家 ANE 算法存在于 extension 范式之外的首个证据。

这开启了多玩家算法的设计空间，并贡献于缩小最佳已知多项式时间保证与硬度下界之间的差距——这一差距对二人和多玩家设置都仍然很大且 largely 未刻画。

换言之：0.6→0.5 看似只是 0.1 的数值改进，但实际上是范式壁垒的突破——它证明了存在另一条设计路径，而此前整个领域认为 extension 是唯一路径。

🔬与 AlphaGeometry/FunSearch/AlphaEvolve 的对比

LegoNE+LLM 与 AlphaGeometry、FunSearch、AlphaEvolve 同属 explore-and-evaluate 架构。论文明确指出三个技术差异：

1. evaluator 的来源：AlphaGeometry 的演绎引擎 DDAR 可追溯到 Chou-Gao-Zhang 1990s 的工作，是预先存在的；FunSearch 的 evaluator 通过在特定实例上执行程序来评估，构造直接；LegoNE 的分析器是基于 instantiation+forgetting 编译原则在本工作中新构造的形式系统。
2. 反馈类型：AlphaGeometry 的 evaluator 提供二元反馈（证明找到或未找到）；LegoNE 分析器返回定量的 worst-case 保证 ϵ，使 LLM 搜索 loop 中可进行"梯度式"优化。这是关键差异——定量反馈让 LLM 知道"离最佳有多远"，而二元反馈只知"成功或失败"。
3. 验证对象：AlphaGeometry 验证静态几何命题；LegoNE 验证过程式算法的通用性能保证，需要 Floyd-Hoare 风格的程序推理结合 instantiation+forgetting 编译。

这个对比揭示了一个重要模式：AI-for-science 系统的能力上限，往往不取决于 LLM 的探索能力，而取决于 evaluator 的形式化质量与反馈粒度。LegoNE 的贡献正是 evaluator 本身——一个此前在该领域不存在的自动 worst-case 分析形式系统。

⚠️边界与诚实声明

论文的 Discussion 部分给出了诚实的边界声明，本报告完整保留：

"Our progress should be read as both a positive result and a boundary marker. LegoNE currently depends on human-curated building blocks that encode proof strategies from the existing literature; it cannot discover fundamentally different proof techniques. The framework's scope is limited to algorithm analysis problems where the instantiation and forgetting principles apply—settings where universal guarantees can be reduced to finite systems of algebraic inequalities."

具体边界：

• 依赖人类策展：building blocks 编码现有文献的证明策略，LLM 不能发现根本不同的证明技术。定义新 building block 需要深度领域专家和复杂数学推导——这是保留给人类专家的角色。
• scope 有限：仅适用于 instantiation+forgetting 可应用的领域——即通用保证可简化为有限代数不等式系统的设置。初步扩展到 vertex cover 和 polymatrix games 表明这一类非平凡，但精确边界仍待刻画。
• 编译器当前限制：不支持分支操作（编码 BBM-1 时利用对称性只编码一个分支）；不支持平方根操作（BBM-2 的 0.36392 保证需手动计算编译器输出）；KPS 和 DMP3 需手动提供对角逻辑编码。
• 未来方向：开发更具表达力的语言，允许从第一性原理分析算法，减少对手工策展 blocks 的依赖，扩大可自动分析的问题范围。

🚀对 AI4Science 的启示

LegoNE 的意义远超博弈论本身。它示范了一个可推广的神经-符号发现范式，对 AI4Science 有三点深刻启示。

11.1 "编码证明策略"是 LLM 科学发现的关键瓶颈

AlphaGeometry 之所以能超越人类奥数选手，是因为有 DDAR 这个编码了几何证明策略的演绎引擎。FunSearch 之所以能发现新矩阵乘法算法，是因为有"执行程序评估"这个简单但有效的 evaluator。LegoNE 之所以能发现超越 extension 范式的算法，是因为有 instantiation+forgetting 这个编码了 ANE 证明策略的形式系统。

共同模式：LLM 的探索能力 × evaluator 的形式化质量 = 科学发现能力。AI4Science 的下一个突破点不在于更大的 LLM，而在于为更多领域构造 LegoNE 式的形式化 evaluator。本站已解读的 Frank Coyle 演讲中"Pydantic at the door, ontology at the ledger"原则在此得到验证——LegoNE 正是一个领域特定的"ledger"，用形式化约束校验 LLM 的"幻觉"输出。

11.2 定量反馈优于二元反馈

LegoNE 与 AlphaGeometry 的关键差异是反馈类型：AlphaGeometry 返回"证明找到/未找到"，LegoNE 返回"ϵ = 0.523"。定量反馈让 LLM 能进行梯度式优化——知道"这次比上次好 0.05"比知道"这次失败"信息量大得多。

这对 AI4Science agent 系统设计有直接含义：在蛋白设计（pLDDT 分数）、药物发现（亲和力数值）、材料科学（带隙能量）等领域，应优先构造能返回连续定量指标的 evaluator，而非二元通过/失败判定。本站已解读的 Nesso-1（连续亲和力预测）、Diff-Switch（连续奖励函数）都隐含遵循这一原则。

11.3 "范式外发现"是可能的

LegoNE 最震撼的结果不是 0.6→0.5 的数值改进，而是证明了"存在 extension 范式之外的有效算法"。这意味着：当人类专家在某个领域陷入单一范式时，LLM+形式化 evaluator 有可能发现范式外的解。

在 AI4Science 中，许多领域存在类似的"范式垄断"：蛋白设计以 RFdiffusion 为中心、药物发现以 docking 为中心、基因调控以 motif 分析为中心。LegoNE 暗示：如果能为这些领域构造形式化 evaluator（编码其证明策略或验证标准），LLM 可能发现人类未预见的替代路径。这正是本站 tooluniverse 系列技能（1264+ 工具）的长期愿景——为 LLM 提供足够丰富的形式化工具层，使其能在多个科学范式间组合探索。

11.4 与本站已解读工作的呼应

LegoNE 与本站已解读的多项工作形成呼应：

• 与 Frank Coyle 演讲的呼应：LegoNE 是 Coyle "neuro-symbolic AI" 论点的完美案例——LLM（概率性）+ 形式化分析器（符号）= 科学发现。Coyle 的"Pydantic at the door, ontology at the ledger"在 LegoNE 中具体化为"building blocks at the door, instantiation+forgetting at the ledger"。
• 与潜空间综述的呼应：LegoNE 的"编码证明策略为符号语言"是潜空间综述中"表示轴"的一个具体实例——把人类证明策略编码为机器可操作的表示空间。
• 与 Diff-Switch 的呼应：Diff-Switch 用扩散模型+元动力学在集体变量空间探索蛋白开关构象；LegoNE 用 LLM+优化求解器在 building block 组合空间探索算法。两者都是"生成模型+形式化约束"的混合范式。

📄参考信息