Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. 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.

One easily identifies the following mixed strategy Nash equilibrium:

"Player A shows the larger number with prob 1/2 and player B guesses 'larger' with prob 1/2"

The book also suggests a smart pure strategy for A, which is in effect identical to her mixed strategy above (in the sense that locks her winning prob at 1/2 regardless of B's strategy):

"Player A shows the number which is closer to 1/2"

A little thought shows that B also has a pure strategy in like manner:

"Player B guesses larger iff the number he sees exceeds 1/2"

Together these two strategies form a pure strategy Nash equilibrium.


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

Similarly, A's pure strategy is a function $f_A(\{x,y\})=x\ or\ y$, i.e., she assigns x or y to every set $\{x,y\}$, where $x,y\in [0,1]$.

My question is: Is the above pure strategy Nash equilibrium unique? Given the above definition, there are infinite pure strategies for each player. Could other less obvious or highly artificial equilibria be constructed? How can we prove or disprove the uniqueness of equilibrium from those infinite strategies?

Edit: To avoid possible ambiguity in Steven's answer, I add the last sentence in the 2nd paragraph.

share|improve this question
add comment

2 Answers

I think you're going to have to be careful about what you mean by equilibrium.

Definition 1: $(f_A,f_B)$ is an equilibrium if, taking $f_B$ as given, $f_A$ maximizes the expected value of $A's$ payoff to $(-,f_B)$ (and symmetrically).

Definition 2: $(f_A,f_B)$ is an equilibrium if, for every $(x,y)$, taking $f_B(x,y)$ as given, $f_A(x,y)$ maximizes $A's$ payoff to $(-,f_B(x,y))$ (and symmetrically).

In the first case, you are looking for the equilibrium in a single game. In the second case, you are looking for a family of equilibria in a family of games (parameterized by $(x,y)$).

If I take literally your request for equilibria in "this game" (singular), it would seem that Definition 1 applies. In that case, you can start with your Nash equilibrium, vary either player's strategy arbitrarily on any set of measure zero, and have another Nash equilibrium.

share|improve this answer
    
Thank you for reminding. Yes it's Definition 1 --- otherwise there's no need for the requirement "uniform distribution on [0,1]". But while varying ranges of equilibrium $f_A$ and $f_B$ on measure zero sets trivially leads you to a different equilibrium by the definition, is a more essential change possible? –  user16033 Mar 7 '12 at 16:36
add comment

Given that calculation of probability is involved. It is appropriate to restrict strategies to be measurable functions.

"Player B guesses larger iff the number he sees exceeds 1/2". Denote this strategy of B ${S}_{B}^{*}$.

The first part of the argument proves (I hope) that ${S}_{B}^{*}$ is the only kind of pure strategy (except by a difference of measure zero) that B can adopt in any pure strategy equilibrium. The second part proves A's corresponding pure strategies for ${S}_{B}^{*}$. Their combinations then form all possible pure strategy equilibria.


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

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

which guarantees her a winning probability $\geq a^2+(1-a)^2>1/2$. To counter this strategy of A, B's better off reverting to ${S}_{B}^{*}$. Hence $m(B_L)\neq1/2$ can't be an equilibrium pure strategy for B.

Now let $B_L\subseteq[0,1]$ and $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 already guarantees winning probability $\geq1/2$ for A. 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 pure strategy:

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

which will guarantee her winning probability $\geq 1/2+2m(C)m(B)>1/2$, which can't be an equilibrium pure strategy for the same reason as in the $m(A_L)\neq 1/2$ case. Because $B\subseteq B_L$ was arbitrary, we then know in a pure strategy equilibrium it is necessary that the set $\{x\in B_S|x>y, \forall y\in B_L\} $ has measure zero. Hence, to conclude, necessary conditions for strategies of B in a pure equilibrium:

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

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

However, we already know ${S}_{B}^{*}$ and its possible variations on measure zero sets are strategies that B can adopt in a pure strategy equilibrium. Since these are exactly those strategies that satisfy 1 and 2. We conclude the only pure equilibrium strategy for B is ${S}_{B}^{*}$ (except by a difference of a measure zero set).


Given ${S}_{B}^{*}$, as long as $x\in [0,1/2]$ and $y\in (1/2,1]$, choice of $f_A$ is irrelevant, and player B will guess correctly. Since this happens with probability 1/2, the best A can do is to salvage all remaining situations, which amounts to show the smaller one if both numbers fall into (1/2,1] and larger one if both into [0,1/2], and achieve a winning probability of 1/2.

And this should include all possible pure strategy equilibria.

share|improve this answer
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.