4
$\begingroup$

(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?

$\endgroup$
4
  • 1
    $\begingroup$ "Assuming optimal play" is ambiguous in concurrent games like this. $\endgroup$
    – PattuX
    Commented Jul 8 at 10:16
  • $\begingroup$ @PattuX fair point, my intention was to say that each player chooses a strategy which maximises their win percentage under the assumption that the other player chooses the best possible counter-strategy. (Discussion: mathoverflow.net/questions/407083/…) $\endgroup$
    – fblundun
    Commented Jul 8 at 11:02
  • 1
    $\begingroup$ So are you looking for a Nash equilibrium for this game? Both playing random where Bndrew succeeds 1 out of 3 does not look like such equilibrium (if Andrew plays random Bndrew can do better and reach (a bit more than) 1/2 using probability help). That said, sure there may exist a clever other equilibrium, perhaps with worse or better odds for Bndrew, or maybe the point is to prove there is none such equilibrium? All this assuming you ask for equilibrium.... Thanks for great question $\endgroup$ Commented Jul 11 at 0:04
  • 1
    $\begingroup$ @FirstNameLastName that's right, I'm looking for a Nash equilibrium or an argument that there isn't one. $\endgroup$
    – fblundun
    Commented Jul 11 at 16:32

4 Answers 4

5
$\begingroup$

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$.

$\endgroup$
6
  • 1
    $\begingroup$ @FirstNameLastName Bndrew has an obvious strategy to guarantee a 1/3 chance of victory, namely ignoring the revealed number and choosing one of the three boxes uniformly at random. I would imagine that any deviation from this strategy would allow Andrew a counter-strategy that works in his favor. $\endgroup$
    – Nitrodon
    Commented Jul 12 at 1:22
  • 1
    $\begingroup$ Fantastic!! This is the elegant answer I was hoping existed! $\endgroup$ Commented Jul 12 at 2:48
  • $\begingroup$ @Nitrodon : For completeness : non-cooperative games can have multiple pure-strategy Nash equilibrium and one may exist here for which Bndrew chance is higher than 1/3. I personally would argue for such better equilibrium to not possibly exist but what is your exact reasoning about this? $\endgroup$ Commented Jul 12 at 22:25
  • $\begingroup$ @Nitrodon : it seems to me this solution can be generalized to more numbers ... what do you think? $\endgroup$ Commented Jul 13 at 23:38
  • 1
    $\begingroup$ @FirstNameLastName This is a two-player zero-sum game (since Andrew wins iff Bndrew doesn't win), and each player has a minimax strategy. And yes, this generalizes to any number of boxes. If Bndrew still needs to choose the largest box out of n, the critical point is n^(-1/(n-1)). $\endgroup$
    – Nitrodon
    Commented Jul 15 at 5:51
2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

(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:
enter image description here

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).

$\endgroup$
1
  • $\begingroup$ @ Tom Sirgedas : I liked your reply +1 and removed my comments $\endgroup$ Commented Jul 10 at 23:54
-1
$\begingroup$

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}$

$\endgroup$
5
  • 2
    $\begingroup$ Bndrew can use random guessing to win with chance 1/3. How can Bndrew's optimal win chance be less? $\endgroup$ Commented Jul 8 at 7:36
  • $\begingroup$ @Lucenaposition: You are right, I added a correction. $\endgroup$
    – Retudin
    Commented Jul 8 at 7:54
  • $\begingroup$ I suppose you mean $(1-n)$ instead of $(n-1)$. Also can you guarantee there isn't a better (deterministic) strategy other than a simple cutoff? $\endgroup$
    – PattuX
    Commented Jul 8 at 9:31
  • $\begingroup$ If Andrew plays the suggested strategy, Bndrew should always pick an opaque box if the revealed number is > 2/3. By doing this, and picking randomly if the revealed number is < 2/3, he can raise his win rate above 1/3. $\endgroup$
    – fblundun
    Commented Jul 8 at 9:46
  • $\begingroup$ @fblundun Bndrew does not know Andrew's strategy. My (admittingly unsupported) assumption is that if Bndrew can not predeclare a strategy better than random guessing, Andrew always has an (unspecified) strategy that makes random guessing optimal for problems like this. $\endgroup$
    – Retudin
    Commented Jul 9 at 6:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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