Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer
    
thank you for the answer, if I have only a finite number of draws the best what I can do is taking any action in support randomly, such that there is no way to opponent to predict my action,i.e. we have the same $p_i \cdot w_i$,where $p_i$-probability of action $i$ in mixed strategy, $w_i$-payoff of action $i$ for all action. The only reason for mixed strategy is to make opponent indifferent in playing his actions. Is this the right direction? –  user16168 Jun 13 '13 at 9:43
    
Now I am thinking about the hint in exercise, what if given the mixed Nash equilibrium we just omit some pure action from the mixed NE, or course it worsen the payoff, but if support is large enough, may be we could find approximation $\epsilon$, the main question is there are must be better and worsen actions to eliminate, how to find them? –  user16168 Jun 13 '13 at 9:53
    
@user16168 - see my edits! –  usul Jun 13 '13 at 16:51
    
OK, I see your point, but there few point I don't get, how exactly should I decide what actions to choice from the multiset? And how to show that what I choice is indeed $\epsilon$-NE –  user16168 Jun 14 '13 at 2:59
    
@user16168 - re-edited! –  usul Jun 14 '13 at 3:47

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.