Simple approximate equilibria in large games
Simple approximate equilibria in large games
复制标题
大型博弈中的简单近似均衡
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
R. Peretz
中科院分区：
文献类型：
--
作者：
Y. Babichenko;Siddharth Barman;R. Peretz
我们证明了在每个参与人有m个行动的n人博弈中，存在一个近似纳什均衡，其中每个参与人在O（log m + log n）个纯行动集合中均匀随机化。这一结果引出了一个O（N log log N）时间算法，用于计算游戏中的近似纳什均衡，其中行动数量是玩家数量的多项式（m=poly(N)）；这里N=nmn是游戏的大小（输入大小）。此外，当动作数量为固定常数（m=O(1)）时，相同的算法运行时间为O（Nlog log log N）。此外，我们建立了博弈中纳什均衡的熵与使用随机抽样方法找到这样一个近似纳什均衡所需的时间之间的反比关系。我们还考虑了均衡的其他相关概念。具体地说，我们证明了在参与者数量n和每个参与者的行动数量m中存在支持大小多对数的近似相关均衡。特别是，使用概率方法，我们证明了存在多对数大小的行动轮廓的多集，使得该多集上的均匀分布形成了近似相关均衡。沿着类似的思路，我们建立了具有对数支持的近似粗相关平衡的存在性。我们通过考虑确定小支持近似平衡的计算复杂性来补充这些结果。我们证明了随机抽样可以有效地确定具有对数支持的近似粗相关平衡。但是，这种紧密的结果并不适用于相关平衡，也就是说，抽样可能会产生支持大小Ω(m)的近似相关平衡，其中m是每个玩家的行动数量。最后，我们表明，即使在两方零和博弈的情况下，在Cook约简下，找到具有最小可能支持的精确相关均衡也是np困难的。
We prove that in every normal form n-player game with m actions for each player, there exists an approximate Nash equilibrium in which each player randomizes uniformly among a set of O(log m + log n) pure actions. This result induces an O(N log log N)-time algorithm for computing an approximate Nash equilibrium in games where the number of actions is polynomial in the number of players (m=poly(n)); here N=nmn is the size of the game (the input size). Furthermore, when the number of actions is a fixed constant (m=O(1)) the same algorithm runs in O(Nlog log log N) time. In addition, we establish an inverse connection between the entropy of Nash equilibria in the game, and the time it takes to find such an approximate Nash equilibrium using the random sampling method. We also consider other relevant notions of equilibria. Specifically, we prove the existence of approximate correlated equilibrium of support size polylogarithmic in the number of players, n, and the number of actions per player, m. In particular, using the probabilistic method, we show that there exists a multiset of action profiles of polylogarithmic size such that the uniform distribution over this multiset forms an approximate correlated equilibrium. Along similar lines, we establish the existence of approximate coarse correlated equilibrium with logarithmic support. We complement these results by considering the computational complexity of determining small-support approximate equilibria. We show that random sampling can be used to efficiently determine an approximate coarse correlated equilibrium with logarithmic support. But, such a tight result does not hold for correlated equilibrium, i.e., sampling might generate an approximate correlated equilibrium of support size Ω(m) where m is the number of actions per player. Finally, we show that finding an exact correlated equilibrium with smallest possible support is NP-hard under Cook reductions, even in the case of two-player zero-sum games.