Fast Convergence of Best-Reply Dynamics in Aggregative Games
研究了大量玩家参与的聚合博弈，提出一种最优反应动态，能在准线性步数内达到近似纳什均衡，且均衡出现的极限频率随玩家数指数趋近于1。
We consider small-influence aggregative games with a large number of players n. For this class of games we present a best-reply dynamic with the following two properties. First, the dynamic reaches Nash approximate equilibria in quasi-linear (in n) number of steps, and the quasi-linear bound is tight. Second, Nash approximate equilibria are played by the dynamic with a limit frequency that is exponentially (in n) close to 1.