Revealing the least helpful of three numbers

Question

(This is a follow-up to Guessing whether the revealed number is higher.)

They're at it again. This time Andrew is secretly shown three real numbers, all independently, randomly, uniformly chosen from the interval [0, 1]. He must pick one to go in a transparent box. The other two go into opaque boxes. Then Bndrew enters the room, sees the number in the transparent box, and must guess which of the three boxes contains the highest number. If he gets it right, he wins; otherwise Andrew wins.

Assuming optimal play, how likely is Bndrew to win?

Answer 1

This strategy is based on the answer to the previous question:

Andrew should reveal the number "closest" to $\frac{1}{\sqrt{3}}$, where this distance is chosen such that $0$ and $1$ are equally far away, and distance at all other points is linearly interpolated. That is, the "distance" from $\frac{1}{\sqrt{3}}$ to $x$ is $$d(x) = \begin{cases} 1 - \sqrt{3}x & \text{if } x \le \frac{1}{\sqrt{3}} \\ \frac{\sqrt{3}x - 1}{\sqrt{3} - 1} & \text{if } x > \frac{1}{\sqrt{3}} \end{cases}$$

Note that if $X$ is uniformly distributed over $[0,1]$, $d(X)$ is statistically independent of the event $X > \frac{1}{\sqrt{3}}$.

What is Bndrew's chance of picking the right box?

Regardless of the number revealed, if Bndrew chooses the transparent box, he wins if and only if both other boxes are less than $\frac{1}{\sqrt{3}}$. This happens with probability $\left(\frac{1}{\sqrt{3}}\right)^2 = \frac13$. If he chooses an opaque box instead, his probability of winning is half of what's left, which is also $\frac13$.

Answer 2

I claim that

Bndrew's chances of winning are $\frac{1}{3}+\varepsilon$, where $\varepsilon$ can be as small as Andrew desired, but not zero.

---

Let's start by formalizing the problem.

For Andrew's strategy, we say $A(x,y,z)=p_x$ is the probability Andrew reveals $x$ when the numbers he is shown are $x,y,z$. Obviously, $A(x,y,z)=A(x,y,z)$ and $A(x,y,z)+A(y,x,z)+A(z,x,y)=1$.

Towards calculating the best counter-strategy, Bndrew can calculate the probability that any given number is chosen: $P(x)=\int_0^1\int_0^1 A(x,y,z) dydz$.

Moreover, he can also quantify the probability that the shown $x$ is the largest of the three numbers: $L(x)=\frac{1}{P(x)}\int_0^x\int_0^x A(x,y,z) dydz$.

The best possible counter-strategy for Bndrew is to choose $x$ when $L(x)>\frac{1}{3}$, and otherwise a random opaque box. Clearly, this gives Bndrew an advantage if $L(x)\neq \frac{1}{3}$. So Andrew's optimal strategy has to satisfy $L(x)=\frac{1}{3}$ for all $x$. This gives Bndrew a winning chance of $\frac{1}{3}$.

The question that remains is, is there a strategy that satisfies $L(x)=\frac{1}{3}$ for all $x$ with $P(x)=0$?

The first attempt might be to pick a random number, i.e. $A(x,y,z)=\frac{1}{3}$. However then $L(x)=x^2$ which can be countered by Bndrew by picking the revealed number $x$ if and only if $x^2\geq\frac{1}{3}$, or in other words, if $x\geq \sqrt 3/3=0.57735\dots$. The chance of Bndrew winning can then be calculated as $\int_0^{\sqrt 3/3} \frac{1}{2}(1-x^2)dx+\int_{\sqrt 3/3}^1 x^2 dx+= \frac{1}{9} (3 + \sqrt 3)\approx 0.5258$

Compare this to Tom Sirgedas' answer:

He discretized the problem to ensure that approximately $\frac{1}{3}$ of the time a number is chosen, it is the highest number.

We can apply a similar logic here:

Start by dividing the numbers into $N$ buckets, evenly spread (i.e. bucket 1 is $[0,\frac{1}{N})$, bucket 2 is $[\frac{1}{N},\frac{2}{N})$ etc). For each triplet of numbers, Andrew then devises a deterministic strategy depending on buckets. First, if two numbers are from the same bucket, he picks randomly (this is for simplicity). So now we only need to consider the case of three different buckets. Here, Bndrew wins if he identifies whether the bucket being shown is the largest. This is equivalent to the discrete case Tom's answer. As he mentioned, for large $N$ the winning probability of Bndrew tends to $\frac{1}{3}$. Also chance of there being two numbers from the same bucket tends to $0$ for large $N$. Therefore, for large $N$ the winning probability of Bndrew also tends to $\frac{1}{3}$ in the continuous case, if Andrew uses this strategy.

Small remark about the efficiency of this strategy:

Andrew could optimize this strategy in case there are two numbers from the same bucket. While this lowers Bndrew's win probability for each $N$, it does not change the limit. Put differently: Instead of optimizing the strategy for the case where two or more numbers are from the same bucket, Andrew could achieve the same effect by simply choosing a large enough $N$.

Open question:

I've not been able to show that a strategy for Andrew with $L(x)=\frac{1}{3}$ exactly does not exist. I do not have a strong intuition for whether this exists or not, but I'm just gonna conjecture it does not.

Answer 3

(Partial Answer)

Let's consider a discrete version of the problem, where Andrew is secretly shown three distinct numbers from $\{1,2,3,...,N\}$.

We'll show that for $N=6$, Andrew has a strategy that limits Bndrew's probability of winning to $0.35$. (This value tends towards $\frac{1}{3}$ as $N$ increases.)

Andrew's strategy

As an example, let's consider $N=6$. There are $\binom{N}{3}=20$ scenarios. Each row/scenario in the table below shows which numbers Andrew is shown, and the probability that he chooses that number. (For example, the first row corresponds to the scenario where Andrew is shown $\{1,2,3\}$. Andrew always picks $3$ in this scenario.)

$$ \begin{array} {cc} 1&2&3&4&5&6 \\ \hline 0&0&1&&&&\\0&0&&1&&&\\0&0&&&1&&\\0&1&&&&0&\\0&&0&1&&&\\0&&0&&1&&\\0&&1&&&0&\\0&&&1&0&&\\0&&&1&&0&\\0&&&&1&0&\\&0&0&1&&&\\&0&1&&0&&\\&0&1&&&0&\\&0&&1&0&&\\&0&&1&&0&\\&0&&&1&0&\\&&0&1&0&&\\&&0&1&&0&\\&&0&&1&0&\\&&&0&1&0&\\ \end{array} $$

Bndrew's strategy

We can assume that Bndrew knows Andrew's strategy. Let's calculate the probability that Bndrew wins. To simplify the numbers, let's calculate the Bndrew's expected number of wins if we play each scenario once (and later divide by $20$ to get the probability).

$2$ is only shown once, and Andrew will pick an opaque box. Expected wins: $0.5$

$3$ is shown four times, and $3$ is the highest number only once. Picking $3$ would lead to $1$ win, but picking an opaque box will give $0.5$ expected wins $3$ times (so Bndrew will pick an opaque box). Expected wins: $1.5$

$4$ is shown nine times. One-third of the time it's the highest. Bndrew's strategy is irrelevant here. Expected wins: $3$

$5$ is shown six times. One-third of the time it's the highest. Bndrew's strategy is irrelevant here. Expected wins: $2$

Bndrew expects $7$ wins out of $20$ attempts. So, for $N=6$, Bndrew wins with probability $\frac{7}{20} = 0.35$.

Probability of winning

As $N\rightarrow\infty$, the probability of Bndrew winning approaches $\frac{1}{3}$.

Example: an optimal solution for N=20

I'll explain an optimal strategy for Andrew for N=20. It limits Bndrew's probability of winning to $\frac{1}{3}+\frac{1}{N(N-1)(N-2)}=0.333479...$.

It turns out that Andrew never needs to select the lowest number (of his 3 options).

Here is one optimal strategy for Andrew:

Let's say Andrew has a choice of $\{15,10,7\}$. Andrew ignores the $7$ and looks up $10,15$ on the chart, which has a value of $4$.

The entry at $10,15$ actually represents $9$ scenarios: $\{15,10,1\}$, $\{15,10,2\}$, ..., $\{15,10,9\}$, and the entry indicates that in $4$ of the $9$ scenarios, Andrew should pick the biggest number offered. So, Andrew picks $15$ with a probability of $\frac{4}{9}$ (otherwise, he picks $10$).

The chart was constructed such that for each number, if you consider all the scenarios (triplets) which pick that number, the biggest number is picked in exactly one-third of those scenarios. EXCEPTION: In the $\{1,2,20\}$ scenario, Andrew picks $2$, and that is the only scenario in which he picks $2$, which gives Bndrew a probability of $\frac{1}{2}$ of winning.

Example: Let's find the scenarios where Andrew picks $3$, according to the chart: $\{1,2,3\}$, $\{1,3,20\}$, $\{2,3,20\}$. $3$ is the biggest one-third of the time.

I found the chart's values in an ad-hoc manner, but it should be possible to smooth the values out. (It's straight-forward to modify the chart and have it remain valid).

Answer 4

With chance $ \frac{2}{9}$ when restricted to a fully deterministic strategy. Bndrew should choose the visible number if it is high enough.
Both can calculate the optimal cutoff number and Andrew can use it to its advantage.
So:

If there are no numbers higher than the cutoff, Andrew can choose the highest and win.
If there are 2 or 3 numbers higher than the cutoff, Andrew can choose the second highest and win.
If there is 1 number higher than the cutoff, Andrew can best choose a lower number and the chance is 50-50.

With cutoff n this will mean that Bndrew wins with chance $ \frac{1}{2} * 3 * n * n * (n-1)$ , which is at maximum $ \frac{2}{9}$ for $ n = \frac{2}{3}$

(addition after remark) Since Andrew can bring the chance of Bndrew winning when using the shown value below a random guess. Bndrew should randomly guess for $ \frac{1}{3}$