Here is another variant of the question that I asked previously.
In a game there is a 20-sided die. At the start of the game it is on the table and the 1 face is facing upright. In each of the 100 rounds you have 2 options: you can either roll the dice or you can take a number of dollars equal to the current face.
However, once you take the money, the casino gets to choose if she wants to reroll the die and if she wants to, she rerolls the die. This doesn't cost your turn, but the value of the die changes.
So my basic idea is that the expected value of the die is $10.5$, which is the average from $1$ to $20$. So obviously the casino wants to minimize my return, so I guess she would reroll if I get a value above the expected value so in this case, the casino will reroll if I get a value between $11$ to $20$. And not reroll and just let me have it from $1$ to $10$.
So I guess $\frac{1}{2}$ of the time I will get some number between $11$ to $20$, in which I will take money and $\frac{1}{2}$ of the time I will get some between $1$ to $10$, in which I will reroll. So on average I take money for $50$ rounds, each round has an expected value of $15.5$, so I make $775$ on average for $100$ rounds. I spent $50$ rounds taking money and spent $50$ rounds rerolling.
So that means on average each round pays around $\frac{775}{100}= 7.75$.
Should I now adjust my range of acceptable numbers? Since now each round pays $7.75$, should I accept any number from $8$ and above (ie any number greater than the expected return of each round)?
So now I no longer spend $50$ rounds on rerolling and $50$ rounds on taking money, I will take money $\frac{13}{20}$ of $100$ rounds of the time and reroll $\frac{7}{20}$ of $100$ of the time. Now the average value of money taken is the average of $8$ to $20$ is $14$, $65 \times 14 = 910$. So with this strategy I make $910$ from $100$ rounds, which is a better strategy than the last one.
So now the expected return of each round is $9.10$, so I need to readjust again to accept $10$ to $20$ and do all the calculations again?
But how do find the optimum strategy that maximize my return and what would my return be? Is my approach ok?
Like in optimal strategy for a 20 sided die with 100 rounds game, we can first analytically solve the infinite game before numerically solving the finite game with $100$ rounds.
Again we can assume that with the end of the game sufficiently far off on the horizon both players will always use a constant threshold. Let $t$ be the threshold up to which you reroll and $c$ the threshold down to which the casino rerolls.
Unlike that other game, this one doesn’t have qualitatively different states – the die is always on the table, so we just have to calculate the expected payoff per roll.
If $c-t\gt1$, the game will eventually get stuck at one of the values in $[t+1,c-1]$, so the expected payoff is the average payoff $\frac{c+t}2$ of that range.
Now assume $c-t\le1$, so someone will always reroll the die. Then the expected payoff per round is
$$ \frac1{20}\sum_{k=t+1}^{20}k=\frac1{40}(21+t)(20-t)\;.\tag1 $$
This is independent of $c$ and decreases with $t$, whereas $\frac{c+t}2$ increases with both $c$ and $t$. Thus, the best responses of both players are always on the boundary between the two cases, with $c-t$ either $1$ or $2$.
For $c-t=2$, the game is certain to eventually get stuck at $t+1=c-1$, so that’s the expected payoff per round.
For $c-t=1$, the expected payoff is $(1)$, and we need to find where this crosses $t+1$. That happens at
$$t=\frac{41-\sqrt{3201}}2\approx7.8\;.$$
Indeed, there is a unique equilibrium at $t=8$ and $c=9$, with expected payoff $8.7$. The casino cannot change the payoff by decreasing $c$ (since the die is already always being rerolled), and if she increases $c$ to $10$, the payoff increases to $9$. If you switch to $t=7$, the payoff decreases to $8$, and if you switch to $t=9$, the payoff decreases to $8.25$.
Thus the equilibrium strategy in the infinite game is for you to reroll up to $8$ and for the casino to reroll down to $9$, and the expected payoff per round is $8.7$.
Here’s Java code that solves the finite game with $100$ rounds. The expected payoff is
$$ \frac{11058363311}{12800000}\approx863.93\;, $$
quite close to $100$ times the expected payoff of the infinite game per round.
Note that whereas for the infinite game we had to resort to self-consistent equilibrium considerations, for the finite game each player can directly optimize their strategy based on the expected values of future rounds, without any equilibrium considerations. As expected, this optimization leads to both players applying the equilibrium strategy of the infinite game for most of the finite game, up to (and including) round $91$. Here are optimal thresholds $t$ and $c$ for the remaining rounds:
\begin{array}{c|cc} \text{round}&92&93&94&95&96&97&98&99\\\hline t&8&7&7&7&7&7&6&5\\\hline c&10&10&10&10&10&10&10&11\\ \end{array}
(Obviously you should always take the money in the last round, and it’s irrelevant whether the casino rerolls in the last round.)
As in the other game, there’s some deviation from the long-term equilibrium as the end draws nigh, but there’s no oscillation – rather, your threshold gradually decreases while the casino’s threshold gradually increases. Thus, more and more numbers don’t get rerolled, with the numbers $6$ through $10$ not being rerolled in the penultimate round. That makes sense: The casino knows that you’re not going to reroll in the last round, so she doesn’t need to reroll the $9$ and $10$ (whereas during the bulk of the game she has to reroll them so as not to save you the cost of rerolling them yourself); and you only have one payoff left so just like in the original game it doesn’t pay to reroll a $6$, $7$ or $8$ (whereas during the bulk of the game you have to reroll them so as not to get stuck on them).