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.
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?