论文标题
部分可观测时空混沌系统的无模型预测
Nash, Conley, and Computation: Impossibility and Incompleteness in Game Dynamics
论文作者
论文摘要
在什么条件下，反复玩游戏的玩家的行为会融合到NASH平衡？如果假设玩家的行为是一个离散的时间或连续时间规则，将当前的混合策略配置文件映射到下一个规则，则在动态系统理论中成为一个问题。我们应用了这个理论，尤其是链复发，吸引子和康利索引的概念，以证明一个普遍的不可能结果：存在任何动态的游戏必然会具有最终无法达到NASH平衡的起点。对于$ε$ -Approximate Nash Equilibria来说，我们还证明了更强大的结果：有些游戏使得没有游戏动力可以（从适当意义上）融合到$ε$ -Nash Equilibria，实际上，此类游戏的集合具有积极的衡量标准。进一步的数值结果表明，这对于零至0.09 $之间的任何$ε$。我们的结果表明，尽管NASH均衡（及其计算启发的近似值）的概念普遍适用于所有游戏，但无论动力学选择如何，它们也是长期行为的预测指标。
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 $ε$-approximate Nash equilibria: there are games such that no game dynamics can converge (in an appropriate sense) to $ε$-Nash equilibria, and in fact the set of such games has positive measure. Further numerical results demonstrate that this holds for any $ε$ 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.
