Wiese Samuel C, Heinrich Torsten
Department of Computer Science, University of Oxford, Oxford, OX1 3QD UK.
Institute for New Economic Thinking, University of Oxford, Oxford, OX1 3UQ UK.
Dyn Games Appl. 2022;12(2):689-700. doi: 10.1007/s13235-021-00401-3. Epub 2021 Oct 19.
We calculate the frequency of games with a unique pure strategy Nash equilibrium in the ensemble of -player, -strategy normal-form games. To obtain the ensemble, we generate payoff matrices at random. Games with a unique pure strategy Nash equilibrium converge to the Nash equilibrium. We then consider a wider class of games that converge under a best-response dynamic, in which each player chooses their optimal pure strategy successively. We show that the frequency of convergent games with a given number of pure Nash equilibria goes to zero as the number of players or the number of strategies goes to infinity. In the 2-player case, we show that for large games with at least 10 strategies, convergent games with multiple pure strategy Nash equilibria are more likely than games with a unique Nash equilibrium. Our novel approach uses an -partite graph to describe games.
我们计算了在n玩家、m策略正规形式博弈集合中具有唯一纯策略纳什均衡的博弈频率。为了得到该集合，我们随机生成收益矩阵。具有唯一纯策略纳什均衡的博弈会收敛到纳什均衡。然后，我们考虑一类更广泛的在最佳响应动态下收敛的博弈，其中每个玩家依次选择其最优纯策略。我们证明，随着玩家数量或策略数量趋于无穷大，具有给定数量纯纳什均衡的收敛博弈频率趋于零。在两人博弈的情况下，我们表明，对于至少有10个策略的大型博弈，具有多个纯策略纳什均衡的收敛博弈比具有唯一纳什均衡的博弈更有可能出现。我们的新方法使用n部图来描述博弈。
