标题： 纳什、康利和计算：博弈动态中的不可能性和不完整性 显示英文标题

标题： Nash, Conley, and Computation: Impossibility and Incompleteness in Game Dynamics

摘要： 在什么条件下，反复进行游戏的玩家的行为会收敛到纳什均衡？ 如果假设玩家的行为是一个离散时间或连续时间的规则，其中当前的混合策略组合被映射到下一个策略组合，这便成为动力系统理论中的一个问题。 我们应用这一理论，特别是链重现、吸引子和康利指标的概念，证明了一个一般的不可能性结果：存在一些游戏，任何动态过程都必然存在不最终达到纳什均衡的起始点。 我们还证明了一个更强的结果，针对$\epsilon$-近似纳什均衡：存在一些游戏，没有任何游戏动态过程可以（以适当的方式）收敛到$\epsilon$-纳什均衡，事实上，这样的游戏集合具有正测度。 进一步的数值结果表明，这对于任何$\epsilon$在零和$0.09$之间的值都成立。 我们的结果表明，尽管纳什均衡（以及其计算启发的近似）的概念在所有游戏中都是普遍适用的，但它们作为长期行为预测工具从根本上来说是不完整的，无论选择何种动态过程。 显示英文摘要

摘要： Under what conditions do the behaviors of players, who play a game repeatedly, converge to a Nash equilibrium? If one assumes that the players' behavior is a discrete-time or continuous-time rule whereby the current mixed strategy profile is mapped to the next, this becomes a problem in the theory of dynamical systems. We apply this theory, and in particular the concepts of chain recurrence, attractors, and Conley index, to prove a general impossibility result: there exist games for which any dynamics is bound to have starting points that do not end up at a Nash equilibrium. We also prove a stronger result for $\epsilon$-approximate Nash equilibria: there are games such that no game dynamics can converge (in an appropriate sense) to $\epsilon$-Nash equilibria, and in fact the set of such games has positive measure. Further numerical results demonstrate that this holds for any $\epsilon$ between zero and $0.09$. Our results establish that, although the notions of Nash equilibria (and its computation-inspired approximations) are universally applicable in all games, they are also fundamentally incomplete as predictors of long term behavior, regardless of the choice of dynamics.