Efficient Algorithms for Constant Well Supported Approximate Equilibria in Bimatrix Games
Efficient Algorithms for Constant Well Supported Approximate Equilibria in Bimatrix Games
复制标题
Bimatrix 博弈中恒定良好支持的近似均衡的高效算法
DOI：
10.1007/978-3-540-73420-8_52
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
P. Spirakis
中科院分区：
文献类型：
--
作者：
S. Kontogiannis;P. Spirakis
本文研究了双矩阵对策中支持性好的近似纳什均衡（简称SuppNE）的易处理性。鉴于在多项式时间内构造纳什均衡（简称NE）的明显困难性，即使是双矩阵博弈，理解问题的可逼近性的局限性也是非常重要的。
我们初步证明了SuppNE对任意真实的向量加到行（列）玩家的收益矩阵的行（列）上是免疫的。因此，我们提出了一个多项式时间算法（基于线性规划），构造了一个0.5-SuppNE的任意赢输游戏。
然后，我们参数化我们的技术赢输游戏，为了将其应用到任意（规范化）双矩阵游戏。事实上，这种新技术导致了一个较弱的赢-输游戏，其中的黄金比例是1/5-1/2。然而，这种参数化技术很好地扩展到任意[0，1]-双矩阵游戏的技术，它确保了多项式时间内的0.658-SuppNE。
据我们所知，这些是第一个多项式时间算法提供了规范化或输赢双矩阵游戏的e-SuppNE，对于一些非平凡常数e ∈ [0，1），有界远离1。
In this work we study the tractability of well supported approximate Nash Equilibria (SuppNE in short) in bimatrix games. In view of the apparent intractability of constructing Nash Equilibria (NE in short) in polynomial time, even for bimatrix games, understanding the limitations of the approximability of the problem is of great importance.
We initially prove that SuppNE are immune to the addition of arbitrary real vectors to the rows (columns) of the row (column) player's payoff matrix. Consequently we propose a polynomial time algorithm (based on linear programming) that constructs a 0.5-SuppNE for arbitrary win lose games.
We then parameterize our technique for win lose games, in order to apply it to arbitrary (normalized) bimatrix games. Indeed, this new technique leads to a weaker ϕ-SuppNE for win lose games, where ϕ = √5-1/2 is the golden ratio. Nevertheless, this parameterized technique extends nicely to a technique for arbitrary [0, 1]-bimatrix games, which assures a 0.658-SuppNE in polynomial time.
To our knowledge, these are the first polynomial time algorithms providing e-SuppNE of normalized or win lose bimatrix games, for some nontrivial constant e ∈ [0, 1), bounded away from 1.