Milionis Jason, Papadimitriou Christos, Piliouras Georgios, Spendlove Kelly
Department of Computer Science, Columbia University, New York, NY 10027.
Google DeepMind, London EC4A 3TW, United Kingdom.
Proc Natl Acad Sci U S A. 2023 Oct 10;120(41):e2305349120. doi: 10.1073/pnas.2305349120. Epub 2023 Oct 5.
The Nash equilibrium-a combination of choices by the players of a game from which no self-interested player would deviate-is the predominant solution concept in game theory. Even though every game has a Nash equilibrium, it is not known whether there are deterministic behaviors of the players who play a game repeatedly that are guaranteed to converge to a Nash equilibrium of the game from all starting points. 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 question becomes a problem in the theory of dynamical systems. We apply this theory, and in particular Conley index theory, to prove a general impossibility result: There exist games, for which all game dynamics fail to converge to Nash equilibria from all starting points. The games which help prove this impossibility result are degenerate, but we conjecture that the same result holds, under computational complexity assumptions, for nondegenerate games. We also prove a stronger impossibility result for the solution concept of approximate Nash equilibria: For a set of games of positive measure, no game dynamics can converge to the set of approximate Nash equilibria for a sufficiently small yet substantial approximation bound. Our results establish that, although the notions of Nash equilibrium and its computation-inspired approximations are universally applicable in all games, they are fundamentally incomplete as predictors of long-term player behavior.
纳什均衡——博弈中参与者的一种选择组合,没有自利的参与者会偏离该组合——是博弈论中占主导地位的解概念。尽管每个博弈都有一个纳什均衡,但尚不清楚反复进行博弈的参与者的确定性行为是否能保证从所有起始点收敛到该博弈的纳什均衡。如果假设参与者的行为是一种离散时间或连续时间规则,即当前的混合策略配置被映射到下一个,那么这个问题就变成了动力系统理论中的一个问题。我们应用该理论,特别是康利指标理论,来证明一个一般性的不可能性结果:存在一些博弈,对于这些博弈,所有博弈动态都无法从所有起始点收敛到纳什均衡。有助于证明这个不可能性结果的博弈是退化的,但我们推测,在计算复杂性假设下,对于非退化博弈同样的结果也成立。我们还针对近似纳什均衡的解概念证明了一个更强的不可能性结果:对于一组正测度的博弈,对于足够小但相当可观的近似界限,没有博弈动态能够收敛到近似纳什均衡集。我们的结果表明,尽管纳什均衡及其受计算启发的近似概念在所有博弈中普遍适用,但作为长期参与者行为的预测器,它们从根本上是不完整的。