## January 5 – Ron Peretz

December 30, 2013 by ilannehama

===================================================

Sunday January 5, 14:00-15:30 Rationality Center, top floor, seminar room

Approximate Nash Equilibria via Sampling

Speaker: Ron Peretz, LSE. http://ronprtz.droppages.com/

===================================================

We prove that in a normal form n-player game with m actions for each player, there exists an approximate Nash equilibrium where each player randomizes uniformly among a set of O(log m+log n) pure strategies. This result induces an N^{log logN} algorithm for computing an approximate Nash equilibrium in games where the number of actions is polynomial in the number of players (m = poly(n)), where N = nm^n is the size of the game (the input size). Furthermore, when the number of actions is bounded (m = O(1)) the same algorithm runs in N^{log 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 algorithm.

joint work with Yakov Babichenko

### Like this:

Like Loading...

*Related*

## Leave a Reply