7
$\begingroup$

I took the following game from the Peter Winkler collection (chapter "Games"):

Two numbers are chosen independently at random from the uniform distribution on [0,1]. Player A then looks at the numbers. She must decide which one of them to show to player B, who upon seeing it, guesses whether it's the larger or smaller of the two. If he guesses right, B wins, otherwise A wins. Payoff to a player is his/her winning probability.

To be clear, let me define a strategy for B as a (measurable) function ${f}_{B}:[0,1]\longmapsto \{larger, smaller\}$, i.e., a strategy for B specifies "larger" or "smaller" for every real in [0,1].

Similarly, A's strategy is a function ${f}_{A}(\{x,y\})$ $=x$ or $y$, i.e., a strategy for A specifies x or y for every $\{x,y\}$ where $x,y\in [0,1]$.

A strategy of A (or B) is called a candidate (for equilibrium), if it prevents the opponent from achieving a winning probability strictly greater than 1/2 no matter what strategy he (or she) adopts. By this definition, the following strategy of A is a candidate (check it yourself):

" ${f}_{A}(\{x,y\})=x$ iff $|x-1/2|<|y-1/2|$"

My question: Are there any other candidates for player A, except those that differ only by a measure zero set from the above?

(P.S., One can show that the candidate for player B is unique, except by a difference of measure zero set. Hence if candidate for A is unique, too, there's a unique (pure) equilibrium.)


Edit: Here's how I prove that candidate for B is unique. I don't know if a simpler argument can be made, or similar reasoning can be used to prove or disprove the case of A.

By definition, B's strategy is to choose measurable $B_L\subseteq[0,1]$ such that he reports larger for $x\in B_L$ and smaller for $x\in [0,1]/B_L$. Now if $m(B_L)=a>1/2$, A can adopt the following strategy:

"Show the smaller number if both $x,y\in B_L$, otherwise show the larger number".

which guarantees her winning probability $\geq a^2+(1-a)^2>1/2$. Hence $m(B_L)>1/2$ can't be a candidate for B. Reversing the strategy shows that $m(B_L)<1/2$ can't be candidate, either. Hence $m(B_L)=1/2$.

Now let $m(B_L)=1/2$. Define $B_S=[0,1]/B_L$. Consider the following incomplete specification of a strategy for A:

"Show the smaller number if both $x,y\in B_L$; show the larger if both $x,y\in B_S$"

which guarantees her winning probability $=1$ in those situations. What about the remaining situations, i.e., $x\in B_L$ and $y\in B_S$?

For any measurable $B\subseteq B_L$ with $m(B)>0$, we can define $C=\{x\in B_S|x>y, \forall y\in B\} $. Suppose there exists such a $B$ such that $m(C)>0$, then A can adopt the following strategy:

"Show the smaller number if both $x,y\in B_L$, otherwise show the larger number"

which will guarantee her winning probability:

P(win)$=$ P(both $x,y\in B_L$ or both $x,y\in B_S$ and win)$+$ P($x\in B_L$ and $y\in B_S$ and win) $\ge$ P(both $x,y\in B_L$ or both $x,y\in B_S$ and win)$+$ P($x\in B$ and $y\in C$ and win) $=1/2+2m(B)m(C)>1/2$

Hence if a strategy of B is to be a candidate, we must have $m(C)=0$. Because $B\subseteq B_L$ was arbitrary, it is true that the set $\{x\in B_S|x>y, \forall y\in B_L\} $ has measure zero. Hence, to conclude, necessary conditions for a strategy of B to be candidate:

  1. $m(B_L)=m(B_S)=1/2$.

  2. $\{x\in B_S|x>y, \forall y\in B_L\} $ has measure zero.

There is only one strategy of B satisfying these conditions (up to measure zero difference), i.e., $B_L=[1/2,1]$. For sufficiency it is easy to check this is indeed a candidate. Hence it is the only candidate for B.

  • 0
    Upon some further consideration, I think the only way to get B's winning percentage up to 50% for the strategy by A that would be least favorable to B would be to allow B's strategy to be defined as "For each number you might be shown, specify the probability with which you should want to keep that number"; in that case, B should specify is strategy as "choose 50% probability regardless of the displayed number". Otherwise, if there exist two numbers where the probabilities are different, A can show whichever number would more likely make B guess wrong.2014-02-23

2 Answers 2

2

This is the only candidate for A up to sets of zero measure.

For a strategy $\def\fa{f_{\text A}}\fa$ to be a candidate for A, the two sets

$B_\lessgtr=\{(x,y)\mid y\in M\land f(\{x,y\})=y\land x\lessgtr y)$

have to be of equal measure for all measurable sets $M\subseteq[0,1]$; otherwise $B$ could do better than average by always guessing that the number presented is the lesser/greater whenever it lies in $M$.

To visualize this, imagine the unit square coloured in black and white, with black signifying that $\fa$ selects $x$ and white that it selects $y$; then at any given height, except for a set of $y$-values of zero measure, there has to be as much white to the left of the main diagonal as to the right.

Now divide the unit square into eight triangles by the diagonals and edge bisectors, and consider the measures of white for the four triangles with $x\lt y$: $a_1$ for $y\lt1/2$, $a_2$ for $1-x\gt y\gt1/2$, $a_3$ for $y\gt1-x\gt1/2$ and $a_4$ for $x\gt1/2$. For convenience, let's normalize these such that each triangle has measure $1$. Then the mirror image of the triangle with white measure $a_i$ has white measure $1-a_i$. Now applying the above principle for $M=[0,1/2]$ and $M=[1/2,1]$ yields, respectively,

$ a_1=1-a_1+1-a_2+1-a_3\;,\\ a_2+a_3+a_4=1-a_4\;. $

Eliminating $a_2+a_3$ leads to $a_1=a_4+1$. Since $a_1$ and $a_4$ are both between $0$ and $1$, this implies $a_1=1$ and $a_4=0$. This determines the strategy in the upper right and lower left quarters (up to a set of zero measure).

Now divide the upper left quarter into four equal squares and denote their white measures by $b_1$ through $b_4$ in Latin script reading order, with the normalization adjusted to scale such that measure $1$ corresponds to a triangle forming half of one of the squares. Then applying the above principle using each of the four quarters of $[0,1]$ for $M$ yields, respectively,

$ b_1+b_3=3\;,\\ b_2+b_4=1\;,\\ b_3+b_4=3\;,\\ b_1+b_2=1\;. $

The first and third equations yield $b_1=b_4$, and then the first and second equations yield $b_3=b_2+2$. Since $b_2$ and $b_3$ are both between $0$ and $2$, this implies $b_2=0$ and $b_3=2$. This determines the strategy in two of the four squares up to a set of measure zero, and the procedure can be applied recursively to determine the strategy in the successively smaller squares remaining. By countable additivity, the union of all the sets of zero measure left over at the stages of this process also has measure zero.

  • 0
    @Eric: This is the part of the proof that I had trouble getting straight in my head :-) I ended up thinking that $M\times M$ gets overcounted, but I've thought it through again now and I think you're right that we don't have to treat it separately -- I've removed that part.2012-03-13
1

Let $f_0(\{x,y\}) = x $ iff $|x-1/2| < |y-1/2|$. Consider the candidate $f_1$ that deviates from $f_0$ on some $\{x_1,y_1\}$. If it does, then it means that $|x_1-1/2| < |y_1-1/2|$ and $f(\{x_1,y_1\}) = y_1$, but then probability that $f_0$ is correct on $\{x_1,y_1\}$ equals $\frac{P(y_1 < x_1 < 1/2) + P(x_1 < 1/2 < y_1) + P(y_1 < 1/2 < x_1) + P(1/2 < x_1 < y_1)}{P(|x_1-1/2| < |y_1-1/2|)} = 1$ because of terms $P(y_1 < x_1 < 1/2)$ and $P(1/2 < x_1 < y_1)$ which would have been absent if $f_1$ wouldn't deviate.

The conclusion is that for every pair $\{x,y\}$ that $f_1$ deviates from $f_0$ the probability is strictly greater than 1/2, so one can split the domain of $f_1$ into $D_1$ being the sets on which $f_1 = f_0$ and $D_2$ being everything else and then integrate: $P(f_0 \text{ is correct}) = \int_{D_1}\frac{1}{2}\ dP + \int_{D_2}1\ dP = \frac{1}{2}P(D_1) + P(D_2)\,,$ but $P(D_1)+P(D_2) = 1$, so if $P(D_2) > 0$ then $P(f_0\ $is correct) > 1/2. Therefore, if $f_1$ deviates too much (i.e. measure of $D_2$ is greater than $0$) then there exists a strategy for $B$ with probability of winning strictly better than $1/2$, and then by the definition $f_1$ is not a candidate.

Hope this helps ;-)

Edit: Fixed some notation problems. Besides, as pointed out by joriki, this proof is not complete, because for $x < 1/2 < y$ strategy $f_0$ doesn't fix the strategy of player $A$. This can be solved as follows: the condition that there would be no strategy $f_B$ that takes advantage of asymmetric choice if $f_1$ can be reformulated into set of formulae: \begin{align*} \forall x < 1/2.\ P(f_1(x,y) = x\ |\ y > 1/2) &= x \\ \forall y > 1/2.\ P(f_1(x,y) = x\ |\ x < 1/2) &= 2y-1 \\ \end{align*} which has only one solution up to measure $0$, i.e. $f_0$. In fact this is exactly the same as second part of joriki's post, so I am not describing the details, his argument is much easier than mine.

  • 0
    @joriki I agree, I had some problems with notation, and there was indeed a huuuge hole in the proof. Many thanks for pointing that out!2012-03-12