# Mixed strategy nash equilibria in from $2\times N$ bimatrix form

I'm looking for a way of finding (manually!) mixed strategy Nash equilibria in a $2\times N$ game. Calling player 1 the player with two strategies and player 2 the one with $N$ strategies, I've constructed player 2's best response function, however this leaves me only half way and I'm unsure on how to continue.

Ideas?

-

You should construct an "upper envelope diagram" that describes the best response pure strategies and payoffs of player 2 against the mixed strategies of player 1. For an example, see the left part of figure 1 in the following paper:

D. Avis, G. Rosenberg, R. Savani, and B. von Stengel (2010), Enumeration of Nash equilibria for two-player games. Economic Theory 42, 9-37. http://www.maths.lse.ac.uk/Personal/stengel/ETissue/ARSvS.pdf

(That paper also includes a complete technical exposition of the general problem for m by n games.)

Here is an example of the upper envelope diagram for a 2x5 game, where player I has pure strategies A and B and player 2 has pure strategies a,..,e.

What you are interested in is the "vertices" of this upper envelope. The two vertices at the far left and right correspond to the best responses against the two pure strategies of player one (so for these vertices you just check if the corresponding strategy of player 1 is a best response to this best response of player 2).

Vertices between these correspond to mixed strategies of player 1 that make player 2 indifferent between (at least) two different pure strategies.

Suppose we are at such a vertex defined by the pure strategies of player 2 a and b. For this vertex you need to look at the two columns of player 1's payoff matrix that correspond to a and b and check if the best response of player 1 against a is different from the best response of player 1 against b (or is tied, but let's ignore that case for simplicity). If these two best responses to a and b differ then you can find a mixed strategy for player 2 that makes player 1 indifferent between his two pure strategies. Then this strategy of player 2, paired with the strategy of player 1 given by the point on the x-axis in the best response diagram, is a Nash equilibrium.

You need to check this for every vertex (for the example above, corresponding to {d} at the left, then {d,b},{b,a}, and {a,e} in the interior, and {e} on the far right). Checking the far left and far right vertices correspond to checking for pure Nash equilibria. Checking the "interior" vertices corresponds to looking for equilibria where both players use 2 pure strategies.

Things can be complicated by degeneracies in the payoffs, e.g., three lines meeting in one point on the upper envelope, but I won't go into that here.

To investigate this, you can use our software:

http://www.gametheoryexplorer.org/

-

For the zero-sum case you should look at Philip Straffin's book: Game Theory and Strategy, Part I, Chapter 3.

-
Unfortunately I'm looking for an approach to a non-zero-sum problem, but thanks, +1 – em70 Oct 13 '11 at 22:51