Playing Anonymous Games using Simple Strategies
Playing Anonymous Games using Simple Strategies
复制标题
使用简单策略玩匿名游戏
DOI：
10.1137/1.9781611974782.40
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Alistair Stewart
中科院分区：
文献类型：
--
作者：
Yu Cheng;Ilias Diakonikolas;Alistair Stewart
我们研究了匿名游戏中计算近似纳什均衡的复杂性。我们的主要算法结果如下：对于任何策略数量有限且常数 $\delta>0$ 的 $n$ 玩家匿名游戏，可以在多项式时间内计算 $O(1/n^{1-\delta})$ 近似纳什均衡。补充这个积极的结果，我们表明，如果存在任何常数 $\delta>0$ 使得可以在多项式时间内计算 $O(1/n^{1+\delta})$ 近似平衡，则该问题存在一个完全多项式时间近似方案。
我们还提出了一种更快的算法，对于任何 $n$ 玩家 $k$ 策略匿名游戏，运行时间为 $\tilde O((n+k) k n^k)$ 并计算 $\tilde O(n^{-1/3} k^{11/3})$ 近似均衡。该算法源于匿名游戏的简单近似均衡的存在，其中每个玩家以概率 $1-\delta$ 玩一种策略，对于一些小的 $\delta$，并以概率 $\delta$ 均匀随机玩。
我们的方法利用了匿名游戏中的纳什均衡与泊松多项分布（PMD）之间的联系。具体来说，我们证明了一个新的概率引理，建立以下内容：两个 PMD，在每个方向上具有较大方差，其前几个矩近似匹配，在总变化距离上接近。我们的结构结果通过提供方差界限和匹配矩数量之间的平滑权衡来加强之前的工作。
We investigate the complexity of computing approximate Nash equilibria in anonymous games. Our main algorithmic result is the following: For any $n$-player anonymous game with a bounded number of strategies and any constant $\delta>0$, an $O(1/n^{1-\delta})$-approximate Nash equilibrium can be computed in polynomial time. Complementing this positive result, we show that if there exists any constant $\delta>0$ such that an $O(1/n^{1+\delta})$-approximate equilibrium can be computed in polynomial time, then there is a fully polynomial-time approximation scheme for this problem.
We also present a faster algorithm that, for any $n$-player $k$-strategy anonymous game, runs in time $\tilde O((n+k) k n^k)$ and computes an $\tilde O(n^{-1/3} k^{11/3})$-approximate equilibrium. This algorithm follows from the existence of simple approximate equilibria of anonymous games, where each player plays one strategy with probability $1-\delta$, for some small $\delta$, and plays uniformly at random with probability $\delta$.
Our approach exploits the connection between Nash equilibria in anonymous games and Poisson multinomial distributions (PMDs). Specifically, we prove a new probabilistic lemma establishing the following: Two PMDs, with large variance in each direction, whose first few moments are approximately matching are close in total variation distance. Our structural result strengthens previous work by providing a smooth tradeoff between the variance bound and the number of matching moments.