Monday, April 5, 2021

Sphinx hijinks

You will be asked four seemingly arbitrary true-or-false questions by the Sphinx on a topic about which you know absolutely nothing. Before the first question is asked, you have exactly $\$1.$ For each question, you can bet any non-negative amount of money that you will answer correctly. That is, you can bet any real number (including fractions of pennies) between zero and the current amount of money you have. After each of your answers, the Sphinx reveals the correct answer. If you are right, you gain the amount of money you bet; if you are wrong, you lose the money you bet.

However, there’s a catch. (Isn’t there always, with the Sphinx?) The answer will never be the same for three questions in a row.

With this information in hand, what is the maximum amount of money you can be sure that you’ll win, no matter what the answers wind up being?

Just before the $i$th question, let's assume that we have $S_{i-1}$ dollars. Further, let $x_i \in [0, S_{i-1}]$ be the wager and $u_i \in \{T, F\}$ be your answer for question $i.$ Finally let $\mathcal{T}_i = (t_1, \dots, t_i)$ be the historical truth values of the question up until question $i.$ We assume that $S_0 = 1$ and $\mathcal{T}_0 = \emptyset.$

Rather than the full binary tree of $16$ possible truth values to a sequence of $4$ true/false questions, the condition that the answer to three consecutive questions is never the same prunes the tree down to $10$ possible outcomes.

At each leaf $\mathcal{T} = \mathcal{T}_4$ of this tree, we can come up with the value of $S_4(x,u,\mathcal{T})$ at each leaf based on the strategies of $x = (x_1(S_0), \dots, x_4(S_3,\mathcal{T}_3)),$ $u = (u_1(S_0), \dots, u_4(S_3,\mathcal{T}_3)).$ The goal is to choose optimal strategies $$\hat{x}, \hat{u} \in \mathop{\arg\!\max} \left\{ \min_{\mathcal{T}} S_4(x,u,\mathcal{T}) \right\}.$$

We can quickly reduce the dimension by way of a smaller problem. Let's say instead that the Sphinx just had one question, with no restrictions on its truth value, but still allowed you to wager $x \in [0,S].$ In this case, since you have no additional information the choice of $u$ is arbitrary and with $50\%$ probabilty you could end up with $S+x$ and $50\%$ you could end up with $S-x.$ If this case, still wanting to maximize the minimum final wealth, we would select $$\hat{x} \in \mathop{\arg\!\max}\limits_{x\in[0,S]} \{ \min \{S+x,S-x\} \} = \{0\}.$$ By extension, we see that when presented with a true $50\% / 50\%$ proposition it is best "not to play the game".

Additionally, as with all sure bets, with perfect information (i.e., when we have already observed two T in a row and know that the next answer will be F, or vice versa) we should bet the house, thereby doubling the your money.

Combining these two examples, we can resolve the optimal behavior of the $4$th question and conclude that we should always bet $0$ on the first question as well. By symmetry, without loss of generality, let's assume that the Sphinx's first question was true. We can reduce the dimensionality further by allowing the bet size to assume negative values, as well, we can infer the optimal answer ($x \gt 0$ implies optimal answer for question 2 is T, vice versa).

Then we can analytically solve for the following optimization problem: $$\max_{-S_0 \leq x \leq S_0} \max_{-S_0 + x \leq y \leq S_0 - x} \min \Big\{ 2(S_0+x), S_0 - x + y, 2(S_0 - x -y) \Big\},$$ which is solved by $(\hat{x},\hat{y}) = (-\frac{S_0}{5}, \frac{2S_0}{5}),$ which gives the optimal minimal value of $$S_4(\hat{x},\hat{y}) = \frac{8S_0}{5} = 1.6,$$ meaing you can guarantee winning $\$0.60.$

No comments:

Post a Comment