论文标题
无限重复重复的两人游戏具有可计算策略的完整表征
A Complete Characterization of Infinitely Repeated Two-Player Games having Computable Strategies with no Computable Best Response under Limit-of-Means Payoff
论文作者
论文摘要
众所周知，对于无限重复的游戏，有一些可计算的策略具有最佳的响应，但没有可计算的最佳响应。这些结果最初是针对特定游戏（例如，囚犯的困境）或满足某些不确定既是必要又足够的某些条件的游戏类别的证明。 我们以简单和充分条件的形式得出一个完整的表征，以实现可计算策略的存在，而没有在均值限制下的可计算最佳响应。我们通过要求策略概况为NASH均衡或子游戏平均均衡，进一步完善表征，我们表明表征如何有效地确定是否有无限重复的游戏是否具有可计算的策略而没有可计算的最佳响应。
It is well-known that for infinitely repeated games, there are computable strategies that have best responses, but no computable best responses. These results were originally proved for either specific games (e.g., Prisoner's dilemma), or for classes of games satisfying certain conditions not known to be both necessary and sufficient. We derive a complete characterization in the form of simple necessary and sufficient conditions for the existence of a computable strategy without a computable best response under limit-of-means payoff. We further refine the characterization by requiring the strategy profiles to be Nash equilibria or subgame-perfect equilibria, and we show how the characterizations entail that it is efficiently decidable whether an infinitely repeated game has a computable strategy without a computable best response.
