知识卡片：ℓ∞ 收缩映射的拟多项式时间算法

一句话结论

针对 $d$ 维 ℓ∞ 范数下的非扩张映射，该论文给出了计算其 $\epsilon$-近似不动点的算法，时间复杂度为 $\log(1/\epsilon)^{O(\log^2 d)}$，并由此推出简单随机博弈可在拟多项式时间内求解。

事件概述或研究问题

论文研究的是在 ℓ∞ 范数下计算 $d$ 维非扩张（nonexpansion）映射的 $\epsilon$-近似不动点问题。作者提出了一种新算法，其核心是一个“boosting”论证，用于几何式地收缩搜索区域。作为推论之一，该算法表明简单随机博弈（simple stochastic games）可以在拟多项式时间内求解。

方法/产品要点

• 算法目标：计算任意 $d$ 维 ℓ∞ 非扩张映射的 $\epsilon$-近似不动点。
• 时间复杂度：$\log(1/\epsilon)^{O(\log^2 d)}$。
• 核心技术：boosting 论证，几何式收缩搜索区域。
• 作者：Ashkan Soleymani, Gabriele Farina。
• 发表信息：arXiv 2610.30122v1，2026-10-21，主分类 cs.GT，交叉分类 cs.CC、cs.LG、math.OC。

主要结果或产业意义

• 主要结果：给出 ℓ∞ 非扩张映射 $\epsilon$-近似不动点的拟多项式时间算法，时间上界为 $\log(1/\epsilon)^{O(\log^2 d)}$。
• 推论：简单随机博弈可在拟多项式时间内求解。
• 产业意义：待核实（材料未展开具体应用场景）。

为什么重要

该结果将 ℓ∞ 非扩张映射的不动点计算纳入拟多项式时间可解范围，并直接推出简单随机博弈的拟多项式时间可解性，对博弈论与理论计算机科学的复杂度认识具有增量意义。与既有卡片无直接重复；本条为独立的理论算法结果。

局限与不确定性

• 材料仅提供摘要，算法的具体构造细节、正确性证明与下界讨论待核实。
• “简单随机博弈可在拟多项式时间内求解”的具体归约方式与适用范围待核实。
• 是否存在更紧的时间上界或匹配下界，材料未说明，待核实。

可用于图书/PPT/简报的角度

• 作为“拟多项式时间算法”在博弈求解中的案例。
• 作为 ℓ∞ 范数下不动点计算与简单随机博弈复杂度联系的切入点。
• 作为 boosting/搜索区域几何收缩技术的算法设计示例。

原始材料

• Title: A Quasipolynomial Algorithm for $\ell_\infty$ Contractions
• Authors: Ashkan Soleymani, Gabriele Farina
• arXiv ID: 2610.30122v1
• Published: 2026-10-21T17:57:19Z
• Primary category: cs.GT
• Categories: cs.GT, cs.CC, cs.LG, math.OC
• Abstract URL: https://arxiv.org/abs/2610.30122v1
• PDF URL: https://arxiv.org/pdf/2610.30122v1