Heinrich Torsten, Jang Yoojin, Mungo Luca, Pangallo Marco, Scott Alex, Tarbush Bassel, Wiese Samuel
Faculty for Economics and Business Administration, Chemnitz University of Technology, Chemnitz, Germany.
Institute for New Economic Thinking at the Oxford Martin School, University of Oxford, Oxford, UK.
Int J Game Theory. 2023;52(3):703-735. doi: 10.1007/s00182-023-00837-4. Epub 2023 Jun 14.
We analyze the performance of the best-response dynamic across all normal-form games using a random games approach. The playing sequence-the order in which players update their actions-is essentially irrelevant in determining whether the dynamic converges to a Nash equilibrium in certain classes of games (e.g. in potential games) but, when evaluated across all possible games, convergence to equilibrium depends on the playing sequence in an extreme way. Our main asymptotic result shows that the best-response dynamic converges to a pure Nash equilibrium in a vanishingly small fraction of all (large) games when players take turns according to a fixed cyclic order. By contrast, when the playing sequence is random, the dynamic converges to a pure Nash equilibrium if one exists in almost all (large) games.
我们采用随机博弈方法分析了所有正规形式博弈中最佳反应动态的性能。在某些类型的博弈（例如潜在博弈）中，玩家更新行动的顺序——即游戏顺序——在确定动态是否收敛到纳什均衡时基本上无关紧要，但是，当对所有可能的博弈进行评估时，收敛到均衡在很大程度上取决于游戏顺序。我们的主要渐近结果表明，当玩家按照固定的循环顺序轮流行动时，在所有（大型）博弈中，最佳反应动态收敛到纯纳什均衡的比例极小。相比之下，当游戏顺序是随机的时，如果几乎所有（大型）博弈中存在纯纳什均衡，那么动态就会收敛到该均衡。
