论文标题
无限 - 摩恩一通用随机游戏的复杂性
The Complexity of Infinite-Horizon General-Sum Stochastic Games
论文作者
论文摘要
我们研究了N-Player Infinite-Horizon General-Sum随机游戏中计算固定NASH平衡（NE）的复杂性。当每个玩家仅限于选择固定策略和奖励时，我们将重点放在计算NE的问题上。首先，我们证明计算此类NE在PPAD中（除了显然是PPAD-HARD之外）。其次，我们考虑基于回合的游戏专业，在每个状态下，最多都有一个玩家可以采取行动并表明这些（看似简单的）游戏仍然是ppad-hard。第三，我们表明，在多项式时间里，在这种基于回合的游戏中，在奖励计算中的进一步结构假设下。为了实现这些结果，我们建立了有关更广泛效用的随机游戏的结构性事实，包括单态单进取更改下实用程序的单调性，并减少每个玩家控制单个状态的设置。
We study the complexity of computing stationary Nash equilibrium (NE) in n-player infinite-horizon general-sum stochastic games. We focus on the problem of computing NE in such stochastic games when each player is restricted to choosing a stationary policy and rewards are discounted. First, we prove that computing such NE is in PPAD (in addition to clearly being PPAD-hard). Second, we consider turn-based specializations of such games where at each state there is at most a single player that can take actions and show that these (seemingly-simpler) games remain PPAD-hard. Third, we show that under further structural assumptions on the rewards computing NE in such turn-based games is possible in polynomial time. Towards achieving these results we establish structural facts about stochastic games of broader utility, including monotonicity of utilities under single-state single-action changes and reductions to settings where each player controls a single state.
