Well Supported Approximate Equilibria in Bimatrix Games: A Graph Theoretic Approach
Well Supported Approximate Equilibria in Bimatrix Games: A Graph Theoretic Approach
复制标题
Bimatrix 游戏中得到良好支持的近似均衡：图论方法
DOI：
10.1007/978-3-540-74456-6_53
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
P. Spirakis
中科院分区：
文献类型：
--
作者：
S. Kontogiannis;P. Spirakis
本文研究了双矩阵对策中一个近似均衡的存在性和易处理性，称之为良好支持的近似纳什均衡（简称SuppNE），证明了对任意常数e？（0，1），对于两个参与者只有对数支持大小。此外，我们提出了一个多项式时间的建设SuppNE，无论是输赢和任意（规范化）双矩阵游戏。这些SuppNE的质量取决于纳什动力学图的周长，或者原始规范化游戏的（四舍五入）赢输图像。我们的建设是非常成功的稀疏赢输游戏（即，有一个常数的（0，1）-元素的双矩阵）与大围长的纳什动力学图。这同样适用于正规化的游戏，其赢输图像是稀疏的，具有大周长。
最后，我们证明了在随机正规化博弈和随机输赢博弈中构造SuppNE的简单性。在前一种情况下，我们证明了均匀全混合是一个o（1）-SuppNE，而在输赢游戏的情况下，我们表明（以高概率）有一个PNE或0.5-SuppNE的支持大小只有2。
We study the existence and tractability of a notion of approximate equilibria in bimatrix games, called well supported approximate Nash Equilibria (SuppNE in short).We prove existence of e-SuppNE for any constant e ? (0, 1), with only logarithmic support sizes for both players. Also we propose a polynomial-time construction of SuppNE, both for win lose and for arbitrary (normalized) bimatrix games. The quality of these SuppNE depends on the girth of the Nash Dynamics graph in the win lose game, or a (rounded-off) win lose image of the original normalized game. Our constructions are very successful in sparse win lose games (ie, having a constant number of (0, 1)-elements in the bimatrix) with large girth in the Nash Dynamics graph. The same holds also for normalized games whose win lose image is sparse with large girth.
Finally we prove the simplicity of constructing SuppNE both in random normalized games and in random win lose games. In the former case we prove that the uniform full mix is an o(1)-SuppNE, while in the case of win lose games, we show that (with high probability) there is either a PNE or a 0.5-SuppNE with support sizes only 2.