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

Thanks in advance!

share|improve this question
add comment

2 Answers

up vote 1 down vote accepted

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.

Upper envelope diagram

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/

share|improve this answer
add comment

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

share|improve this answer
    
Unfortunately I'm looking for an approach to a non-zero-sum problem, but thanks, +1 –  emaster70 Oct 13 '11 at 22:51
add comment

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.