标题： 重复多玩家博弈中收益计算的状态聚类方法 显示英文标题

标题： State-clustering method of payoff computation in repeated multiplayer games

摘要： 直接互惠是一种众所周知的机制，可以解释合作如何在进化种群中出现并占优。 许多先前的研究已经探讨了多人博弈中合作的出现。 然而，大多数研究都使用数值或实验方法，而不是理论分析。 缺乏关于合作进化的理论工作是由于计算收益的高复杂性。 在本文中，我们提出了一种新方法，即状态聚类方法，用于计算重复博弈中的长期收益。 使用这种方法，在一个$n$人重复博弈中，计算复杂度从$O(2^n)$降低到$O(n^2)$，这使得计算大规模重复博弈的收益成为可能。 我们以无限和有限重复公共物品博弈为例，探讨合作的进化，以展示我们方法的有效性。 在这两种情况下，我们发现当协同因子足够大时，游戏参与人数的增加对合作的进化是有害的。 我们的工作为研究重复多人博弈中合作的进化提供了一种理论方法。 显示英文摘要

摘要： Direct reciprocity is a well-known mechanism that could explain how cooperation emerges and prevails in an evolving population. Numerous prior researches have studied the emergence of cooperation in multiplayer games. However, most of them use numerical or experimental methods, not theoretical analysis. This lack of theoretical works on the evolution of cooperation is due to the high complexity of calculating payoffs. In this paper, we propose a new method, namely, the state-clustering method to calculate the long-term payoffs in repeated games. Using this method, in an $n$-player repeated game, the computing complexity is reduced from $O(2^n)$ to $O(n^2)$, which makes it possible to compute a large-scale repeated game's payoff. We explore the evolution of cooperation in both infinitely and finitely repeated public goods games as an example to show the effectiveness of our method. In both cases, we find that when the synergy factor is sufficiently large, the increasing number of participants in a game is detrimental to the evolution of cooperation. Our work provides a theoretical approach to study the evolution of cooperation in repeated multiplayer games.