Computer Science – Computer Science and Game Theory
Scientific paper
2008-08-20
Computer Science
Computer Science and Game Theory
In the 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008
Scientific paper
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, e2, ...,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 eps-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.
Daskalakis Constantinos
Papadimitriou Christos H.
No associations
LandOfFree
Discretized Multinomial Distributions and Nash Equilibria in Anonymous Games 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 Discretized Multinomial Distributions and Nash Equilibria in Anonymous Games, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Discretized Multinomial Distributions and Nash Equilibria in Anonymous Games will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-609795