Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
Is that really the right definition of strategy? In particular, you exclude randomized strategies, such as "B makes his choice by flipping a fair coin, without looking at the number he was given". –  Hurkyl Mar 12 '12 at 6:55
    
@Hurkyl: Yes I exclude randomization, to focus on pure strategies. I'm interested in possible pure strategy equilibria, and to what extend can a player use a pure strategy to substitute his random one in random equilibria, which is the reason I defined the term "candidate". To those purposes, I think it's irrelevant if you include random strategies or not. Besides, without a full discussion of possible candidate strategies, we can't fully understand the family of random equilibria either. –  Eric Mar 12 '12 at 7:22
    
What does "Payoff to a player is his/her winning probability" mean? –  Henry Mar 12 '12 at 8:25
    
@Henry: You can just ignore that sentence. It simply means that players are rational and seek out to maximize his/her own probability of winning. –  Eric Mar 12 '12 at 9:12
    
I'm unclear why B's given strategy is a candidate (or why any strategy for B can be a candidate given your definitions). I would think the probability that either none or both numbers will be in $B_L$ will be at least 50% no matter what set is chosen, and if exactly one number is in the $B_L$, then B has a 50% chance of winning no matter what A does. Since A can choose his strategy to win all the cases where neither or both values are in $B_L$, that that for any fixed strategy B might choose, A could pick a strategy where A wins 75% of the time. –  supercat Feb 23 at 21:16
show 1 more comment

2 Answers

up vote 2 down vote accepted

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.

share|improve this answer
    
:"whereas the measure of $P\times P$ would go as $1/n^2$, so that for sufficiently large n the difference would allow B to do better than average..." Why consider $P\times P$ here? You meant both x and y in $P$? @joriki –  Eric Mar 13 '12 at 3:19
    
@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. –  joriki Mar 13 '12 at 8:20
add comment

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.

share|improve this answer
    
It is simpler than I thought. Thank you! –  Eric Mar 12 '12 at 11:24
    
I don't understand this answer in several respects. a) What is $f_{\text{B}}$? Is it an arbitrary strategy for B or a specific one? b) What is "the probability that $f_{\text{B}}$ is correct on $\{x_1,y_1\}$"? The only probabilities we have are the ones from the draw, since the strategies aren't probabilistic; so the probability that $f_{\text{B}}$ is correct on $\{x_1,y_1\}$ is always either $0$ or $1$, right? c) Where does the $1/2$ on $D_1$ come from? Don't you have to specify $f_{\text{B}}$ to determine that? –  joriki Mar 12 '12 at 12:25
    
@joriki:a)I think by ${f}_{B}$ he meant the strategy "guess larger iff in [1/2,1]"; b)Indeed the probability is just 1; c) Right... the 1/2 can't be explained. Thank you for your answer. I'll look at it later. Haven't got time now. –  Eric Mar 12 '12 at 13:36
    
@Eric: If that's what's meant by $f_{\text B}$, then an argument focussing on that strategy corresponds to the first part of my answer, which fixes A's strategy in the case when the two numbers are in the same half. A's strategy in the other case isn't fixed by this $f_{\text B}$, since with that strategy B wins that case anyway, regardless of what A does. The second part of my answer corresponds to considering increasingly refined strategies for B that successively fix A's strategy. –  joriki Mar 12 '12 at 13:58
    
@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! –  dtldarek Mar 12 '12 at 17:21
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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