论文标题
随机潜在游戏
Stochastic Potential Games
论文作者
论文摘要
计算N-player非唑随机游戏的NASH平衡（NE）是一个巨大的挑战。当前，随机游戏理论中的算法方法无法在除极端情况下为随机游戏（SGS）计算NE，在这些情况下，玩家要么是一个团队的比赛，要么在两人设置中具有截然相反的目标。这极大地阻碍了SG框架在经济学和实际感兴趣系统中的许多问题上的应用。在本文中，我们提供了一种计算非零和设置中NASH平衡的方法，以及两个以上玩家的种群。特别是，我们确定了称为随机潜在游戏（SPG）的SGS的子集，在该游戏中，（Markov Perfect）NASH平衡可以在多项式时间内易于计算。与SGS一般而言，计算NE的SG是Pspace-Hard，我们表明具有潜在属性的SG是P的。我们进一步证明，对于每个SPG，都有一个双马尔可夫决策过程，其解决方案与SPG的MP-NE一致。最后，我们提供算法，可以随时计算具有两个以上播放器的SGS的MP-NE。
Computing the Nash equilibrium (NE) for N-player non-zerosum stochastic games is a formidable challenge. Currently, algorithmic methods in stochastic game theory are unable to compute NE for stochastic games (SGs) for settings in all but extreme cases in which the players either play as a team or have diametrically opposed objectives in a two-player setting. This greatly impedes the application of the SG framework to numerous problems within economics and practical systems of interest. In this paper, we provide a method of computing Nash equilibria in nonzero-sum settings and for populations of players more than two. In particular, we identify a subset of SGs known as stochastic potential games (SPGs) for which the (Markov perfect) Nash equilibrium can be computed tractably and in polynomial time. Unlike SGs for which, in general, computing the NE is PSPACE-hard, we show that SGs with the potential property are P-Complete. We further demonstrate that for each SPG there is a dual Markov decision process whose solution coincides with the MP-NE of the SPG. We lastly provide algorithms that tractably compute the MP-NE for SGs with more than two players.
