We consider the question of whether, and in what sense, Wardrop equilibria provide a good approximation for Nash equilibria in atomic unsplittable congestion games with a large number of small players. We examine two different definitions of small players. In the first setting, we consider games where each player's weight is small. We prove that when the number of players goes to infinity and their weights to zero, the random flows in all (mixed) Nash equilibria for the finite games converge in distribution to the set of Wardrop equilibria of the corresponding nonatomic limit game. In the second setting, we consider an increasing number of players with a unit weight that participate in the game with a decreasingly small probability. In this case, the Nash equilibrium flows converge in total variation towards Poisson random variables whose expected values are Wardrop equilibria of a different nonatomic game with suitably-defined costs. The latter can be viewed as symmetric equilibria in a Poisson game in the sense of Myerson, establishing a plausible connection between the Wardrop model for routing games and the stochastic fluctuations observed in real traffic. In both settings we provide explicit approximation bounds, and we study the convergence of the price of anarchy. Beyond the case of congestion games, we prove a general result on the convergence of large games with random players towards Poisson games.
翻译:我们考虑的是,在与众多小球员一起的原子无法渗透的拥挤游戏中,Wardrop equilibria是否为Nash equilibria提供了与大量小球员一起的原子无法渗透的拥挤游戏中Nash equilibria提供了很好的近似。我们检查了两个小球员的不同定义。在第一个环境中,我们考虑的是每个球员体重小的游戏;我们考虑的是每个球员重量小的游戏。我们证明,当玩家数量达到无限和重量到零的游戏时,所有(混合的)有限游戏(混合的)Nash NAs equiliblibria 的随机流动会集中到相应的非原子游戏游戏中。在第二个背景下,我们考虑的是越来越多的有单位重量的球员参加游戏。在这个游戏中,一个单位重量的球员数量越来越小,但概率越来越小。在这种情况下,纳什平衡的球流将完全转向普瓦森随机变量,其预期值是不同的非原子游戏(混合游戏),其成本是适当的。在Myerson的博尔森游戏中可以被看成对称的平调,在战争的游戏游戏中,在战流模式上建立了一个合理的连接模式,我们之间,我们所观察到的极化的游戏中,我们所观察到的极化的游戏的造价统化。