Games of fixed rank: a hierarchy of bimatrix games
Games of fixed rank: a hierarchy of bimatrix games
复制标题
固定等级的游戏：双矩阵游戏的层次结构
DOI：
10.1007/s00199-009-0436-2
复制
发表时间：
2005
期刊：
影响因子：
1.3
通讯作者：
T. Theobald
中科院分区：
文献类型：
--
作者：
R. Kannan;T. Theobald
本文提出并研究了一类双矩阵对策（A，B），其两个局中人的支付矩阵之和为秩k，其中k为常数.我们可以说这个博弈的秩是k。对于任何固定的k，秩k-对策类严格推广了零和对策类，但它是一般双矩阵对策的一个非常特殊的情况。我们研究这些游戏的表现力和算法行为。具体来说，我们表明，即使k = 1的纳什均衡的这些游戏可以由一个任意大数目的连接组件。虽然问题的确切多项式时间算法找到一个纳什均衡仍然开放的游戏固定秩，我们提出了多项式时间算法找到一个ε-近似。
We propose and investigate a hierarchy of bimatrix games (A, B), whose (entry-wise) sum of the pay-off matrices of the two players is of rank k, where k is a constant. We will say the rank of such a game is k. For every fixed k, the class of rank k-games strictly generalizes the class of zero-sum games, but is a very special case of general bimatrix games. We study both the expressive power and the algorithmic behavior of these games. Specifically, we show that even for k = 1 the set of Nash equilibria of these games can consist of an arbitrarily large number of connected components. While the question of exact polynomial time algorithms to find a Nash equilibrium remains open for games of fixed rank, we present polynomial time algorithms for finding an ε-approximation.