Mixed Strategy Simplification I am very consufed by the following problem.
Show that for any fixed $\epsilon > 0$ and any 2 player game with all non negative
payoffs, there is an $\epsilon$-approximate Nash equilibrium such that both players play the following simple kind of mixed strategy: For each player $j$ the strategy selects a subset $\hat{S_j}$ of at most $O(\log n)$ of player $j$th pure strategies, and makes player $j$ select one of the strategies in $\hat{S_j}$ uniformly at random. The set $\hat{S_j}$ may be a multi-set, i.e. may contain the same pure strategy more than once (such a strategy is more likely to be selected by a random choice). The constant in the $O(.)$ notation may depend on the given parameter $\epsilon$
Hint: consider any mixed Nash strategy with possibly large support, and try to simplify the support by selecting the subset $\hat{S_j}$ for the two players based on this Nash strategy.
The definition is very confusing, in other words the exercise asks somehow (maybe even randomly)  select the support  $\hat{S_j}$ of size $O(\log n)$, and somehow from the support select one pure strategy with is $\epsilon$-Nash equilibrium. The problem is I don't have idea how to approach the solution, the only reasonable answer is for $\epsilon$ infinite large take any action and this will be $\epsilon$ -Nash equilibrium.
If you have any idea how to solve please give a hint.
 A: To clarify the question: What they want is not a pure strategy that is an $\epsilon$-equilibrium. What they want is to take for each player a multiset of pure strategies -- so for example if the strategy space is $\{1,2,\dots,n\}$, maybe the multiset is $\{1,3,4,3,7,2,1,1\}$. Then the idea is that if each player is picking randomly from their own multiset $\hat{S}$, then this should be an $\epsilon$-equilibrium.
Now the question is how to select this multiset for each player (or show that correct choices exist).
This seems very tough to solve if you don't already know the answer ... let me give a first hint: Suppose I had a Nash equilibrium $(s_1,s_2)$. Then if each player randomly draws actions from her strategy, we know that in expectation, each maximizes expected value drawing from $s_i$. Think of this as saying that, as the number of draws/repeated plays goes to infinity, each is maximizing expected value. What if there were only a finite number of draws?
Your comments below are on the right track -- but instead of omitting pure strategies from the equilibrium strategy $s_i$, what if I just randomly draw a bunch of pure strategies according to $s_i$? (Maybe I draw $O(\log n)$ of them....)
So now, suppose I've drawn for each player a multiset of pure strategies by randomly sampling from $s_i$. Now most of the time these multi-sets are not going to be an $\epsilon$-Nash equilibrium. But I just need to show that sometimes, they are. That is, the probability that they are is nonzero. The original proof takes this approach, anyway. The paper is "Playing Large Games Using Simple Strategies" by Lipton, Markakis, and Mehta; spoiler alert! It contains the proof.
