Number exchange game

Question

Inigo and Vizzini are to have a battle of wits to the death. The rules are:

• Inigo is given two independent random numbers uniformly distributed between 0 and 1.

• Inigo chooses one of the numbers to give to Vizzini and keeps the other.

• Vizzini decides whether or not to trade numbers.

• Whoever has the higher number wins.

Vizzini could just randomly decide whether or not to trade, and this will give him a 50/50 chance of winning. But Vizzini of course has a dizzying intellect, and might be able to come up with a clever strategy which lets him do better...

Who does this game favor? What are both players' optimal strategies?

Source: Games People Don't Play, Peter Winkler, available here.

Answer 1

A possible strategy for Inigo is to

Always give Vizzini the number that is closer to 0.5.

For Vizzini, this means that

Let's say he receives $x$. For every possibility of the two numbers being $(x,y)$ such that $x > y$, there is an equal probability outcome $(x,1-y)$ with $1-y > x$. So Vizzini has an equal probability to win whether he stays or switches; he can do no better than taking the 50/50 gamble.

Answer 2

We already know that Inigo’s chances to win are at most 1/2.

The only strategy for Inigo to keep the chance of winning at 1/2 is by giving Vizzini the number closer to 0.5.

To see this we need some math

Let $X$ and $Y$ be the two random variables.

Let $f:[0,1]\times[0,1]\rightarrow[0,1]$ be Inigo’s strategy. I.e., $f(x,y)=f(y,x) = x$ if Inigo chooses to give Vizzini $x$ when given the numbers $x$ and $y$.

Let $G_x = \{y\in[0,x]|f(x,y)=x\}$ and $H_x=\{y\in[x,1]|f(x,y)=x\}$.

We will use $|G_x|$ and $|H_x|$ to denote the lengths of the elements of the sets (e.g., if $G_{0.8}=[0,0.25]\cup[0.5,0.75]$ then $|G_{0.8}|=0.5$).

We can assume that Vizzini knows Inigo’s strategy. If they are playing multiple rounds Vizzini could anyway learn Inigo’s strategy by some round $N$.

Let us assume Inigo gives Vizzini $x$. Then if $|G_x|>|H_x|$ Vizzini will keep the $x$. If $|G_x|<|H_x|$ then Vizzini will trade numbers. With this strategy the probability of Vizzini being given $x$ and winning is
\begin{equation}(\mathbb{P}(X=x)\mathbb{P}(Y \in G_x\cup H_x)+\mathbb{P}(Y=x)\mathbb{P}(X\in G_x\cup H_x))\times \frac{\max\{|G_x|,|H_x|\}}{|G_x|+|H_x|}\\=2\times\mathbb{P}(X=x)\times(|G_x|+|H_x|)\times\frac{\max\{|G_x|,|H_x|\}}{|G_x|+|H_x|}\\=2\times\mathbb{P}(X=x)\times \max\{|G_x|,|H_x|\}\end{equation}
By summing over every $x$ we get the total probability of Vizzini winning, which we will denote by $W$
\begin{equation}W= \sum_x 2\times\mathbb{P}(X=x)\times \max\{|G_x|,|H_x|\}\end{equation}
Since the probability is uniformly distributed we can write this as an integral with $\mathbb{P}(X=x) = dx$
\begin{equation}W=\int_0^12\times \max\{|G_x|,|H_x|\}dx\end{equation}
We have the constraints $0\leq |G_x|\leq x$ and $0\leq|H_x|\leq 1-x$ and $2\int_0^1 (|G_x|+|H_x|)dx = 1$.

We can now write
\begin{equation}W=2\int_0^1 \max\{|G_x|, |H_x|\}dx\\=2\int_0^1 \max\{|G_x|, |H_x|\}dx -\int_0^1 (|G_x|+|H_x|)dx +1/2\\=\int_0^1||H_x|-|G_x||dx+1/2\end{equation}.
We can see that this is more than $1/2$ unless $|H_x|=|G_x|$ $\forall x$.


The two can be equal only in the triangle below both $x$ and $1-x$. The size of the triangle is $1/4$ so the constraint $2\int_0^1 (|G_x|+|H_x|)dx = 1$ means that $W = 1/2$ if and only if $|H_x|=|G_x|=x$ if $x\in[0,0.5]$ and $|H_x|=|G_x|=1-x$ if $x\in[0.5,1]$.

So if $x=0.5$ then $G_x\cup H_x = [0,1]$. If $x$ is close but less than $0.5$ then $G_x = [0, x]$ but anything closer to $0.5$ cannot be in $H_x$, because $x$ is in their $G_x\Rightarrow H_x=[1-x,1]$. Same logic applies for all $x$ so $G_x\cup H_x = [0,x]\cup[1-x,1]\quad\forall x$.

Any other strategy could be exploited by Vizzini, but this strategy makes sure that Vizzini might as well flip a coin to decide whether to trade or not.

Above we assumed that Inigo uses always the same strategy. We can show that the same applies also for more sophisticated strategies.

We can instead assume that Inigo uses different strategies with different probabilities (any other strategy could eventually be described from Vizzini's point of view this way).

Any such combination of strategies can eventually be written down as having a random variable $T_{x,y,N}$ describing whether for the $N$th pair of $(x,y)$ given to Inigo, he chooses to give $x$ or $y$ to Vizzini.

Let $\mathbb{P}(T_{x,y,N} = x) = t_{x,y}$. Then nothing changes in the above calculations except that we must define the lengths $|G_x|$ and $|H_x|$ in a way that takes into account $t_{x,y}$. This is simply done by using $t_{x,y}$ as a weight function for the lengths.

After that everything in the above calculations stays the same, including the constraints on $|G_x|$ and $|H_x|$ so we arrive to the same conclusion, and $t_{x,y}\in\{0,1\}\quad\forall x,y$.

Answer 3

I initially thought it is sufficient for Vizzini to chose any strategy in which

he will swap a number x < 0.5 with probability > 50%, and will swap a number x > 0.5 with a probability > 50%.

I knew this wouldn't necessarily be his optimal strategy, but I thought it would enough for him to do better than the random strategy described in the question, regardless of Inigo's strategy.

However, this doesn't work as stated because for example: if Vizzini chooses to keep all x > 0.5, and swap for all X < 0.5, (which is an example of my assumed good-enough strategy) then if Inigo was using the strategy

send larger number if both randoms are < 0.5, otherwise send the smaller number,

...it would be disastrous for Vizzini. Hmmm... So my next best bet is that Vizzini chooses any strategy in which

he chooses to swap (when given some particular x) with a probability distribution curve S(x), for which S(x) is continuous, and dS(x)/dx is negative for all x in the range (0..1). Or to say it without differentials, the probability of him choosing to swap any particular x is greater than the probability of him choosing to swap any y > x (and obviously less than the probability of him choosing to swap any y < x).

Answer 4

Since it is not mentioned that they can or cannot change their strategy in the middle of the game, I will assume they decide a strategy at the very beginning and sticking with that until the game decided. So It is like there are two machines, and two computer guy put a code how they play and they see who wins:

First of all, we know that two random numbers are generated, so the outcome probabilities is actually known. And if a random number is below $.5$, the other number's probability to have bigger is $75\%$. below $.6$, the other number's probability to have bigger is $60\%$. Even if the random number generated between $.4$ and $.5$ is outcome, the other number's probability to have bigger than that is around $55\%$. Therefore Vizzini knows that if he gets a lower number he is supposed to change it with Inigo.

So Vizini's strategy should be

If Vizini gets bigger than $.5$ stay on that number, if he gets lower or equal to $.5$, change his number.

Inigo also knows this information, so he needs to think a way to win over this. There are some possible way to fight over this:

1.

If he gets two higher number than $.5$, give the lower one, so Vizzini will need to stay his number to increase his chance to win.

2.

If he gets two lower number than $.5$, give the lower one, so Vizzini will need to change this time and Inigo will win.

Other than that

If one is lower than $.5$ and the other is bigger than $.5$. Inigo has no chance if Vizzini will play the strategy that I have mentioned. Even Vizzini sees this strategy of Inigo he will not be sure if two numbers are both lower than $.5$ or higher than $.5$ or one higher one lower and he will need to stick with his strategy.

As a result of these strategies:

Their win chance becomes 50-50, and noone is in favor since getting one lower than $.5$ and the other one bigger than $.5$ is equal to both numbers less than $.5$ and/or both numbers higher than $.5$. Though Vizzini can increase his chance a bit if he stays after getting between $.4$ to $.5$, or change after getting between $.5$ and $.6$. But Inigo can also see this strategy and change his strategy accordingly, then Vizzini can go back to the original methodology, but in the long run, this will not change the actual result. But in the short run, Vizzini will have a slight higher chance to win.