Average Case Performance of Replicator Dynamics in Potential Games via Computing Regions of Attraction
Average Case Performance of Replicator Dynamics in Potential Games via Computing Regions of Attraction
复制标题
通过计算吸引区域计算潜在博弈中复制器动力学的平均案例性能
DOI：
10.1145/2940716.2940784
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
G. Piliouras
中科院分区：
文献类型：
--
作者：
Ioannis Panageas;G. Piliouras
完全理解自适应代理网络的行为意味着什么？黄金标准通常是潜在游戏中学习动态的行为，其中许多进化动态，例如，复制动力学，是已知的收敛到均衡集。即使在这样的经典环境中，许多问题仍然没有答案。我们研究的问题，如：逐点收敛：系统是否总是平衡，即使在存在连续的平衡？计算吸引区域：给定逐点收敛，我们可以计算每个平衡点的渐近稳定区域（例如，估计其体积、几何形状）？系统不变：不变函数在沿着每个系统轨迹上保持不变。这个概念与博弈论中的势函数概念是正交的，势函数总是严格地沿着沿着系统轨迹增加/减少。势博弈中的动力学是否表现出不变函数？如果有，有多少？这些功能看起来如何？基于这些几何特征，我们提出了一个新的定量分析框架，潜在的游戏与许多均衡的效率。不同的平衡的预测加权的概率下出现的进化动力学一致随机的初始条件。这种平均情况下的分析提供了新的见解，在经典的博弈论的挑战，包括量化的风险优势，在猎鹿游戏，并允许更细致入微的性能分析，在网络协调和拥塞游戏之间的价格稳定和价格的无政府状态的巨大差距。CCS概念：计算理论！博弈论中的解概念;博弈中的收敛和学习;
What does it mean to fully understand the behavior of a network of adaptive agents? The golden standard typically is the behavior of learning dynamics in potential games, where many evolutionary dynamics, e.g., replicator dynamics, are known to converge to sets of equilibria. Even in such classic settings many questions remain unanswered. We examine issues such as: Point-wise convergence: Does the system always equilibrate, even in the presence of continuums of equilibria? Computing regions of attraction: Given point-wise convergence can we compute the region of asymptotic stability of each equilibrium (e.g., estimate its volume, geometry)? System invariants: Invariant functions remain constant along every system trajectory. This notion is orthogonal to the game theoretic concept of a potential function, which always strictly increases/decreases along system trajectories. Do dynamics in potential games exhibit invariant functions? If so, how many? How do these functions look like? Based on these geometric characterizations, we propose a novel quantitative framework for analyzing the efficiency of potential games with many equilibria. The predictions of different equilibria are weighted by their probability to arise under evolutionary dynamics given uniformly random initial conditions. This average case analysis is shown to offer novel insights in classic game theoretic challenges, including quantifying the risk dominance in stag-hunt games and allowing for more nuanced performance analysis in networked coordination and congestion games with large gaps between price of stability and price of anarchy. CCS Concepts: rTheory of computation! Solution concepts in game theory; Convergence and learning in games;