Nash Equilibrium of 2-players game

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 ﬁnite 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.

• 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. – D.W. Oct 29 '13 at 15:12

• 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? – com Jul 1 '13 at 14:25