Oct, 2023
近似纳什均衡算法中的搜索与混合范式
The Search-and-Mix Paradigm in Approximate Nash Equilibrium Algorithms
TL;DRAI在数学领域以一种建设性的方式处理数学问题，使推理自动化、减少劳动力和降低错误率。本研究首次提供了一个自动化方法，用于理论计算机科学中一个经过深入研究的问题：计算两人博弈中的近似纳什均衡。我们观察到，这样的算法可以被重新表述为搜索混合范式，其中包括搜索阶段和混合阶段。通过这样做，我们能够完全自动化设计和分析混合阶段的过程。例如，我们演示了如何使用我们的方法来分析文献中所有算法的近似界限。这些近似界限是无需任何手写证明计算的。我们的自动化方法严重依赖近似纳什均衡中的LP松弛结构。由于许多近似算法和在线算法采用了LP松弛，我们的方法可能被扩展用于自动化分析其他算法。