Two Plus Two Publishing LLC Two Plus Two Publishing LLC
 

Go Back   Two Plus Two Poker Forums > Other Topics > Science, Math, and Philosophy

Notices

Science, Math, and Philosophy Discussions regarding science, math, and/or philosophy.

Reply
 
Thread Tools Display Modes
Old 01-21-2011, 09:49 AM   #1
newbie
 
Join Date: Sep 2010
Posts: 34
Mixed strategy Nash equilibria

Say that we have a simple 2x2 game of heads and tails with the payoffs

... H ..... T
H 1,-1 -1,1
T -1,1 1,-1

Then to determine the MSNE (mixed strategy nash eq) I just assign probabilities for one of the players, calculate the expected value etc. In this example let's say that I assign the probability p that the column players chooses H and probability q that he chooses T.

Then if the row player chooses H his expected payoff will be 1*p + (-1)*q
and if the row player chooses T his expected payoff will be (-1)*p + 1*q. Setting these expected payoffs equal we get that

p-q = -p+q , i.e. p=q.

Using the fact that p+q = 1 we easily get that p = q = 1/2. Then you just reverse and assign probabilities for the row player and you're done. Easy.

Now let's say that we expand the game to a 3x3 matrix, for example

... A ... B ... C
A 1,0 1,1 1,2
B 0,0 2,2 3,1
C 0,1 1,1 1,3

Now if we do the same by assigning probabilities p, q and r we get three expressions for the expected payoff, namely

p + q + r
2q + 3r
q+r

and also p + q + r = 1


I'm really stupid right now but which is the easiest way to solve this? Those 3 expressions are suppose to be equal and also fullfill p+q+r = 1. Anyone?
swe_suns is offline   Reply With Quote
Old 01-21-2011, 10:05 AM   #2
veteran
 
Join Date: Aug 2006
Location: By Choice...
Posts: 2,739
Re: Mixed strategy Nash equilibria

Quote:
Originally Posted by swe_suns View Post
p + q + r
2q + 3r
q+r

and also p + q + r = 1


I'm really stupid right now but which is the easiest way to solve this? Those 3 expressions are suppose to be equal and also fullfill p+q+r = 1. Anyone?
If they're all supposed to equal each other, you've got problems...specifically with the 2q+3r = q+r portion of the equations.

I do see one thing (if I understand the payoffs correctly). Check for dominated strategies you can eliminate--there's at least one and then you can check for others when those are eliminated. In fact, I think there is only one NE, and it isn't a mixed strategy--and that's something provable.

Edit, I'm assuming that the payoffs are written as row_player, column_player, which I think works with your first example.
................... is offline   Reply With Quote
Old 01-21-2011, 10:14 AM   #3
newbie
 
Join Date: Sep 2010
Posts: 34
Re: Mixed strategy Nash equilibria

In the 3x3 example I just made up some numbers. The real problem is this one:

...A...B...C
A 7,0 2,5 0,7
B 5,2 3,3 5,2
C 0,7 2,5 7,0

So in this example we get (using probabilities for the column player p,q,r in that order)

7p + 2q
5p + 3q + 5r
2q + 7r

with p + q + r = 1

Putting the first and the 3rd expression equal we get that

7p + 2q = 7r + 2q , i.e. p = r

This leads to

7p + 2q
10p + 3q
7p + 2q

i.e. we can eliminate one equation. We end up with

7p + 2q
10p + 3q

which should be equal,

7p + 2q = 10p + 3q <=> 3p + q = 0 <=> p = (-1/3)q

Using p + q + r = {p = r} = 2p + q = 1

we get

2*(-1/3)q + q = 1

i.e. (1/3)q = 1

i.e. q = 3

Which would mean that

p = -1
q = 3
r = -1

Obviously p,q and r should lie inbetween 0 and 1 so what am I doing wrong?

btw the only PSNE (pure nash eq) is B,B which isn't hard to see. Does my solution to find a MSNE mean that there isn't one?
swe_suns is offline   Reply With Quote
Old 01-21-2011, 11:10 AM   #4
veteran
 
Join Date: Aug 2006
Location: By Choice...
Posts: 2,739
Re: Mixed strategy Nash equilibria

A couple of things...Nash (1950?) showed there has to be at least one NE in any game. We've found BB is a NE as you said, so there's the one we're guaranteed. Iterated elimination of dominated strategies can't eliminate any strategy in this case (even using a combination of the other two strategies as a 'dominant' strategy), so we are left with the 3x3.

I am pretty sure it's true that your attempt to find a mixed strategy NE resulting in non-nonsensical quantities for the probabilities means that a mixed strategy doesn't exist for this game. The one hang-up in the back of my mind would be this: what if we forced r = 0 for instance...then could we find p and q that satisfy the conditions for a mixed strategy *and* playing C would result in a lower utility than the expected utility of the mixed strategy. I am pretty sure that this case would be included in the more general solution you tried, but I am not 100% sure.
................... is offline   Reply With Quote
Old 01-21-2011, 11:44 AM   #5
journeyman
 
Join Date: Dec 2005
Posts: 277
Re: Mixed strategy Nash equilibria

Quote:
Originally Posted by swe_suns View Post
Does my solution to find a MSNE mean that there isn't one?
In this case yes, and in general as long as you didn't make any mistakes yes. Basically, in this particular game, in order to make our opponent indifferent between A and C, we must ourselves be using A and C in equal amounts. Having deduced that, we've effectively reduced the number of strategies to two-playing B or playing a 50-50 mix of A/C and we need some mixture of the two that works. However, against these two strategies, B is a dominant response. Hence there can be no mixed strategy equilibrium since no mixture will make your opponent indifferent among best responses (which is necessary for him to be willing to mix himself.)

In general, the easiest way to solve these is to immediately plug in the constraint (i.e. r=1-p-q). Now we have three expressions (involving two unknowns) that must all be equal. Select two pairs of them and we now have two equations with two unknowns, something we know how to solve. If no solution exists between 0 and 1, then something must be wrong with the original problem, i.e. that there is no mixed strategy equilibrium involving all three strategies.
MathEconomist is offline   Reply With Quote
Old 01-21-2011, 11:55 AM   #6
journeyman
 
Join Date: Dec 2005
Posts: 277
Re: Mixed strategy Nash equilibria

I should clarify-your failure to find an answer here means there is no MSNE where all three strategies are being used. It remains to verify whether or not there exists a MSNE where one or both players use only two strategies.
MathEconomist is offline   Reply With Quote

Reply
      

Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are Off
Pingbacks are Off
Refbacks are Off



All times are GMT -4. The time now is 04:01 PM.


Powered by vBulletin®
Copyright ©2000 - 2014, Jelsoft Enterprises Ltd.
Content Relevant URLs by vBSEO 3.6.0 ©2011, Crawlability, Inc.
Copyright 2008-2010, Two Plus Two Interactive