标题： 共同达成：种群如何在重复博弈中获胜 显示英文标题

标题： Reach together: How populations win repeated games

摘要： 在重复博弈中，玩家在每一步同时选择行动。 我们考虑一个参数化的重复博弈设置，其中玩家形成任意大小的人口群体。 他们的效用函数编码了一个可达性目标。 问题是是否存在一种统一的联盟策略，使得玩家无论人口规模如何都能确保胜利。 我们使用代数工具证明该问题可以在多项式空间内解决。 首先，我们展示了一个有限半群，其元素总结了在有限人口规模区间上的策略。 然后，我们通过该半群中特定元素的存在来表征获胜策略的存在性。 最后，我们提供了匹配的复杂度下界，以得出结论：具有可达性目标的重复人口博弈是PSPACE完全的。 显示英文摘要

摘要： In repeated games, players choose actions concurrently at each step. We consider a parameterized setting of repeated games in which the players form a population of an arbitrary size. Their utility functions encode a reachability objective. The problem is whether there exists a uniform coalition strategy for the players so that they are sure to win independently of the population size. We use algebraic tools to show that the problem can be solved in polynomial space. First we exhibit a finite semigroup whose elements summarize strategies over a finite interval of population sizes. Then, we characterize the existence of winning strategies by the existence of particular elements in this semigroup. Finally, we provide a matching complexity lower bound, to conclude that repeated population games with reachability objectives are PSPACE-complete.