5
$\begingroup$

There is a $20$-sided (face value of $1$-$20$) die and a $10$-sided (face value of $1$-$10$) dice. $A$ and $B$ roll the $20$ and $10$-sided dice, respectively. Both of them can roll their dice twice. They may choose to stop after the first roll or may continue to roll for the second time. They will compare the face value of the last rolls. If $A$ gets a bigger (and not equal) number, $A$ wins. Otherwise, $B$ wins. What's the best strategy for $A$? What's $A$'s winning probability?

I know this problem can be solved using the indifference equations, which have been described in details in this paper by Ferguson and Ferguson. However, this approach is complicated and it’s easy to make mistakes for this specific problem. Are there any other more intuitive methods?

Note: $A$ and $B$ roll simultaneouly. They don't know each other's number until the end when they compare them with one another.

$\endgroup$
2
  • $\begingroup$ there is not information here to solve this problem. Do they observe the result of the first roll of the rival ? Is A and B rolling simultaneously or A goes first? Or they roll their first and (possibly) second rolls and only at the end they observe the number of the rival? $\endgroup$ Apr 12 '14 at 16:19
  • $\begingroup$ A and B roll simultaneouly. They don't know each other's number until at last they compare with each other. $\endgroup$
    – user142116
    Apr 14 '14 at 16:15
3
$\begingroup$

Certainly the strategy for each player must be of the form to reroll below a certain threshold. To find the threshold, we can start from Ross’ approximate solution and iteratively adjust the strategies until they're in equilibrium.

So assume that $B$ rerolls below $6$ and $A$ rerolls below $9$. Then every number of $B$ below $6$ has probability $\frac12\cdot\frac1{10}=\frac1{20}$, and every number $6$ or higher has probability $\frac1{10}+\frac12\cdot\frac1{10}=\frac3{20}$. Every number of $A$ below $9$ has probability $\frac8{20}\cdot\frac1{20}=\frac1{50}$ and every number $9$ or higher has probability $\frac1{20}+\frac8{20}\cdot\frac1{20}=\frac7{100}$.

If $B$ were to adjust her strategy by keeping $5$, she would get a winning chance of $5\cdot\frac1{50}=\frac1{10}$ instead of the current winning chance of $\frac1{10}\sum_{k=1}^{10}\frac k{50}+3\cdot\frac1{10}\left(\frac7{100}-\frac1{50}\right)$, where the second term corrects for the $9$ and $10$ that are incorrectly included in the sum in the first term. This is $\frac{10(10+1)}{2\cdot10\cdot50}+\frac3{200}=\frac{11}{100}+\frac3{200}=\frac{25}{200}=\frac18$. Thus, there is no gain in this strategy change.

On the other hand, if she were to adjust her strategy by rerolling $6$, she would give up the current winning probability of $6\cdot\frac1{50}=\frac3{25}$ to get the above winning probability upon rerolling, $\frac18$. Since this is slightly larger than $\frac3{25}$, she should switch strategies and reroll $6$. (The reason this didn't show up in Ross’ argument is that given $A$'s strategy, $9$ and $10$ are far more likely than the other numbers, so it makes sense for $B$ to try harder to beat them even though it lowers $B$'s average roll.)

On the other hand, keeping $7$ yields a winning probability of $7\cdot\frac1{50}=\frac7{50}\gt\frac18$, so $B$ shouldn't reroll $7$. Thus $B$’s best response to $A$’s current strategy is to reroll $6$ or lower. The probability for $B$ to end up with a number below $7$ will then be $\frac6{10}\cdot\frac1{10}=\frac3{50}$, and the probability for a number $7$ or higher will be $\frac1{10}+\frac6{10}\cdot\frac1{10}=\frac4{25}$.

Now we should check whether $A$’s strategy is the best reponse to $B$’s new strategy. If $A$ were to adjust his strategy by keeping $8$, he’d get a winning chance of $1-3\cdot\frac4{25}=\frac{13}{25}$ instead of the current winning chance of $\frac12+\frac1{20}\sum_{k=1}^{10}(k-1)\cdot\frac3{50}+6\cdot\frac1{20}\left(\frac4{25}-\frac3{50}\right)=\frac12+\frac{3\cdot9\cdot10}{2\cdot20\cdot50}+\frac3{100}=\frac12+\frac{27}{200}+\frac3{100}=\frac{133}{200}$. Since $\frac{13}{25}=\frac{104}{200}$ is lower, there is no gain in this strategy change.

On the other hand, keeping $9$ yields a winning probability of $1-2\cdot\frac4{25}=\frac{17}{25}=\frac{136}{200}\gt\frac{133}{200}$, so rerolling $9$ is no gain, either. Thus, $A$’s current strategy of rerolling below $9$ is still the best response to $B$’s new strategy. The overall winning probability of $A$ for this equilibrium strategy pair is

$$ \frac12+\frac1{20}\left(1-\frac4{25}+1-\frac8{25}+8\left(\frac12+\frac1{20}\left(1-\frac4{25}+1-\frac8{25}+\sum_{k=1}^8(k-1)\cdot\frac3{50}\right)\right)\right) \\ = \frac12+\frac1{20}\left(\frac{38}{25}+4+\frac25\left(\frac{38}{25}+\frac{7\cdot8\cdot3}{2\cdot50}\right)\right)=\frac{21}{25}=0.84\;, $$

a slight drop from Ross’ approximation due to the slight improvement in $B$’s strategy.

$\endgroup$
1
  • $\begingroup$ Very nice. +1${ }$ $\endgroup$ Dec 22 '19 at 14:44
1
$\begingroup$

$B$ should reroll anything $5$ or below as he is likely to improve, while with a $6$ he is more likely to get worse. He then has $\frac 1{20}$ chance of getting each number $1$ to $5$ and $\frac 3{20}$ chance of any number $6$ to $10$.

$A$ can then compute the chance that each number wins. Any number $11$ through $20$ is a guaranteed win, so clearly should be accepted. If he rolls a second die, each number is equally probable, and he will win $\frac 12$ (that he rolls $11-20$) plus $\frac 1{20} \cdot \frac {17}{20}$ (that he rolls a $10$ and wins) plus $\frac 1{20} \cdot \frac {14}{20}$ (that he rolls a $9$ and wins) plus ... $\frac 1{20} \cdot \frac {4}{20}$ (that he rolls a $5$ and wins) plus ... The total is $$\frac 12+\frac 1{20}\left(\frac{17+14+11+8+5+4+3+2+1}{20}\right)=\frac{53}{80}$$ He should therefore accept a $9$ or higher as these have a higher winning chance than a random roll. His winning chance is then $\frac 12$ (that the first roll is $11-20$) plus $\frac 1{20} \cdot \frac {17}{20}$ (that he rolls a $10$ and wins) plus $\frac 1{20} \cdot \frac {14}{20}$ (that he rolls a $9$ and wins) plus $\frac8{20}\cdot \frac {53}{80}$ (that he rolls $8$ or less and wins with the second roll). The total is $$\frac 12+\frac {17+14}{20^2}+\frac 8{20}\cdot \frac {53}{80}=\frac {1348}{1600}=\frac {337}{400}=0.8425$$

$\endgroup$
1
  • $\begingroup$ The first sentence isn't quite right. This would only be the case if $B$ were optimizing the average roll rather than the winning probability. It actually turns out that $B$ should reroll $6$ (see my answer, which builds on yours). $\endgroup$
    – joriki
    Dec 22 '19 at 9:28
0
$\begingroup$

This is not really an answer but a long comment. I did not have chance to read the article you posted so not sure what is the indifference method you refer. Perhaps is the same method I have in mind: Assume player 1 rolls for the second time if and only if his first number was below $x$. Given this strategy compute the expected winning probability of player 2 given his first roll was $y$, that is $W_2(\text{action of 2},y|x)$, under two scenarios: if she rolls again and if she does not roll again. If $x$ and $y$ were continuous variables, you would equate the two winning probabilities (roll and don't roll for 2) and also set $y=x$ and finally solve for $x$. In the discrete case you have to consider several inequalities: $$ W_2(\text{roll},y=x-1|x)>W_2(\text{don't roll},y=x-1|x)$$ and $$ W_2(\text{roll},y=x|x)<W_2(\text{don't roll},y=x|x).$$

I would use a computer algebra system (Maple or Mathematica) and solve this by brute force.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.