Game theory math puzzle
Poll
| No votes (0%) | |||
 | 2 votes (40%) | ||
| No votes (0%) | |||
| | 1 vote (20%) | ||
| No votes (0%) | |||
| | 1 vote (20%) | ||
| | 1 vote (20%) | ||
| No votes (0%) | |||
| | 2 votes (40%) | ||
| | 2 votes (40%) |
5 members have voted
November 18th, 2017 at 3:59:59 PM
permalink
The game One Card Poker at the Cutting Edge got me to thinking about a math puzzle based on the game. Here it is.
Questions:
Free beer to first set of all correct answers. Add a side dish or second drink for a well-explained solution.
- A random number generator provides random numbers between 0 and 1 uniformly distributed.
- Two players each get a separate number. Each player can see his own number only.
- Player 1 may keep his initial number or swap for a new random number.
- Player 2, knowing player 1's action, has the same option to keep his original number or swap for a new one.
- Player with the higher number wins.
Questions:
- At what number is player 1 indifferent to standing and switching?
- Assuming player 1 switches, at what number should player 2 be indifferent to standing and switching?
- Assuming player 1 stands, at what number should player 2 be indifferent to standing and switching?
- Assuming optimal strategy by both players, what is the probability player 1 will win?
Free beer to first set of all correct answers. Add a side dish or second drink for a well-explained solution.
I think both Rose and Jack could have fit on that piece of wood.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
November 18th, 2017 at 6:45:10 PM
permalink
I am not 100% sure about this, as my initial premise may be wrong.
Let P1 and P2 be the two players' numbers
My initial premise is that P1 will switch if P1 < 1/2, as P1 is more likely to get a larger number if < 1/2 and less likely if > 1/2.
Given that P2's decision is based on P1's, I don't see how it should have any effect on P1's.
1/2 of the time, P1's initial number is uniformly in [1/2, 1], and P1 keeps it
1/2 of the time, P1's initial number is uniformly in [0, 1/2], and P1 replaces it
1/2 x 1/2 = 1/4 of the time, P1's new number is uniformly in [0, 1/2]
1/2 x 1/2 = 1/4 of the time, P1's new number is uniformly in [1/2, 1]
This means P1 is uniformly in [0, 1/2] 1/4 of the time, and in [1/2, 1] 3/4 of the time
The mean value of P1 is 1/4 x 1/4 + 3/4 x 3/4 = 5/8, which I am assuming is the answer to #1
#1: 5/8
If P1 switches, P2 knows P1 is uniformly in [0, 1]
If P2 stands, P2's probability of winning is P2 (since P2 wins if a uniform number in [0, 1] < P2)
If P2 switches, P2's number is also uniformly between 0 and 1, so P2's probability of winning = 1/2
These are the same when P2 = 1/2
#2: 1/2
If P1 stands, P2 knows P1 is uniformly in [1/2, 1]
If P2 stands, P2's probability of winning is (P2 - 0.5) / 0.5 = 2 P2 - 1
If P2 switches, then 1/2 of the time, P2 < 1/2, and P2 never wins, and the other 1/2 of the time, P2 is also uniformly in [1/2, 1], so P2's probability of winning = 1/2 x 1/2 = 1/4
These are the same when 2 P2 - 1 = 1/4
#3: 5/8
To calculate P1's overall probability of winning:
(1) P1's initial number < 1/2, and P1 switches to a uniform number in [0, 1]
(1.1) P2's initial number < 1/2, and P2 also switches; P1's probability of winning = 1/2 x 1/2 x 1/2 = 1/8
(1.2) P2's initial number > 1/2, so P2 stands
(1.2.1) If P1's new number < 1/2, P1 never wins
(1.2.2) If P1's new number > 1/2, then both are uniformly in [1/2, 1], so P1's probability of winning = 1/2 x 1/2 x 1/2 x 1/2 = 1/16
(2) P1's initial number is in (1/2, 5/8], so P1 keeps it
(2.1) P2's initial number < 5/8, so P2 switches
(2.1.1) If P2's new number < 1/2, P1 always wins; P1's probability of winning = 1/8 x 5/8 x 1/2 = 5/128
(2.1.2) If P2's new number is in [1/2, 5/8], then both are uniformly in [1/2, 5/8], so P1's probability of winning = 1/8 x 1/8 x 1/2 = 1/128
(2.1.3) If P2's new number > 5/8, P1 never wins
(2.2) P2's initial number > 5/8, so P2 stands; P1 never wins
(3) P1's initial number is in (5/8, 1], so P1 keeps it
(3.1) P2's initial number < 5/8, so P2 switches
(3.1.1) If P2's new number < 5/8, P1 always wins; P1's probability of winning = 3/8 x 5/8 x 5/8 = 75/512
(3.1.2) If P2's new number > 5/8, P1 and P2 both have uniform numbers in [5/8, 1]; P1's probability of winning = 3/8 x 5/8 x 3/8 x 1/2 = 45/1024
(3.2) P2's initial number > 5/8, so P2 also stands; both are uniformly in [5/8, 1], so P1's probability of winning = 3/8 x 3/8 x 1/2 = 9/128
P1's overall probability of winning = 1/8 + 1/16 + 1/128 + 75/512 + 45/1024 + 9/128
#4: 467/1024
Let P1 and P2 be the two players' numbers
My initial premise is that P1 will switch if P1 < 1/2, as P1 is more likely to get a larger number if < 1/2 and less likely if > 1/2.
Given that P2's decision is based on P1's, I don't see how it should have any effect on P1's.
1/2 of the time, P1's initial number is uniformly in [1/2, 1], and P1 keeps it
1/2 of the time, P1's initial number is uniformly in [0, 1/2], and P1 replaces it
1/2 x 1/2 = 1/4 of the time, P1's new number is uniformly in [0, 1/2]
1/2 x 1/2 = 1/4 of the time, P1's new number is uniformly in [1/2, 1]
This means P1 is uniformly in [0, 1/2] 1/4 of the time, and in [1/2, 1] 3/4 of the time
The mean value of P1 is 1/4 x 1/4 + 3/4 x 3/4 = 5/8, which I am assuming is the answer to #1
#1: 5/8
If P1 switches, P2 knows P1 is uniformly in [0, 1]
If P2 stands, P2's probability of winning is P2 (since P2 wins if a uniform number in [0, 1] < P2)
If P2 switches, P2's number is also uniformly between 0 and 1, so P2's probability of winning = 1/2
These are the same when P2 = 1/2
#2: 1/2
If P1 stands, P2 knows P1 is uniformly in [1/2, 1]
If P2 stands, P2's probability of winning is (P2 - 0.5) / 0.5 = 2 P2 - 1
If P2 switches, then 1/2 of the time, P2 < 1/2, and P2 never wins, and the other 1/2 of the time, P2 is also uniformly in [1/2, 1], so P2's probability of winning = 1/2 x 1/2 = 1/4
These are the same when 2 P2 - 1 = 1/4
#3: 5/8
To calculate P1's overall probability of winning:
(1) P1's initial number < 1/2, and P1 switches to a uniform number in [0, 1]
(1.1) P2's initial number < 1/2, and P2 also switches; P1's probability of winning = 1/2 x 1/2 x 1/2 = 1/8
(1.2) P2's initial number > 1/2, so P2 stands
(1.2.1) If P1's new number < 1/2, P1 never wins
(1.2.2) If P1's new number > 1/2, then both are uniformly in [1/2, 1], so P1's probability of winning = 1/2 x 1/2 x 1/2 x 1/2 = 1/16
(2) P1's initial number is in (1/2, 5/8], so P1 keeps it
(2.1) P2's initial number < 5/8, so P2 switches
(2.1.1) If P2's new number < 1/2, P1 always wins; P1's probability of winning = 1/8 x 5/8 x 1/2 = 5/128
(2.1.2) If P2's new number is in [1/2, 5/8], then both are uniformly in [1/2, 5/8], so P1's probability of winning = 1/8 x 1/8 x 1/2 = 1/128
(2.1.3) If P2's new number > 5/8, P1 never wins
(2.2) P2's initial number > 5/8, so P2 stands; P1 never wins
(3) P1's initial number is in (5/8, 1], so P1 keeps it
(3.1) P2's initial number < 5/8, so P2 switches
(3.1.1) If P2's new number < 5/8, P1 always wins; P1's probability of winning = 3/8 x 5/8 x 5/8 = 75/512
(3.1.2) If P2's new number > 5/8, P1 and P2 both have uniform numbers in [5/8, 1]; P1's probability of winning = 3/8 x 5/8 x 3/8 x 1/2 = 45/1024
(3.2) P2's initial number > 5/8, so P2 also stands; both are uniformly in [5/8, 1], so P1's probability of winning = 3/8 x 3/8 x 1/2 = 9/128
P1's overall probability of winning = 1/8 + 1/16 + 1/128 + 75/512 + 45/1024 + 9/128
#4: 467/1024
November 18th, 2017 at 7:05:45 PM
permalink
Just so strangely caught me doing laundry, so here is the solution I came up with. Some of the algebra is intense, so I at times used the Wolfram site. I put the explanation in there, so if I made an error in valuation functions you can correct me but I have high confidence the method is correct.
1. 0.766446
2. 0.75
3. 0.820993
4. 0.498305
Solution:
There are four situations player 2 finds himself in. P1 switched and P2 stood, P1 switched and P2 switched, P1 stood and P2 stood, P1 stood and P2 switched.
Start by finding where P2 is indifferent to switching or standing after P1 switched. Assume he stands at some number b and switches below it. His value when he stands is (2b-1) and when he switches is 0. His overall expected value then is (1-b)(2b-1). Performing a derivative to find the max, you find his optimal b is at 3/4. His optimal expected value in this situation is 1/8, which makes the value of P1's decision to switch -1/8.
Then find where P2 is indifferent to switching or standing after P1 stood. Assume he stands at some number c and switches below it. Worth mentioning is that P1 will stand at some number a and switch below it. Under an optimal strategy, P2 will choose a c greater than a (You can verify this changing the value function for standing with c less than a). His value for switching is (1-2a). His value for choosing c higher than a is (c-a)/(1-a) as he wins (c-a)/(1-a) of the time and ties otherwise. His overall expectation is then (1-c)(c-a)/(1-a) + c(1-2a). Performing a derivative to find the max, we find the optimal c is a^2-a+1. His optimal expected value is -a^3+a^2-2a+1, which makes the value of P1's decision to stand a^3-a^2+2a-1.
Now we can get the optimal expected value for P1 which is -1/8*a + (1-a)*(a^3-a^2+2a-1). This maxes out at an a of 0.766466 and value of -.00339003. Solving for c, we find the value is 0.820993. Using the formula EV=pwin - (1-pwin) as pwin = (EV+1)/2, we find that P1 wins 49.83% of the time with player 2 having an edge of 0.3390% on him.
1. 0.766446
2. 0.75
3. 0.820993
4. 0.498305
Solution:
There are four situations player 2 finds himself in. P1 switched and P2 stood, P1 switched and P2 switched, P1 stood and P2 stood, P1 stood and P2 switched.
Start by finding where P2 is indifferent to switching or standing after P1 switched. Assume he stands at some number b and switches below it. His value when he stands is (2b-1) and when he switches is 0. His overall expected value then is (1-b)(2b-1). Performing a derivative to find the max, you find his optimal b is at 3/4. His optimal expected value in this situation is 1/8, which makes the value of P1's decision to switch -1/8.
Then find where P2 is indifferent to switching or standing after P1 stood. Assume he stands at some number c and switches below it. Worth mentioning is that P1 will stand at some number a and switch below it. Under an optimal strategy, P2 will choose a c greater than a (You can verify this changing the value function for standing with c less than a). His value for switching is (1-2a). His value for choosing c higher than a is (c-a)/(1-a) as he wins (c-a)/(1-a) of the time and ties otherwise. His overall expectation is then (1-c)(c-a)/(1-a) + c(1-2a). Performing a derivative to find the max, we find the optimal c is a^2-a+1. His optimal expected value is -a^3+a^2-2a+1, which makes the value of P1's decision to stand a^3-a^2+2a-1.
Now we can get the optimal expected value for P1 which is -1/8*a + (1-a)*(a^3-a^2+2a-1). This maxes out at an a of 0.766466 and value of -.00339003. Solving for c, we find the value is 0.820993. Using the formula EV=pwin - (1-pwin) as pwin = (EV+1)/2, we find that P1 wins 49.83% of the time with player 2 having an edge of 0.3390% on him.
Last edited by: lightningbolts on Nov 18, 2017
November 18th, 2017 at 7:56:56 PM
permalink
Quote: ThatDonGuyI am not 100% sure about this, as my initial premise may be wrong.
Indeed, I think your initial premise is wrong, which led to everything else being wrong.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
November 18th, 2017 at 8:01:56 PM
permalink
Quote: lightningboltsJust so strangely caught me doing laundry, so here is the solution I came up with....
Sorry, I disagree with your answer. Maybe I'm wrong, but I doubt it. I'm not sure if your technique is sound but you made a math error or the fundamental idea is wrong. I got my answer a different way.
The two answers above I deem wrong. So the beer is still up for grabs.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
November 18th, 2017 at 8:48:31 PM
permalink
I should have said earlier that the answer to question #2 by ThatDonGuy is correct. 1/4 of a beer his way.
None of the answers by lightningbolts were correct.
None of the answers by lightningbolts were correct.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
November 18th, 2017 at 9:25:06 PM
permalink
My expected values are wrong as I neglected to integrate. Will look at this later, but you can get the solution that way with player 2 maximizing his EV based on player 1 parameters then player 1 maximizes his EV.
November 18th, 2017 at 10:08:54 PM
permalink
Quote: lightningboltsMy expected values are wrong as I neglected to integrate. Will look at this later, but you can get the solution that way with player 2 maximizing his EV based on player 1 parameters then player 1 maximizes his EV.
No going to bed until solving it.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
November 19th, 2017 at 11:26:05 AM
permalink
1. Player 1 switches at 0.567364
2. If player 1 switches, player 2 is indifferent to switching at 0.5. This one is just logical.
3. If player 1 stands, then player 2 is indifferent to switching at (0.567364^2+1)/2 = 0.660951.
4. Under optimal play, player 1 will win 0.49433 of the time.
It will take quite a bit of time for a full explanation, but #1 is the solution of x^3+x-0.75=0.
#2 is logical
#3 is the point where player 2 has the same chance of winning if they stand (y-x)/(1-x) or if they switch 1-(x+1)/2, if y is Player 2's indifferent point. Solve for y, y=(x^2+1)/2.
#1 calculate the probability of winning on a switch, given the rule 2. p(player winning on a switch) = 0.375. Set this equal to the probability of winning while standing.
#4 integrate
I had a lot of scattered work on this, so the explanation may or may not be completed.
I heart Crystal Math.
November 19th, 2017 at 4:41:12 PM
permalink
Quote: CrystalMath
1. Player 1 switches at 0.567364
2. If player 1 switches, player 2 is indifferent to switching at 0.5. This one is just logical.
3. If player 1 stands, then player 2 is indifferent to switching at (0.567364^2+1)/2 = 0.660951.
4. Under optimal play, player 1 will win 0.49433 of the time.
It will take quite a bit of time for a full explanation, but #1 is the solution of x^3+x-0.75=0.
#2 is logical
#3 is the point where player 2 has the same chance of winning if they stand (y-x)/(1-x) or if they switch 1-(x+1)/2, if y is Player 2's indifferent point. Solve for y, y=(x^2+1)/2.
#1 calculate the probability of winning on a switch, given the rule 2. p(player winning on a switch) = 0.375. Set this equal to the probability of winning while standing.
#4 integrate
I had a lot of scattered work on this, so the explanation may or may not be completed.
Congratulations -- I agree exactly. Add one to the count of beers I owe you. I'll give you another half a beer for the brief solution, which is how I solved it too.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
November 19th, 2017 at 4:56:16 PM
permalink
Now that someone has answered it, I posted a solution to my Math problems site, problem 225.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
November 19th, 2017 at 5:45:00 PM
permalink
It's fun to express the solutions exactly using the cubic formula. x is (1/6)(cbrt(81+3sqrt(921))+cbrt(81-3sqrt(21)) and y is 0.375/x and the House Edge is
(1/12) + (1/96)(cbrt(2763sqrt(921) - 19657) - cbrt(2763sqrt(921) + 19657))
which is the real root of the equation 16384x^3 - 4096x^2 + 103688x - 117 = 0.
The best (that is, most easily remembered and applied) version of the cubic formula is the following:
if x^3 = 3px + 2q, and q^2 >= p^3, then x = cbrt(q + sqrt(q^2 - p^3)) + cbrt(q - sqrt(q^2 - p^3))
It is easy to get an arbitrary cubic in this form by adding or subtracting a constant to the variable to eliminate the 2nd degree term.
If, by the way, q^2 < p^3, so the square root is of a negative number, then there are three real roots but no solution in real radicals, you have to use trig functions:
x = 2 * sqrt(p) * cos((1/3) * arccos(q/(p * sqrt(p))) + A) for A = 0, 120 degrees, and 240 degrees each giving a different root.
(1/12) + (1/96)(cbrt(2763sqrt(921) - 19657) - cbrt(2763sqrt(921) + 19657))
which is the real root of the equation 16384x^3 - 4096x^2 + 103688x - 117 = 0.
The best (that is, most easily remembered and applied) version of the cubic formula is the following:
if x^3 = 3px + 2q, and q^2 >= p^3, then x = cbrt(q + sqrt(q^2 - p^3)) + cbrt(q - sqrt(q^2 - p^3))
It is easy to get an arbitrary cubic in this form by adding or subtracting a constant to the variable to eliminate the 2nd degree term.
If, by the way, q^2 < p^3, so the square root is of a negative number, then there are three real roots but no solution in real radicals, you have to use trig functions:
x = 2 * sqrt(p) * cos((1/3) * arccos(q/(p * sqrt(p))) + A) for A = 0, 120 degrees, and 240 degrees each giving a different root.
November 19th, 2017 at 7:59:48 PM
permalink
Quote: JoeShipmanIt's fun to express the solutions exactly using the cubic formula. x is (1/6)(cbrt(81+3sqrt(921))+cbrt(81-3sqrt(21)) and y is 0.375/x and the House Edge is
(1/12) + (1/96)(cbrt(2763sqrt(921) - 19657) - cbrt(2763sqrt(921) + 19657))
which is the real root of the equation 16384x^3 - 4096x^2 + 103688x - 117 = 0.
The best (that is, most easily remembered and applied) version of the cubic formula is the following:
if x^3 = 3px + 2q, and q^2 >= p^3, then x = cbrt(q + sqrt(q^2 - p^3)) + cbrt(q - sqrt(q^2 - p^3))
It is easy to get an arbitrary cubic in this form by adding or subtracting a constant to the variable to eliminate the 2nd degree term.
If, by the way, q^2 < p^3, so the square root is of a negative number, then there are three real roots but no solution in real radicals, you have to use trig functions:
x = 2 * sqrt(p) * cos((1/3) * arccos(q/(p * sqrt(p))) + A) for A = 0, 120 degrees, and 240 degrees each giving a different root.
You certainly get extra credit for expressing the answers in the exact form. A beer for you too.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
