论文标题
Bimatrix游戏中1/3的nash均衡的多项式时间算法
A Polynomial-Time Algorithm for 1/3-Approximate Nash Equilibria in Bimatrix Games
论文作者
论文摘要
自从Bimatrix游戏中NASH Equilibria的著名PPAD完整性结果以来，一系列的研究集中在计算$ \ Varepsilon $ -AppapproximateNash Equilibria的多项式时间算法上。在多项式时间内找到最佳的近似保证，这是解决近似平衡的复杂性的基本和非平凡的追求。尽管付出了很大的努力，但tsaknakis和spirakis的算法（近似保证金为$（0.3393+δ）$，在过去15年中仍然是最先进的。在本文中，我们提出了TSAKNAKIS-SPIRAKIS算法的新改进，从而产生了一种多项式时算法，该算法计算出$（\ frac {1} {3} {3}+δ）$ - NASH平衡，以实现任何常量$δ> 0 $。我们方法的主要思想是超越原始策略和双重策略的凸组合的使用，如Tsaknakis和Spirakis的优化框架所定义的，并丰富了我们在算法的某些瓶颈案例中构建策略概况的策略池。
Since the celebrated PPAD-completeness result for Nash equilibria in bimatrix games, a long line of research has focused on polynomial-time algorithms that compute $\varepsilon$-approximate Nash equilibria. Finding the best possible approximation guarantee that we can have in polynomial time has been a fundamental and non-trivial pursuit on settling the complexity of approximate equilibria. Despite a significant amount of effort, the algorithm of Tsaknakis and Spirakis, with an approximation guarantee of $(0.3393+δ)$, remains the state of the art over the last 15 years. In this paper, we propose a new refinement of the Tsaknakis-Spirakis algorithm, resulting in a polynomial-time algorithm that computes a $(\frac{1}{3}+δ)$-Nash equilibrium, for any constant $δ>0$. The main idea of our approach is to go beyond the use of convex combinations of primal and dual strategies, as defined in the optimization framework of Tsaknakis and Spirakis, and enrich the pool of strategies from which we build the strategy profiles that we output in certain bottleneck cases of the algorithm.
