Bilinear Games: Polynomial Time Algorithms for Rank Based Subclasses
Bilinear Games: Polynomial Time Algorithms for Rank Based Subclasses
复制标题
双线性游戏：基于排名的子类的多项式时间算法
DOI：
--
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
R. Mehta
中科院分区：
文献类型：
--
作者：
J. Garg;A. Jiang;R. Mehta
受Koller等人[16]序列形式公式的启发，本文考虑了由两个支付矩阵（A，B）和紧多面体策略集表示的双线性博弈。双线性游戏非常普遍，涵盖了许多有趣的游戏类别，包括双矩阵游戏、两人贝叶斯游戏、多矩阵游戏和具有完美回忆的两人扩展形式游戏作为特殊情况，因此通常很难求解。对于一个双线性博弈，我们定义了它的最佳反应多面体（BRP），并将其纳什均衡刻画为BRP的全标号对。一个博弈（A，B）的秩被定义为秩（A +B）。在本文中，我们给出了多项式时间算法计算纳什均衡的（i）秩-1游戏，（ii）FPTAS的常秩游戏，（iii）当秩（A）或秩（B）是常数。
Motivated by the sequence form formulation of Koller et al. [16], this paper considers bilinear games , represented by two payoff matrices (A ,B ) and compact polytopal strategy sets. Bilinear games are very general and capture many interesting classes of games including bimatrix games, two player Bayesian games, polymatrix games, and two-player extensive form games with perfect recall as special cases, and hence are hard to solve in general. For a bilinear game, we define its best response polytopes (BRPs) and characterize its Nash equilibria as the fully-labeled pairs of the BRPs. Rank of a game (A ,B ) is defined as rank (A +B ). In this paper, we give polynomial-time algorithms for computing Nash equilibria of (i ) rank-1 games, (ii ) FPTAS for constant-rank games, and (iii ) when rank (A ) or rank (B ) is constant.
影响因子：
1.3
作者：
Avis, David;Rosenberg, Gabriel D.;von Stengel, Bernhard
通讯作者：
von Stengel, Bernhard