Nash, Conley, and Computation: Impossibility and Incompleteness in Game Dynamics
Nash, Conley, and Computation: Impossibility and Incompleteness in Game Dynamics
复制标题
纳什、康利和计算：博弈动力学中的不可能性和不完备性
DOI：
--
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Kelly Spendlove
中科院分区：
文献类型：
--
作者：
Jason Milionis;Christos Papadimitriou;G. Piliouras;Kelly Spendlove
在什么条件下，重复博弈的参与人的行为会收敛到纳什均衡？如果假设参与者的行为是一个离散时间或连续时间的规则，从而当前的混合策略配置文件映射到下一个，这就成为动力系统理论中的一个问题。我们应用这个理论，特别是链递归，吸引子和康利指数的概念，证明了一个一般的不可能的结果：存在游戏，任何动态必然有起点，不结束在纳什均衡。我们还证明了一个更强的结果$\N $-近似纳什均衡：有游戏，没有游戏动态可以收敛（在适当的意义上）到$\N $-纳什均衡，事实上，这样的游戏集有积极的措施。进一步的数值结果表明，这适用于0和0.09 $之间的任何$\n $。我们的研究结果表明，虽然纳什均衡的概念（及其计算启发的近似）是普遍适用于所有的游戏，他们也从根本上不完整的长期行为的预测，无论选择的动态。
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.
最严格的生存：部分信息正则化学习下的稳定和不稳定平衡
DOI：
--
发表时间：
2021
期刊：
Conference on Learning Theory
影响因子：
--
作者：
Giannou, Angeliki;Vlatakis-Gkaragkounis, Emmanouil-Vasileios;Mertikopoulos, Panayotis
通讯作者：
Mertikopoulos, Panayotis
DOI：
10.4230/lipics.itcs.2019.27
发表时间：
2018-07
期刊：
--
影响因子：
--
作者：
C. Daskalakis;Ioannis Panageas
通讯作者：
C. Daskalakis;Ioannis Panageas
DOI：
10.3390/e20100782
发表时间：
2018-10-12
期刊：
Entropy (Basel, Switzerland)
影响因子：
--
作者：
Papadimitriou C;Piliouras G
通讯作者：
Piliouras G