Evolutionary Game Theory Squared: Evolving Agents in Endogenously Evolving Zero-Sum Games
Evolutionary Game Theory Squared: Evolving Agents in Endogenously Evolving Zero-Sum Games
复制标题
DOI：
10.1609/aaai.v35i13.17352
复制
发表时间：
2020-12
期刊：
影响因子：
--
通讯作者：
Stratis Skoulakis;Tanner Fiez;Ryan Sim;G. Piliouras;L. Ratliff
中科院分区：
文献类型：
--
作者：
Stratis Skoulakis;Tanner Fiez;Ryan Sim;G. Piliouras;L. Ratliff
进化博弈论和更普遍的游戏在线学习的主要范式是基于在给定固定静态游戏的情况下相互作用的动态代理群体之间的明显区别。在本文中，我们摆脱了动态代理和静态游戏之间的人为划分，介绍和分析一大类竞争环境，在这些环境中，代理和他们玩的游戏都会随着时间的推移而战略性地演变。我们重点关注可以说是最典型的博弈论设置——零和博弈（以及网络泛化）——以及研究最多的进化学习动态——复制器，乘法权重的连续时间模拟。智能体群体在零和竞争中相互竞争，这种竞争本身会向当前的群体混合方向发展。值得注意的是，尽管智能体和博弈存在混乱的共同进化，我们证明该系统表现出许多规律性。首先，该系统具有信息论风格的守恒定律，将所有代理和博弈的行为耦合起来。其次，该系统是庞加莱循环系统，实际上所有可能的代理和博弈初始化都位于循环轨道上，并且无限频繁地任意接近其初始条件。第三，时间平均代理行为和效用收敛于时间平均博弈的纳什均衡值。最后，我们提供了一种多项式时间算法，可以有效地预测任何此类共同演化网络游戏的时间平均行为。
The predominant paradigm in evolutionary game theory and more generally online learning in games is based on a clear distinction between a population of dynamic agents that interact given a fixed, static game. In this paper, we move away from the artificial divide between dynamic agents and static games, to introduce and analyze a large class of competitive settings where both the agents and the games they play evolve strategically over time. We focus on arguably the most archetypal game-theoretic setting---zero-sum games (as well as network generalizations)---and the most studied evolutionary learning dynamic---replicator, the continuous-time analogue of multiplicative weights. Populations of agents compete against each other in a zero-sum competition that itself evolves adversarially to the current population mixture. Remarkably, despite the chaotic coevolution of agents and games, we prove that the system exhibits a number of regularities. First, the system has conservation laws of an information-theoretic flavor that couple the behavior of all agents and games. Secondly, the system is Poincare recurrent, with effectively all possible initializations of agents and games lying on recurrent orbits that come arbitrarily close to their initial conditions infinitely often. Thirdly, the time-average agent behavior and utility converge to the Nash equilibrium values of the time-average game. Finally, we provide a polynomial time algorithm to efficiently predict this time-average behavior for any such coevolving network game.