通过扰动最优回应，显著减少零和博弈算法的迭代次数。
Perturbing Best Responses in Zero-Sum Games
- 用扰动后的收益计算最优回应，改进双轨法和虚构演进。
- 在特定扰动下，迭代次数期望可降至对数级别。
- 适用于纯策略具内层结构的游戏，高效实现扰动。
本文研究了在零和博弈中，基于最优回应的算法（如双轨法和虚构演进）受扰动的影响。假设计算最优回应的预言机在选择前对收益进行扰动，我们发现该机制能有效减少两种算法的迭代次数。在某些情况下，合适的扰动可使期望迭代次数降至对数级别。尽管收益扰动在计算上较复杂，需遍历所有纯策略，但我们在纯策略具有内在结构的游戏中证明了其可高效实现。
原文摘要 · Abstract (English)
This paper investigates the impact of perturbations on the best-response-based algorithms approximating Nash equilibria in zero-sum games, namely Double Oracle and Fictitious Play. More precisely, we assume that the oracle computing the best responses perturbs the utilities before selecting the best response. We show that using such an oracle reduces the number of iterations for both algorithms. For some cases, suitable perturbations ensure the expected number of iterations is logarithmic. Although the utility perturbation is computationally demanding as it requires iterating through all pure strategies, we demonstrate that one can efficiently perturb the utilities in games where pure strategies have further inner structure.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。