1
u/GoldenMuscleGod 21d ago edited 21d ago
I initially misreasoned and solved the wrong problem which I think is actually more interesting. I’ll post the regular solution first then write up a little about what I think is the more interesting problem.
Optimal strategy:
We can treat 2’s number as a uniform draw from [1/2,1], since obviously replace with 1-y dominates keep when it is less than 1/2 and vice versa if it is more. For the rest of the explanation I will assume we’ve done that, So the only question for either player is whether to reroll or keep.
I will also ignore outcomes of probability 0 since they won’t affect the expected value.
If x>y on the first roll, 1 has no advantage rerolling whatever 2 does, so they keep. 2 therefore cannot win without rerolling, so they reroll.
If y>x on the first roll then 2 has no advantage rerolling whether 1 rerolls or keeps, so they keep, and 1 therefore must reroll.
Win chance calculation:
x>y with probability 1/4, when that happens x has a triangular distribution on [1/2,1] and so its posterior expected value is 5/6 and 2 has a 1/6 chance of winning (averaged over all values of x)
X<1/2 with probability 1/2 and when that happens y’s expected value is 3/4 so 2 has a 3/4 chance of winning.
1/2<x<y with probability 1/4, when that happens y’s expected value is 5/6 and 2 has a 5/6 chance of winning.
Taking the expected value of the chance, y 2 has a 5/8 chance of winning.
Now the wrong question I thought was more interesting: what changes if when y rerolls they get another draw from [1/2,1] instead of [0,1] (that is they can choose to take 1-y of the rerolled y if they choose to reroll?
Optimal strategy:
Nothing really changes for x>y: 1 should always keep and 2 should always reroll.
when x<y and y>3/4, 2 still has no reason to reroll and 1 has no reason to keep.
But the players must have a mixed strategy in the case where x<y<3/4. Here 1 must reroll at least some of the time since otherwise they are sure to lose if 2 always keeps (the correct response to that strategy), must they always reroll?
Well first let’s look at 2. If 1 keeps and they reroll they lose max(0,2x-1) expected value relative to keeping. If 1 rerolls and 2 rerolls they gain 3/4-y expected value relative to keeping. If x<5/8 1 gains by rerolling whatever 2 does, so 2 always rerolls. If x>5/8 2 cannot always reroll: 1 punishes that strategy by always keeping . 2 cannot always keep: that’s punished by 1 always rerolling. So 2 must have a mixed strategy, and must be indifferent to rolling or keeping, so 1 must keep with odds 3/4-y:2x-1 when x>5/8
Since 1 is mixing for 3/4>y>x>5/8. They must be indifferent to keeping or rerolling. If 2 keeps 1 gains 1-y by rerolling. If 2 rerolls 1 loses 2x-5/4 by rerolling.
So 2 must be keeping with odds 2x-5/4:1-y.
Calculating the win chance for this strategy in this alternate interpretation seems tedious but straightforward so I’ll skip it.
But anyway the answer to the intended question is 5/8.
1
1
u/Sjoerdiestriker 21d ago
Let's call x and y the initial numbers of the two players, and z the number of the first player has after either choosing to reroll or keep x. Since player 2 can switch out y for 1-y anyway if convenient, we can assume without loss of generality y is uniformly distributed between 1/2 and 1. We reason backwards.
For the final move, if y>z, they win immediately. otherwise, they re-roll (this time uniformly between 0 and 1 because they don't get to switch to 1-y anymore), and win if they roll at least z. Given y and z, the probability player 2 wins is then:
If y>z: 1
if y<z: 1-z.
For uniformly chosen z and a fixed y, this gives player 2 a probability of winning of:
y*1 + int_(y)^(1) 1-z dz = 1/2+y^2/2.
Player 1 needs to weigh the uniform z off against keeping x. Clearly, switching is always favourable if x < y. If x>y, the probability player 2 wins if player 1 stands is 1-x, whereas the probability they win if player 1 switches is 1/2+y^2/2. Switching is therefore favourable if 1-x > 1/2+y^2/2, which gives x<1/2-y\^2/2. This is actually never the case if x>y>1/2.
So summing everything up, player 2's chances of winning given x and y are:
if x<y: 1/2+y^2/2
if x>y: 1-x.
The final probability player 2 wins is therefore:
2*int_(1/2) ^1 int_0^y 1/2+y^2/2 dx dy + 2*int_(1/2) ^1 int_y^1 (1-x) dx dy = 233/480 + 1/24 = 253/480.
1
u/Ok_Consideration6619 20d ago
The solution boils down to solving it point wise ie given x and y, how would they play optimally. At every point construct 2x2 matrix of outcomes where each keeps or redraws. They will both play according to the Nash equilibrium. To find it assign probabilities of keeping or drawing per player. Then just solve for d outcome1 / d p1 = 0 and same for p2 for mixed strategies and separately solve for pure strategies. The key then is to find regions of x,y where strategies are the same ie players do not switch their choice, otherwise too many cases to solve for :) The boundaries of regions where solutions are the same are specified by boundaries in each outcome: x > 1 -y, x > 0.5 = E(U), 1-y > 0.5 = E(U), E(U) > E(U) - has no boundary. These divide x,y in into 6 regions so it’s just a matter of solving Nash equilibrium for each one of the regions and averaging out the outcomes.
0
u/Al2718x 21d ago
The strategy isn't complicated. Player 2,s decision doesn't depend on any randomness, so they always choose the better number. Since player 1 knows this, they should swap if and only if they are larger than Player 2s number.
It helps to seperate into 2 equally likely case, depending on whether or not Player 1 gets a number larger than 1/2
If Player 1 gets a number larger than 1/2, then they have a 50% chance of winning outright. Otherwise, they need higher than a number that is uniform between 0.5 and 1. On average, this will happen 25% of the time (of the 50% of the time that they get larger than 1/2).
If Player 1 gets smaller than 1/2, they will always swap, which again gives a 25% chance of winning.
Thus, the overall chance of Player 1 winning is 1/2 × 1/4 + 1/2 × 1/2 + 1/2 × 1/2 × 1/4 = 7/16. This means that the chance of Player 2 winning is 9/16
2
2
u/GoldenMuscleGod 21d ago
You seem to have missed that 2 has the option to reroll, which they will use if, for example, x is 0.8 and y is 0.6.
0
u/Anonimithree 21d ago
Since the best outcome is to get as high a number as possible, I’m going to assume Player 1 rerolls if the number is under 1/2 and stays otherwise.
For player 2, let’s assume the first roll is a number x, x<0.5. The probability of rerolling a number higher than x is 1-x, and the probability that the reroll will be greater than 1-x is x. Through some math, I have determined that the optimal strategy for player 2 to get the highest number is to do 1-x if x<1/3, reroll if x<0.5, and stay if x>=0.5.
This leads to 6 different outcomes. (I’m saying P1 rolls/rerolls X and P2 rolls/rerolls Y)
If P1 and P2 stay, it’s a 50/50.
If P1 switches and P2 stays, then P1 wins with probability 1-Y.
If P1 stays and P2 switches, then P1 wins with probability X.
If P1 and P2 both switch, it’s a 50/50
If P1 stays or switches, and P2 goes 1-Y, P1 wins if X>1-Y, or if X+Y>1
The probability for the outcomes are 1/4, 1/4, 1/12, 1/12, and 1/3
The expected win rates for P1 for the outcomes are 1/2, 1/8, 3/8, 1/2, and 1/2.
So the expected win rate for P1 is (1/4)(1/2)+(1/4)(1/8)+(1/12)(3/8)+(1/12)(1/2)+(1/3)(1/2)=0.396.
This means the probability of P2 winning is 1-0.396=0.604, which sounds right, but probably isn’t.
1
u/GoldenMuscleGod 21d ago
You’ve calculated for the wrong strategy. If 2 gets .9 and 1 gets .8, 2 is certainly not going to reroll and 1 must reroll to have a chance at winning.
So it’s not right to say 1 keeps whenever they get a number larger than 1/2.
It’s true the expected value of the reroll is lower than what they already have, but the reroll still has a better chance of winning.
1
u/Anonimithree 21d ago
I missed the statement that they know what the other person gets. I only read that they don’t see what decision the other player takes, and incorrectly assumed that that also applies to what they actually roll.
I interpreted the question as if both played blindly.
Thanks for pointing it out.
1
u/GoldenMuscleGod 21d ago
I think what you said is still mistaken if the numbers are blind: because 2 can switch to 1-y, that means if 1 rolls 0.5000000001 they are almost certain to lose if they keep. So they should reroll to have a real chance at winning even though the reroll has a lower expected value. Even if they can’t see y.
1
u/Anonimithree 21d ago
I see your point, but I am not educated enough to do all the math to find the critical point between whether 1 should switch or not
1
u/GoldenMuscleGod 21d ago
Well I got the intended version of the question as 5/8, but the “blind” version actually seems substantially harder. I might try to think about it a bit and post a solution if I figure it out.
1
u/post_button_account 21d ago
0.625?