I have a rather interesting exercise in Game Theory.

Assume there is a 2-players game, and player $i$ has $n_i$ pure strategies. The game is given by listing the payoffs for each player for each $n_1 × n_2$ possible plays.

Give a polynomial time algorithm to check if there is a Nash equilibrium for the game in which each player mixes between at most two strategies. Give a finite algorithm for finding a Nash equilibrium for general games with two players. Your algorithm may run in exponential time.

The answer to the first question hopefully can be solved by convex optimization.

In the second case some kind of exhauivet search can be used.

Unfortunately I don't know how to proceed.

  • $\begingroup$ What have you tried? Where did we get stuck? We expect you to make a serious effort on your own first. This is not the place to dump your homework exercise; we don't solve your exercise for you. However, if you have made a serious effort and have gotten stuck on some specific point, asking a narrowly focused question about that might be more suitable for this site. $\endgroup$ – D.W. Oct 29 '13 at 15:12

Hint: Given a mixed strategy for both players, how can you verify that it's a Nash equilibrium? How many potential strategies do you need to consider in both cases?

  • $\begingroup$ For given strategy of the opponent I need to find the best mixed strategy response, with support of size two, so there are $n^2_i$ cases to check. Right? $\endgroup$ – com Jul 1 '13 at 14:25
  • $\begingroup$ The definition of Nash equilibrium doesn't restrict the best response; the strategies forming the Nash equilibrium should be at least as good as any response. However, one thing that could help is that there is always a best response which is a pure strategy. $\endgroup$ – Yuval Filmus Jul 1 '13 at 15:00
  • $\begingroup$ answer to the hint: given the mixed strategies for both players, I will check that the payoff of pure strategies in the support of mixed strategy have a maximal payoff (and of course the same for all pure strategies in the support) given the mixed strategy of the opponent. $\endgroup$ – com Jul 3 '13 at 15:38
  • $\begingroup$ the goal is reduced to find that the "maximal payoff" can have at most two pure strategies, the problem is I don't get how to show this from side of each player. $\endgroup$ – com Jul 3 '13 at 15:41
  • $\begingroup$ You just need to check all possible strategies of the type being considered. $\endgroup$ – Yuval Filmus Jul 3 '13 at 17:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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