Game Theory

 

 

II. Nash Equilibrium in Mixed Strategies

 

Last time we saw an example of a matrix game which has no NE. (from problem set one).

Consider the game, with solution

 

Strategy

L

R

T

(0,3)

(3,0)

B

(2,1)

(1,2)

 

If P1 reveals that they will play T, then P2 will play L, resulting in P1 have the worst possible payoff of 0.

 

Any play that P1 announces will result in them getting the worst possible payoff, but if they keep player 2 guessing they could perhaps better there situation. So it’s best for P1 to use some type of randomized method. It is of course the same situation for P2.

 

These random schemes to choose strategies are called mixed strategies.

 

We will first consider the case when a matrix game is a 2x2 matrix game.

 

In mixed strategies, each play picks a probability profile  P1=(p1,p2)=p and P2=(q1,q2)=q.

Such that p1,p2 ,q1,q2 are all nonnegative and p1+p2=1 and  q1+q2=1.

 

A Nash Equilibrium in Mixed Strategies is when neither player can improve there expected value, given that the other probability profile is fixed.

 

1st) given that P1=(p1,p2) and P2=(q1,q2). How do we compute each player’s expected

      value?

      We first need to give notation to the payoffs that players receive when a strategy is

      chosen.

      The payoffs for P1 are

A11

A12

A21

A22

 

       The payoffs for P2 are

B11

B12

B21

B22

 

      Then we find the equation for the expected pay of Π1(p,q) of P1 when P1 plays p and   

      P2 play q    

      to be  Π1(p,q)= p1(q1 A11 + q2 A12 ) + p2(q1 A21 + q2 A22 ).

 

      Then, similarly for P2 Π2(p,q)= q1(p1 B11 + p2 B12 ) + q2(p1B21 + p2 B22 ).

 

2nd) Recall that p1+p2=1 and  q1+q2=1. So replace p2 with 1- p1, q2 with 1- q1 in the

       equation for the expectations of P1 and P2.

3rd) Maximize each with respect to (w.r.t.) p1 , and q1 respectively by setting

      then any solution to this with p1 and q1 in [0,1] is a mixed strategies Nash Equilibrium, if no solution comes from this then go back and maximize Π1 and Π2 separately. 

 

Problem Set 3 :

Consider again the game, with solution (recall that it has no NE). Find the Nash Equilibrium in Mixed Strategies.

 

Strategy

L

R

T

(0,3)

(3,0)

B

(2,1)

(1,2)

 

 

 

End of Problem Set 3

 

When we arrive in the case that each profile is “pure” i.e. the game as a NE we get that p1 or p2 is 1 and that q1 or q2 is also 1.

It is always true that if a game has a pure or “dominant strategy” NE, that the mixed strategy NE will agree with it.

 

 

 

Problem Set 4 :

 

Recall the Prisoner’s Dilemma game (from Section I) and that it’s solution gives us a NE. Now work through the method described in this Lecture to find it’s mixed strategies NE, and you will find that it does indeed agree with the dominant strategies NE.

 

Can you extend this to cover the case when P1 has m strategies and P2 has n strategies?

 

End of Problem Set 4

 

Now, what about when P1 has m strategies and P2 has n strategies? Can we prove that this game always has a mixed strategies NE? Indeed we can. In fact this was one thing

 (proven in more generality) that the famous John Nash (depicted in the movie “Beautiful Mind”) proved in his 1951 paper entitle “Non-Cooperative Games”. Its reference is J.F.

Nash, Non-cooperative games, Annals of Mathematics 54 (1951), 286-295. Its probably to advanced for the students but if you were interested…

 

For a version that is accessible see [Owe, 127].

 

Notes for the proof:

1st) Set a proper notation

2nd) Take a particular transformation of the probability profile.

3rd) Show that this transformed probability profile is a mixed strategies NE if and only

             if the original one is

4th) Show that the transformation map T is linear and continuous

5th) Apply the Brouwer Fixed Point Theorem to T to find a fixed point and hence a mixed

            strategies NE.

            Brouwer Fixed Point Theorem : If T is a continuous map from a closed, bounded,

                        Convex, set into itself then it has a fixed point. For details check out

                        http://en.wikipedia.org/wiki/Brouwer_fixed_point_theorem

 

 

 

 

 

 

 

References and Further Reading:

1.C. D. Aliprantis, and S. K. Chakrabarti, Games and Decision Making, Oxford   

   University Press, New York, 2000.

2. J.F. Nash, Non-cooperative games, Annals of Mathematics 54 (1951), 286-295

3. G. Owen, Game Theory, 2nd Edition, Academic Press, New York & London, 1982.

4. P. Straffin, Game Theory and Strategy, The Mathematical Association of America, DC,

   1993.