论文标题
Bimatrix游戏中的1/2-Well支持NASH Equilibria的多项式时间算法
A Polynomial-Time Algorithm for 1/2-Well-Supported Nash Equilibria in Bimatrix Games
论文作者
论文摘要
由于即使在两人游戏中，也可以计算出纳什均衡的开创性PPAD完整性结果，因此一项重要的研究重点是在多项式时间内可以实现的放松。在本文中，我们考虑了$ \ varepsilon $ well的nash平衡的概念，其中$ \ varepsilon \ in [0,1] $ in [0,1] $对应于近似保证。简而言之，在$ \ varepsilon $的平衡中，每个玩家都选择以$ \ varepsilon $在最大可实现的回报范围内的积极概率动作，这是针对另一个玩家的策略。自从十多年前确定的良好支持的平衡的最初近似值2/3以来，该问题的进展一直非常缓慢且增量。值得注意的是，通过日益增长的复杂性算法实现了对0.6608，最后对0.6528的小改进。我们的主要结果是一种简单而直观的算法，将近似保证提高到1/2。我们的算法基于线性编程，尤其是基于利用由两个玩家的回报矩阵产生的适当定义的零和游戏。作为副产品，我们展示了如何以查询效率的方式实现相同的近似保证。
Since the seminal PPAD-completeness result for computing a Nash equilibrium even in two-player games, an important line of research has focused on relaxations achievable in polynomial time. In this paper, we consider the notion of $\varepsilon$-well-supported Nash equilibrium, where $\varepsilon \in [0,1]$ corresponds to the approximation guarantee. Put simply, in an $\varepsilon$-well-supported equilibrium, every player chooses with positive probability actions that are within $\varepsilon$ of the maximum achievable payoff, against the other player's strategy. Ever since the initial approximation guarantee of 2/3 for well-supported equilibria, which was established more than a decade ago, the progress on this problem has been extremely slow and incremental. Notably, the small improvements to 0.6608, and finally to 0.6528, were achieved by algorithms of growing complexity. Our main result is a simple and intuitive algorithm, that improves the approximation guarantee to 1/2. Our algorithm is based on linear programming and in particular on exploiting suitably defined zero-sum games that arise from the payoff matrices of the two players. As a byproduct, we show how to achieve the same approximation guarantee in a query-efficient way.
