Topic Choices (Puzzles and Game Theory)

[James Crook]

Jonathan,

Please create a page for 

http://onlinemathcircle.com/wiki/index.php?title=Puzzles_and_Game_Theory

To confirm you'd like to choose this as your topic. 

--James

Whether or not you choose that as your topic, I want to describe a game that will illustrate:

isomorphism

and

alpha-beta search

It's not going to be too important who wins this game, but the two concepts are important.

The game is called 15's.  Two people take it in turns to pick a whole number between 1 and 9 inclusive.

Each number can only be picked once.

A player wins if among the numbers they have picked 3 of the numbers add up to 15.

So for example you could pick 9

I pick 2

You pick 5

I pick 3

You pick 6

I pick 4

You pick 1 

and you have won because 9+5+1=15

Do you understand the rules?

If you do, we'll play this game by e-mail.  I'll go first and I choose 4.  (I've played 15's before, and I know what numbers are good choices).  It's your turn now.

You are welcome to talk by e-mail with other people in the study group and exchange opinions and advice about what number to choose - but I'd like you to do so off list, in particular don't include me in that strategic discussion, so as to make sure I don't know in advance what strategy you may be using!  

Jonathan, what number do you want to pick?  

--James.

[Jonathan Joo]

Ok then, I choose the number 5.

---

From: James Crook <james....@gmail.com>
To: l2lea...@googlegroups.com
Sent: Wednesday, June 29, 2011 2:52 PM
Subject: Topic Choices (Puzzles and Game Theory)

[James Crook]

The best choice.

I choose 6

--James

[Jonathan Joo]

All right, my next choice is 3.

-Jonathan 

---

From: James Crook <james....@gmail.com>
To: l2lea...@googlegroups.com

Sent: Wednesday, June 29, 2011 5:47 PM
Subject: Re: Topic Choices (Puzzles and Game Theory)

[James Crook]

My choice is 7

--James.

[Jonathan Joo]

I choose 2

-Jonathan

---

From: James Crook <james....@gmail.com>
To: l2lea...@googlegroups.com

Sent: Thursday, June 30, 2011 4:31 AM

[James Crook]

I choose 8.

--James

[Jonathan Joo]

I choose 1

-Jonathan

---

From: James Crook <james....@gmail.com>
To: l2lea...@googlegroups.com

Sent: Thursday, June 30, 2011 11:30 AM

[James Crook]

I choose 9, and it's a draw.

Now - why did I mention 'isomorphism'?  

--James.

[Jonathan Joo]

Hmm... not too sure about isomorphism, but I can see where alpha-beta pruning is used in this game.

Whenever a choice is made, you can eliminate all combinations of integers that add up to 15 that include the number that was chosen. Thus, each time a new number is chosen, the number of winning combinations is cut down by a lot! Thus, in making your next move, you only need to consider the integers remaining, instead of all 9 digits you started out with, thus increasing the efficiency (as already chosen numbers do not have to be searched further to figure out all possible combinations).

As for isomorhpism- is it because each choice corresponds with a different integer that would "block" the other person from achieving a score of 15? I don't know if I entirely understand what isomorphism is based on the wikipedia article. http://en.wikipedia.org/wiki/Isomorphism

Could you help me out for this one?

Thanks,

Jonathan

---

From: James Crook <james....@gmail.com>
To: l2lea...@googlegroups.com

Sent: Friday, July 1, 2011 2:05 AM

[James Crook]

Thanks Jonathan, 

Alpha beta is a bit craftier than just skipping moves that have become impossible.  We'll look at it in more detail shortly.

About isomorphism - there's an isomorphism because the game 15's has the same structure as a game you probably are already familiar with.  It just isn't at all obvious that it has the same structure - and that's why I used it as an example of isomorphism.

Write down the 9 numbers 1..9 and then circle the groups of three that sum to 15.  Rearrange to make the layout neater.  You should be able to find a very neat compact layout.  

When you play the game on this layout it should be easier to see what the best moves are.  It should also be clearer what game 15's is in disguise.

---

About Wikipedia - the secret with all Wikipedia maths articles is to know where to stop reading!  They are often great in the early paragraphs, and then explain more abstract variants that only make sense if you already know what they are talking about.  For what we are doing the isomorphism article is best in the 'purpose' paragraph and in the practical examples section.   At this stage it's 'encyclopedic' but not useful beyond that.

For the study group we can have study pages to make sense of any wikipedia page.  I've started one for the isomorphism page.  We can do this for other topics too as we meet them.

http://onlinemathcircle.com/wiki/index.php?title=Isomorphism  

It's just a starter page.  We'll extend it, with the example of 15's, and have a definition of group (on a new page) too, so that wikipedia gradually becomes more of a useful resource to us.  Wikipedia is great as a reference, but as it stands not good for learning.

---

If you don't spot what the game 15's is like with the hints, just say and I'll give the full detail.  Then we'll do Nash equilibrium, which is at the core of game theory, and then alpha-beta.

--James.

[Jonathan Joo]

Hi James,

I tried doing what you said, and I think I got the answer- is the game isomorhpic to tic-tac-toe? It can sort of be represented visually, with the numbers located in the place of a magic square. Thus, 5 is the best choice, since it is in the "middle" of the tic-tac-toe board, and you want to choose the numbers that equal up to 15. So in essence, the number game was just another way of playing tic-tac-toe!

For the wikipedia article, how should I start it?

-Jonathan

---

From: James Crook <james....@gmail.com>
To: l2lea...@googlegroups.com

Sent: Sunday, July 3, 2011 7:59 PM

[James Crook]

Spot on.  15's is isomorphic to tic-tac-toe.

I'd like you to add a brief explanation of that to our isomorphism page

http://onlinemathcircle.com/wiki/index.php?title=Isomorphism

I've found that playing a corner square works better for me as the first move since 'everyone knows' how to draw when I go center first.  But tic-tac-toe should always end in a draw.  In a way it's quite surprising that it can easily be analysed completely when a first estimate is that there are at most 9! games.  Symmetry only reduces it by a factor of 8, which is 45,360 games - so being able to analyse it comes  down to most of those games being over well before all nine moves have been made.  How many positions do you need to consider to prove that tic-tac-toe is, with optimal play, a draw? 

I'd like to show another isomorphism.  Consider matrices of the form:

a  -b

b   a

under multiplication and addition.  You should find that these are exactly isomorphic to complex numbers, a+ib

the matrix 

0 -1

1  0

plays the role of i.  and its square is -I

multiplication of complex numbers is commutative, and all the matrices of the form 

a -b

b  a

commute with each other.

I'm not proposing starting writing articles on wikipedia, but we will create more pages on the OMC wiki, and we will write commentary about wikipedia topics on OMC wiki.

Have a look at wikipedia's

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

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

There is a lot of material irrelevant to us on those pages!   I'd like you to understand what the payoff matrices mean, and tell me in your own words what a 'mixed strategy' is.  We will then be finding a strategy for the zero sum game

      X  Y

A  10 -4

B   -7 3

You can choose A or B, I can choose X or Y.  The amounts shown are how much you win and how much I lose.

'Obviously' you should choose A all the time since you then expect to win 10 half the time and lose 4 half the time, on average winning 3 each game.

However I know you know that, so I will play Y all the time.  And I will gain 4 all the time and you will lose 4 each time.

So you knowing that I know that will now instead play B all the time, and win 3 all the time and I will lose 3 all the time... umm...  and so on...

So how do we resolve this with a mixed strategy?  We'll talk through finding what the stable mixed strategy is shortly, and whether this game is fair or not.

--James.

[Jonathan Joo]

For Tic-tac-toe to be a draw, wouldn't the first move be enough? Because with "optimal play", shouldn't tic-tac-toe always be a draw? Maybe I'm misunderstanding the question.

The matrix isomorphism was really interesting! I typed just a bit up on our wiki about that, but I thought it was really cool how matrices could be used to represent complex numbers.

Payoff matrices are just grids describing the possible outcomes for each player for a given choice. You look at Player A's choice, and Player B's choice, and see where the intersect on the matrix, and then you get the payoffs to each player.

Mixed strategies are when you don't play the same move each time, rather you assign probabilities to each choice so your choices are random (in a way) but are chosen in a certain ratio.

For the last problem, I believe it can be solved (for me) by choosing A 17/24 of the time, and B 7/24 of the time, based on the equation p = (d-b)/(a+d-b-c).

Hope everything makes sense,

-Jonathan

---

From: James Crook <james....@gmail.com>
To: l2lea...@googlegroups.com

Sent: Tuesday, July 5, 2011 5:52 AM

[James Crook]

On 5 July 2011 19:20, Jonathan Joo <jonath...@yahoo.com> wrote:

For Tic-tac-toe to be a draw, wouldn't the first move be enough? Because with "optimal play", shouldn't tic-tac-toe always be a draw? Maybe I'm misunderstanding the question.

Well, OK by that argument we don't need to play any moves at all.

I'm asking how many different positions would you need to present in a proof that neither player has a winning strategy?

How do you know for sure that I can't win by some fiendishly clever series of moves starting by playing an edge square?  Are you absolutely sure I don't have a forced win?

A proof that tic-tac-toe is a draw can use the symmetry to cut the number of positions to consider.

It can also use the fact that it is always an advantage to have a move to establish that if either player has a winning strategy then it is the first player.  (This is unlike chess, where it can on rare occasions be a bad thing to have a move - zugzwang).  Because of that you only need to prove that the first player does not have a winning strategy.

In a proof, you can stop a line of analysis when either there are three in or row, or there are no more opportunities on the board for three in a row.  The board may not be full for that.

So with all these ways of cutting down the number of moves to consider, we have a lot fewer than 45,360 positions to consider.  How few though?  Do we have to consider 10,000 positions to prove that tic-tac-toe, with optimal play, is always a draw?

 

The matrix isomorphism was really interesting! I typed just a bit up on our wiki about that, but I thought it was really cool how matrices could be used to represent complex numbers.

Thank you for writing it up.  It is really cool.

There is some absolutely astonishing maths that links group theory with the theory of matrices. 

 

It's particularly handy that matrices do not (in general) commute, because that means it is possible to also model non-commutative groups using matrices.  For example it is possible to represent the basic moves of a Rubik cube, which do not commute, as matrices, and then a sequence of moves is just matrix multiplication.

 

Payoff matrices are just grids describing the possible outcomes for each player for a given choice. You look at Player A's choice, and Player B's choice, and see where the intersect on the matrix, and then you get the payoffs to each player.

Mixed strategies are when you don't play the same move each time, rather you assign probabilities to each choice so your choices are random (in a way) but are chosen in a certain ratio.

For the last problem, I believe it can be solved (for me) by choosing A 17/24 of the time, and B 7/24 of the time, based on the equation p = (d-b)/(a+d-b-c).

In the right general area, but not actually correct.  If you choose A 17/24 of the time and B 7/24 of the time then I will choose Y all the time.

Your score will be on average

((17 * -4) + (7 * 3)) /24 = -47/24 which is approx -2.

provided I've done the sums right.  Please check that I have!

You can do better than that!

To really understand what is going on draw a sketch of the 3D graph of your expected winnings E given p (the probability you pick A with) and q (the probability I pick X with).  p is a quantity between 0 and 1.  So is q.  The way to draw the graph is to mark in quickly the value for E when p and q are 0,0; 0,1; 1,0 and 1,1.  These are easy because they are the values from the payoff matrix.  You can start to sketch  other values by using the fact that the payoff varies linearly if p is fixed and q varies, and equally it varies linearly if q is fixed and p varies.

I find it kind of astonishing and beautiful that this leads to a curved saddle shaped surface.  See the pictures on http://en.wikipedia.org/wiki/Ruled_surface I haven't a clue what some of the topics being talked about on that page like kodaira dimension are but the pictures of ruled surfaces on their own say most of what I want to say.

Anyway, after sketching you will have a visual guide to help you find your best value for p.  When you do, there will be nothing I can do when playing the game against you.  Even if I know your strategy you will win all the time (on average).

The sketch should help you set up the equations to solve correctly.  You'll see very quickly that for p near to 1 I have a strategy that beats you, and for p near to 0 I have a strategy that beats you.  It should be clear from the graph that p near to 17/24 also gives me a win when q= 0.  The graph gives you a way to check you are doing the calculation right, rather than blindly following a formula.  It also shows you another way to look at what a solution is.

Do the sketch, and if it's not helping you tell me what you tried.

(also if I've got my calculation wrong tell me that - I am anything but infallible).

Also for something we'll need soon have a look at 

http://onlinemathcircle.com/wiki/index.php?title=Markov_chains

and make some comment about that page so I know you've had a look.

It will become relevant shortly.

I've updated http://onlinemathcircle.com/wiki/index.php?title=L2_Study_Group/To_Do

I'm putting energy in where people are interacting.  

--James.

[Jonathan Joo]

Hi James,

For the tic-tac-toe problem, I drew out a bunch of scenarios and I believe that there can be a maximum of 2 empty spaces on a tic-tac-toe board to make sure there is a tie? If there are 3 or more empty spaces on the board, then it is possible for a player to win. I'm not sure how to prove this- it's just based on observations. 

I tried sketching the 3d graph on paper, and I got the saddle-like shape to appear, but I haven't gotten too far with it. I haven't taken calculus yet, so I am not yet familiar with how to utilize 3d graphs. Should the 3d graph have been made on the computer or on a calculator instead of on paper?

I also saw the page on markov chains, and it's interesting- I can't wait to see what's coming.

Thanks for the feedback!

Jonathan

---

From: James Crook <james....@gmail.com>
To: l2lea...@googlegroups.com

Sent: Tuesday, July 5, 2011 5:57 PM

[James Crook]

About the matrix isomorphism with complex numbers -
I should have mentioned:

The determinant of the matrix is 'the same thing' as the magnitude of the complex number, so the fact that det(A)det(B)=det(AB) implies that magnitudes of complex numbers multiply when you multiply complex numbers.

The transpose of a matrix is 'the same thing' as the conjugate of the complex number.  So the fact that det(transpose(A))=det(A) corresponds to the fact that magnitudes of complex numbers are also unchanged by taking the conjugate.

On 6 July 2011 09:34, Jonathan Joo <jonath...@yahoo.com> wrote:

Hi James,

For the tic-tac-toe problem, I drew out a bunch of scenarios and I believe that there can be a maximum of 2 empty spaces on a tic-tac-toe board to make sure there is a tie? If there are 3 or more empty spaces on the board, then it is possible for a player to win. I'm not sure how to prove this- it's just based on observations. 

It's a good idea, but unfortunately it's not true.

Try this position:

X O X
-  -  -
O X O

Then it is impossible for either player to win.  Mind you they both have to have been playing badly to reach this position!

It's much easier to count number of positions to consider by working from the start of the game.
We want to prove the first person can't win.

If he plays a corner, I play the centre, there are then 4 choices so 6 positions to consider so far... 

If at the start he plays the centre, I play a corner, there are then 4 choices so 6 positions so far...

If at the start he plays an edge I play the centre, there are then 4 choices so 6 positions so far, but I've seen 2 of those positions already....

So after 3 moves there are 16 positions we need to have considered, 10 of which have three moves played and need further analysis.  Continuing the analysis from these 10 positions it gets easier because many of the moves are forced....

Our move is next and after our move each of these positions has 5 moves still to play, so already a huge improvement on the 9!
 

I tried sketching the 3d graph on paper, and I got the saddle-like shape to appear, but I haven't gotten too far with it. I haven't taken calculus yet, so I am not yet familiar with how to utilize 3d graphs. Should the 3d graph have been made on the computer or on a calculator instead of on paper?

Sketching by hand is just fine, and more informative.

This problem solves nicely with calculus, but there is another way too.

Look for the values of p and q where the straight lines are horizontal.

Find that value of p and if I change my choice of q the expected score E does not change at all, because the line is horizontal.  So I am defenceless and have no counter strategy.

So write out the equation for E in terms of p and q.  Then rearrange it so that it is q*a(p) + b(p).  Where a(p) and b(p) are functions of p.  If you can make a(p) zero by a suitable choice of p then you have it.  Chose that p and q no longer has any effect whatsoever.  The expected score E will then be b(p) which - if it works out as I think it should - will be positive for this choice of p - and you'll be winning.  No matter what I do.

 

I also saw the page on markov chains, and it's interesting- I can't wait to see what's coming.

Brouwer fixed point theorem is coming soon, because it ties in with both Markov Chains and Nash equilibrium.

So a question...  I start on A in the first Markov Chains diagram.  After 8 moves, how likely am I to be on A?

Hint- consider 1 move, then 2 moves, then 4 moves, then 8 moves.

--James.

 

[Jonathan Joo]

Hi James,

I'm not too sure I understand what you mean with the tic-tac-toe moves and positions... if one player plays a corner and another plays the center, aren't there only 4 positions to consider? 

As for the 3d graphing- I don't yet know how to find a horizontal line or even how to plot the other points in a 3d graph. I plotted just the points (1,1,10), (-1,1,-7), (1,-1,-4) and (-1,-1,3).

How could I determine where a horizontal line would be from those four points?

 For the Markov Chains question, is the answer 63.636364 % ? I used the equation .6*.6 + .4*.7 to get the probability of landing on A the second move (.6 of the time, it will start at A and .6 chance of going from A-A, and .4 of the time, it will start at B and have a .7 chance of going back to A, thus .6*.6 + .4*.7, which is .64.)

I then used the .64 as the new value of the chances of starting out at A, and substituted it back into the above equation. (So .64*.6 + .36*.7) which is .636. I kept on repeating this and noticed that the pattern was .636363...etc. Taking it to the 8th term is .63636364, or 63.636364 %.

Hopefully this is correct,

Jonathan

---

From: James Crook <james....@gmail.com>
To: l2lea...@googlegroups.com

Sent: Wednesday, July 6, 2011 1:44 PM

[James Crook]

Hi jonathan,

On 7 July 2011 17:51, Jonathan Joo <jonath...@yahoo.com> wrote:

Hi James,

I'm not too sure I understand what you mean with the tic-tac-toe moves and positions... if one player plays a corner and another plays the center, aren't there only 4 positions to consider? 

The question was how many positions in total need to be considered to prove that tic-tac-toe is (with best play) a draw.

My solution to that is here:

http://onlinemathcircle.com/wiki/index.php?title=It%27s_a_draw

I haven't counted exactly, but it looks to be less than 150 positions.

 

As for the 3d graphing- I don't yet know how to find a horizontal line or even how to plot the other points in a 3d graph. I plotted just the points (1,1,10), (-1,1,-7), (1,-1,-4) and (-1,-1,3).

How could I determine where a horizontal line would be from those four points?

No, you should be plotting  (1,1,10), (0,1,-7), (1,0,-4) and (0,0,3) since p and q are probabilities and are between 0 and 1.

You should have no trouble also drawing in the lines for E when p=0, or when q=0, or when p=1 or when q=1.  For example there is a straight line joining (1,1,10) to (1,0,-4).  For this straight line p is constant and only q (and of course E) is varying.  You can quickly see from this that for p=1 and q=0.5 the point is (1,0.5, 3).  What equation did you get for E in terms of p and q?  That should give you the height of the graph at any p and q, i.e the points (p,q,E(p,q)).  After you've drawn in the straight lines for p=0 or 1, q=0 or 1, find the points for (p,q) = (0,0.5), (1,0.5), (0.5,0), (0.5,1), and then draw in the (again straight lines) first q=0.5, then p=0.5.

Without seeing the graph you draw I can't check you are doing it right, so send me the formula you got for E and I'll check that!

If you have the equation for E you can then look for a p for which E(p,0)=E(p,1).  With the right p that will be a constant horizontal line on your graph. For that p, E(p,q) will have the same value for all values of q between 0 and 1 inclusive.

 

 For the Markov Chains question, is the answer 63.636364 % ? I used the equation .6*.6 + .4*.7 to get the probability of landing on A the second move (.6 of the time, it will start at A and .6 chance of going from A-A, and .4 of the time, it will start at B and have a .7 chance of going back to A, thus .6*.6 + .4*.7, which is .64.)

I then used the .64 as the new value of the chances of starting out at A, and substituted it back into the above equation. (So .64*.6 + .36*.7) which is .636. I kept on repeating this and noticed that the pattern was .636363...etc. Taking it to the 8th term is .63636364, or 63.636364 %.

Almost...  I think you only took it to six steps though?

Each step we update 'x' to x*0.6+(1-x)*0.7 which is 0.7-0.1x.

so x goes 1, 0.6, 0,64, 0.636, 0.6364, 0.63636, 0.636364, 0.63636636, 0.6363636364

I think we agree on what happens if you take many many steps.  x will converge on a value such that

x = 0.7-0.1x and solving, that gives x = 7/11 = 0.63636363...

(and the probability of being in E would be 4/11 = 0.36363636...)

So let's move on to the next level.  How could we go about working out what the probability of ending up in each state 'after lots of moves' is for the larger Markov chain with 3 states?  Is there a way we can get an equation to solve out of it? 

 --James.

[James Crook]

Sorry!

It looks like I can't count:

 

.64*.6 + .36*.7) which is .636. I kept on repeating this and noticed that the pattern was .636363...etc. Taking it to the 8th term is .63636364, or 63.636364 %.

 

Almost...  I think you only took it to six steps though?
Each step we update 'x' to x*0.6+(1-x)*0.7 which is 0.7-0.1x.
so x goes 1, 0.6, 0,64, 0.636, 0.6364, 0.63636, 0.636364, 0.63636636, 0.6363636364

63.636364 %. is correct.  I went astray at step 7.

 

so x goes 1, 0.6, 0,64, 0.636, 0.6364, 0.63636, 0.636364, 0.6363636, 0.63636364

And expressed as a percentage, that's 63.636364%

--James.

[Jonathan Joo]

Hi James,

I've attempted the graph many many times, but I just can't seem to get it right. I also tried the steps you gave me- but I'm still stuck on figuring out the equation for E and trying to draw the graph in a way that I can actually understand it... I've spent a considerable amount of time trying to figure it out, but haven't gotten very far :(.

For the markov chains one, I noticed that percentage is the rate of changing from A to E or vice versa (.4 or .7) over the total changing (.4+.7=1.1) ending up with .4/1.1 or 4/11, and .7/1.1 or 7/11. So would the probability of ending up in each state for the second markov graph be .15/.425 (6/17), .25/.425 (10/17) and .025/.425 (1/17)?

-Jonathan

---

From: James Crook <james....@gmail.com>
To: l2lea...@googlegroups.com

Sent: Thursday, July 7, 2011 6:27 PM

Subject: Re: Topic Choices (Puzzles and Game Theory)

[James Crook]

OK.

Let's get the equation for your expected winnings E

      X  Y

A  10 -4

B   -7 3

You choose A with probability p, and you choose B with probability (1-p).

I choose X with probability q

[James Crook]

Darn it.  Gmail sent that last e-mail early, whilst I was typing.

OK.

Let's get the equation for your expected winnings E

      X  Y

A  10 -4

B   -7 3

You choose A with probability p, and you choose B with probability (1-p).

I choose X with probability q, and I choose Y with probability (1-q).

So AX with probability pq, AY with probability p(1-q), BX with probability (1-p)q and BY with probability (1-p)(1-q).

So the expected score is 

E(p,q) = 10pq - 4p(1-q) - 7(1-p)q + 3(1-p)(1-q)

Let's collect p and 1-p first.

E(p,q) = p( 10q -4(1-q)) + (1-p)( -7q + 3(1-q))

E(p,q) = p( 14q -4) + (1-p)( 3-10q)

Let's collect p

E(p,q) = p( 14q -4 + 10q -3) + ( 3-10q)

E(p,q) = p( 24q -7) + ( 3-10q)

E(p,q) = 24pq -7p -10q+3

That's our equation for E.  Let's do some quick checks to see we got it right.  

For p=1 q=1 we should get 10; OK 24-7-10+3 = 10.

For p=0,q=0 we should get 3.  We do.

For p=0, q=1 we get -7

For p=1, q=0 we get -4

If we choose any fixed value of p we get E is a linear equation in q.

If we choose any fixed value of q we get E is a linear equation in p.

E represents your winnings.  You want to choose a value of p so that E is always positive, no matter what the value of q.

Does p=0.5 do it?

E(p,q) = 24pq -7p -10q+3

E(0.5,q) = 12q -3.5 -10q+3 = 2q-0.5

No, if I choose q=0, i.e. if I always choose Y, you lose 0.5 on average.  Half the time you win 3 and half the time you lose 4.

You're looking for a value of p where E(p,q) is a constant, and does not depend on q.

--James.

[Jonathan Joo]

Hi James,

Thanks for your extremely comprehensive reply. I think I finally got the answer now- is it 10/24? When you substitute 10/24 for P, you end up with 10y-7(10/24)-10y+3, which simplifies to 70/24 + 3 or 1/12. Sorry it took so long for me to get this- but it was really helpful seeing how you arrived at the equation for E:

("You choose A with probability p, and you choose B with probability (1-p).

I choose X with probability q, and I choose Y with probability (1-q).

So AX with probability pq, AY with probability p(1-q), BX with probability (1-p)q and BY with probability (1-p)(1-q).

So the expected score is 

E(p,q) = 10pq - 4p(1-q) - 7(1-p)q + 3(1-p)(1-q)")

-Jonathan

---

From: James Crook <james....@gmail.com>
To: l2lea...@googlegroups.com

Sent: Friday, July 8, 2011 12:53 PM

[James Crook]

Yes, 10/24 is correct.  So is the Expected value E=1/12.

E(p,q) = 24pq -7p -10q+3

E(p,q) = q(24p-10) -7p +3

If p=10/24 the (24p-10) is zero and changing q has no effect whatsoever.  For this value of p we have:

E(10/24,q) = -70/24 +3 = 2/24 = 1/12

So each turn your expected win is 1/12, no matter what I choose for q.

Please write this up on the starter page along with explanation of what a 'mixed strategy' is:

http://onlinemathcircle.com/wiki/index.php?title=Nash_Equilibrium

Writing this up will be good for other people on OMC learning game theory, and also you'll start to learn LaTeX this way too.  Use <math>\frac{10}{24}</math> for fractions.  You're very welcome to cut and paste from what both you and I have written in our e-mails into that page where you think it helps, and that could be a quick way to get some more content written there.

----

About the graphs we've been discussing:

The format

10*x*y - 4*x*(1-y) - 7*(1-x)*y + 3*(1-x)*(1-y)

is probably best if plotting using an online 3D function grapher like:

http://www.livephysics.com/ptools/online-3d-function-grapher.php?ymin=0&xmin=0&zmin=Auto&ymax=1&xmax=1&zmax=Auto&f=10*x*y-4*x*%281-y%29-7*%281-x%29*y%2B3*%281-x%29*%281-y%29

because then you can vary the 10, the -4, the -7 the 3 and see how it affects the graph.  

I find it kind of odd that in the 3D graph for any fixed p we get a straight line, and that for any fixed q we get a straight line, but that the overall surface is curved.  If we draw a contour graph (think 3D graph as seen from above) and draw the contours E(p,q) = K for different constants K, most of the lines are curves.  [Plotting xy=K is mostly the same thing as plotting y=K/x, so it is no surprise that these lines of constant E are curves].  Think of K increasing as being like water level rising in a mountainous landscape.

A fair Game?

The fact that with the strategy p=5/12 your expected winnings are 1/12 each go means that it is not a "fair game" in that the person choosing A or B has an advantage over the person choosing X or Y.  It's a small margin for sure, but a margin none the less.

So a new question:

How can we adjust the parameters in the payoff matrix to make the game fair?  - and I don't mean making all four values zero!  I'd like to make it not too obvious at first sight whether the game is fair or whether it favors the AB chooser or the XY chooser.  

--James.

[Shri R Ganeshram]

I have been really slow on working through stuff. I should hopefully finish the 2nd section today.________________________________________
From: l2lea...@googlegroups.com [l2lea...@googlegroups.com] On Behalf Of James Crook [james....@gmail.com]
Sent: Saturday, July 09, 2011 6:31 AM
To: l2lea...@googlegroups.com

Subject: Re: Topic Choices (Puzzles and Game Theory)

Yes, 10/24 is correct. So is the Expected value E=1/12.

E(p,q) = 24pq -7p -10q+3
E(p,q) = q(24p-10) -7p +3

If p=10/24 the (24p-10) is zero and changing q has no effect whatsoever. For this value of p we have:

E(10/24,q) = -70/24 +3 = 2/24 = 1/12
So each turn your expected win is 1/12, no matter what I choose for q.

Please write this up on the starter page along with explanation of what a 'mixed strategy' is:
http://onlinemathcircle.com/wiki/index.php?title=Nash_Equilibrium

Writing this up will be good for other people on OMC learning game theory, and also you'll start to learn LaTeX this way too. Use <math>\frac{10}{24}</math> for fractions. You're very welcome to cut and paste from what both you and I have written in our e-mails into that page where you think it helps, and that could be a quick way to get some more content written there.

----

About the graphs we've been discussing:

The format
10*x*y - 4*x*(1-y) - 7*(1-x)*y + 3*(1-x)*(1-y)

is probably best if plotting using an online 3D function grapher like:

http://www.livephysics.com/ptools/online-3d-function-grapher.php?ymin=0&xmin=0&zmin=Auto&ymax=1&xmax=1&zmax=Auto&f=10*x*y-4*x*%281-y%29-7*%281-x%29*y%2B3*%281-x%29*%281-y%29

because then you can vary the 10, the -4, the -7 the 3 and see how it affects the graph.

I find it kind of odd that in the 3D graph for any fixed p we get a straight line, and that for any fixed q we get a straight line, but that the overall surface is curved. If we draw a contour graph (think 3D graph as seen from above) and draw the contours E(p,q) = K for different constants K, most of the lines are curves. [Plotting xy=K is mostly the same thing as plotting y=K/x, so it is no surprise that these lines of constant E are curves]. Think of K increasing as being like water level rising in a mountainous landscape.

A fair Game?
The fact that with the strategy p=5/12 your expected winnings are 1/12 each go means that it is not a "fair game" in that the person choosing A or B has an advantage over the person choosing X or Y. It's a small margin for sure, but a margin none the less.

So a new question:
How can we adjust the parameters in the payoff matrix to make the game fair? - and I don't mean making all four values zero! I'd like to make it not too obvious at first sight whether the game is fair or whether it favors the AB chooser or the XY chooser.

--James.

On 9 July 2011 04:04, Jonathan Joo <jonath...@yahoo.com<mailto:jonath...@yahoo.com>> wrote:
Hi James,

Thanks for your extremely comprehensive reply. I think I finally got the answer now- is it 10/24? When you substitute 10/24 for P, you end up with 10y-7(10/24)-10y+3, which simplifies to 70/24 + 3 or 1/12. Sorry it took so long for me to get this- but it was really helpful seeing how you arrived at the equation for E:
("You choose A with probability p, and you choose B with probability (1-p).
I choose X with probability q, and I choose Y with probability (1-q).

So AX with probability pq, AY with probability p(1-q), BX with probability (1-p)q and BY with probability (1-p)(1-q).

So the expected score is
E(p,q) = 10pq - 4p(1-q) - 7(1-p)q + 3(1-p)(1-q)")

-Jonathan

________________________________
From: James Crook <james....@gmail.com<mailto:james....@gmail.com>>
To: l2lea...@googlegroups.com<mailto:l2lea...@googlegroups.com>

OK.

Let's collect p

--James.

On 8 July 2011 16:44, Jonathan Joo <jonath...@yahoo.com<mailto:jonath...@yahoo.com>> wrote:
Hi James,

I've attempted the graph many many times, but I just can't seem to get it right. I also tried the steps you gave me- but I'm still stuck on figuring out the equation for E and trying to draw the graph in a way that I can actually understand it... I've spent a considerable amount of time trying to figure it out, but haven't gotten very far :(.

For the markov chains one, I noticed that percentage is the rate of changing from A to E or vice versa (.4 or .7) over the total changing (.4+.7=1.1) ending up with .4/1.1 or 4/11, and .7/1.1 or 7/11. So would the probability of ending up in each state for the second markov graph be .15/.425 (6/17), .25/.425 (10/17) and .025/.425 (1/17)?

-Jonathan
________________________________
From: James Crook <james....@gmail.com<mailto:james....@gmail.com>>
To: l2lea...@googlegroups.com<mailto:l2lea...@googlegroups.com>

Sent: Thursday, July 7, 2011 6:27 PM

Subject: Re: Topic Choices (Puzzles and Game Theory)

Hi jonathan,

[Jonathan Joo]

Hi James,

So I wrote up a basic summary of the nash equilibrium and the matrix problem we were working on. 

In the equation E=(#)pq -(#)p -(#)q+(#), as long as the value before pq is less than both the value before p and the value before q, there is no way to cancel out a variable, as the value before pq cannot be greater than 1, and you can't multiply a number less than 1 with a number to make it larger.  For example, if the equation is 1pq-5p-3q+2, you can't cancel out either p or q, because there is no way to turn the 1pq into a 5p or a 3q. Also, if the equation is E=(#)pq +(#)p +(#)q+(#), then a zero can always be substituted to cancel out a variable.

In the first equation, I got that the value of coefficient is equal to A-B-C+D. So, using this knowledge, we can manipulate the values of A, B, C, and D to create a coefficient of pq that is less than the coefficients of both p and q.

Is this correct?

-Jonathan

---

From: Jonathan Joo <jonath...@yahoo.com>
To: "l2lea...@googlegroups.com" <l2lea...@googlegroups.com>
Sent: Friday, July 8, 2011 11:04 PM

[James Crook]

Jonathan -

Yes, we can change the values of A,B,C,D to make the coefficient of pq what we like.

I think A=-5, B=-3, C= -1, D=2

Gives the AB chooser 'winnings' of 1pq-5p-3q+2

The coefficient of pq is indeed A-B-C+D

The matrix is 

    X  Y

A -5 -3

B -1  2

This looks like a very unfair game, and AB chooser can do no better than always choosing B, whereupon the XY chooser always chooses X.  So p=0, q=1 and the payoff is -3+2 = -1.  

However, I want to adjust the game

      X  Y

A  10 -4

B   -7 3

To make it fair. At the moment it favors AB. 

Any ideas how?

It seems fairly clear that we need to keep the 

+ -

-  +

structure, because if we have two of the same sign in a row or column it either makes the row or column a guaranteed win or loss.

I've made some more updates to:

http://onlinemathcircle.com/wiki/index.php?title=Nash_Equilibrium

Take a look at how I made the LaTeX nicer.  Thanks for expanding the page.

--James.

[Jonathan Joo]

Could you change the payoff value of BY to 2 and 11/12? That way, when you substitute 10/24 for P, you end up with E=0, not E=1/12. 

-Jonathan

---

From: James Crook <james....@gmail.com>
To: l2lea...@googlegroups.com

Sent: Tuesday, July 12, 2011 7:13 AM

[James Crook]

Let's try it: So the expected score is 

E(p,q) = 10pq - 4p(1-q) - 7(1-p)q + 35/12(1-p)(1-q)

E(p,q) = 1/12( pq(120+48+84+35) + p(-48-35) + q(-84-35) + 35)

E(p,q) = 1/12( 287pq -83p -119q +35)

Put p = 119/287 and the terms with q disappear...

E(p,q) = 1/3444(  -9877 +10045) = 168/3444 = 2/41

So if I've got the sums right it's narrowed the gap, but it's still an unfair game favoring the AB player.

The problem is that changing one of the scores has shifted the value for the best p.  It's no longer 10/24.

Any other ideas?

--James.

[James Crook]

Any other ideas?

...3 days later, so I guess not.  I've extended this page to give an answer:

http://onlinemathcircle.com/wiki/index.php?title=Nash_Equilibrium

Jonathan - your answer was close, but you needed to subtract 1/12 from all four scores in order not to shift the equilibrium point.  If you think about that you see the net effect of that is just to reduce any score by 1/12 relative to the earlier game payoffs.

One interesting point is that once the game is made fair the determinant of the payoff matrix is zero!  The update to the page explains why that is so.

--James.

[Jonathan Joo]

Hi James,

Sorry for my delayed response. I've been busy for the past couple days, so I apologize for not sending out an email earlier.

I read through the part you've added, and I see that the answer was simpler than I thought! 

Thank you for clarifying this.

-Jonathan

---

From: James Crook <james....@gmail.com>
To: l2lea...@googlegroups.com

Sent: Friday, July 15, 2011 4:24 PM

[James Crook]

No problem.  It's just I vary the amount of time I put into teaching by how much time students put into the maths and writing back.  For example I was planning to do more on 3D maths, but no one had a go, so I've not built on that topic.

About Nash equilibrium...  in a 2x2 matrix we know the game is fair if the determinant is zero.

Have a go at constructing a fair game with a 3x3 payoff matrix.  Try not to use any zeroes in the matrix.  The A,B,C chooser will have a strategy p_1, p_2, p_3 where p_1+p_2 +p_3 = 1 such that the score is zero no matter what the X,Y,Z chooser chooses as their strategy.  

--James.

[James Crook]

Actually I said something incorrect here.

A fair 2x2 matrix has determinant zero, but a determinant zero 2x2 matrix is not always fair.

10 10 

10 10

isn't fair, for example.  The X,Y chooser always loses 10 points.

--James.

[Jonathan Joo]

18   -21   9

-12  14   -6

24   -28   12

The determinant of this payoff matrix is zero, and I got this by using the factors:

3X6    -3X7  3X3
-2X6   2X7  -2X3
4x6   -4x7   4x3

Horizontally, they all have the same factor (3, 2, or 4) and vertically, they also share the same factor (6,7, or 3)
I'm not sure if this is correct, but it has a determinant of zero and seems to make sense.

-Jonathan

---

From: James Crook <james....@gmail.com>
To: l2lea...@googlegroups.com

Sent: Sunday, July 17, 2011 4:57 PM

[James Crook]

Looks good to me.

If anything you've made really thoroughly sure of it, as the matirx is very degenerate - it has rank 1, whereas rank less than 3 is enough for the determinant to be zero.

p(A)=0, p(B)=2/3, p(C) = 1/3

will guarantee an average score of zero - i.e ignoring the first row.  And I could have made many other choices of the p's for that to be so.

Equally the column chooser can do:

p(X)=0, p(Y)=3/10, p(Z)=7/10

and guarantee an average score of zero - ignoring the first column.

A good choice of matrix.

We may come back and look at Nash Equilibrium again briefly, when we have a new piece of mathematical machinery to use on it, just to establish why there always is an equilibrium Nash strategy which the other player can do nothing about, no matter how big the matrix is or what values it has in it.

--James.