Discretized Multinomial Distributions and Nash Equilibria in Anonymous Games
Discretized Multinomial Distributions and Nash Equilibria in Anonymous Games
复制标题
匿名博弈中的离散多项分布和纳什均衡
DOI：
--
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
C. Papadimitriou
中科院分区：
文献类型：
--
作者：
C. Daskalakis;C. Papadimitriou
我们表明，有一个多项式时间近似方案，用于在匿名游戏中计算NASH Equilibria，并具有任何固定数量的策略（一种非常广泛而重要的游戏类），从而扩展了Daskalakis和Papadimitriou的两策略结果。近似保证。从更普遍的兴趣的概率结果来看：n独立单位向量的总和的分布，值范围超过{e1，...，ek}，其中EI是沿k-nimenional Euclidean Space的维度I的单位向量，可以通过另一组独立单元向量的总和的分布来近似，其获得每个值的概率是某些整数z的倍数，因此两个分布的变异距离最多是EPS，其中两个分布的差距是EPS在Z中的逆多项式和K的函数中受到逆转录，但不依赖于n。我们的概率结果指定了一个令人惊讶的稀疏EPSI覆盖 - 在总变化距离下 - 独立单位矢量的分布组集合，这本身就是感兴趣的。
We show that there is a polynomial-time approximation scheme for computing Nash equilibria in anonymous games with any fixed number of strategies (a very broad and important class of games), extending the two-strategy result of Daskalakis and Papadimitriou 2007. The approximation guarantee follows from a probabilistic result of more general interest: The distribution of the sum of n independent unit vectors with values ranging over {e1,...,ek}, where ei is the unit vector along dimension i of the k-dimensional Euclidean space, can be approximated by the distribution of the sum of another set of independent unit vectors whose probabilities of obtaining each value are multiples of 1/z for some integer z, and so that the variational distance of the two distributions is at most eps, where eps is bounded by an inverse polynomial in z and a function of k, but with no dependence on n. Our probabilistic result specifies the construction of a surprisingly sparse epsi-cover- under the total variation distance - of the set of distributions of sums of independent unit vectors, which is of interest on its own right.