Computer Science – Computer Science and Game Theory
Scientific paper
2011-02-11
STOC 2009
Computer Science
Computer Science and Game Theory
extended version of paper of the same title that appeared in STOC 2009
Scientific paper
If a game has a Nash equilibrium with probability values that are either zero or Omega(1) then this equilibrium can be found exhaustively in polynomial time. Somewhat surprisingly, we show that there is a PTAS for the games whose equilibria are guaranteed to have small-O(1/n)-values, and therefore large-Omega(n)-supports. We also point out that there is a PTAS for games with sparse payoff matrices, which are known to be PPAD-complete to solve exactly. Both algorithms are of a special kind that we call oblivious: The algorithm just samples a fixed distribution on pairs of mixed strategies, and the game is only used to determine whether the sampled strategies comprise an eps-Nash equilibrium; the answer is yes with inverse polynomial probability. These results bring about the question: Is there an oblivious PTAS for Nash equilibrium in general games? We answer this question in the negative; our lower bound comes close to the quasi-polynomial upper bound of [Lipton, Markakis, Mehta 2003]. Another recent PTAS for anonymous games is also oblivious in a weaker sense appropriate for this class of games (it samples from a fixed distribution on unordered collections of mixed strategies), but its runtime is exponential in 1/eps. We prove that any oblivious PTAS for anonymous games with two strategies and three player types must have 1/eps^c in the exponent of the running time for some c>1/3, rendering the algorithm in [Daskalakis 2008] essentially optimal within oblivious algorithms. In contrast, we devise a poly(n) (1/eps)^O(log^2(1/eps)) non-oblivious PTAS for anonymous games with 2 strategies and any bounded number of player types. Our algorithm is based on the construction of a sparse (and efficiently computable) eps-cover of the set of all possible sums of n independent indicators, under the total variation distance. The size of the cover is poly(n) (1/ eps^{O(log^2 (1/eps))}.
Daskalakis Constantinos
Papadimitriou Christos H.
No associations
LandOfFree
On Oblivious PTAS's for Nash Equilibrium does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On Oblivious PTAS's for Nash Equilibrium, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Oblivious PTAS's for Nash Equilibrium will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-632156