9
$\begingroup$

The starting point for this question is the old chestnut, already discussed on MO, about a game show on which the host has chosen two distinct integers and the contestant gets to reveal one of them at random, upon which the contestant must guess whether the remaining integer is larger than or smaller than the revealed integer.

I would like to suggest that there is a certain precise sense in which the commonsense intuition that the contestant cannot beat the host is correct. As explained in the answers to the other MO question, the usual statement of the puzzle does not yield a precise definition of the "success probability" of the contestant. Allow me to suggest the following interpretation. The game show is repeated a countably infinite number of times. The host strategy is defined as follows: For each $n$, there is a probability distribution $h_{n,T}$ on pairs of distinct integers, that depends on $n$ as well as on the transcript $T$ of what happened on all rounds prior to the $n$th round. In other words, the host's choice of integers in the $n$th round is governed by some probability distribution that is allowed to depend on what the host has observed happen in previous rounds, but is otherwise fixed. Similarly, the contestant strategy is determined by a family of probability distributions $c_{n,T,v}$ that depend on $n$ and $T$ as well as on the value $v$ of the randomly chosen revealed integer.

Under these conditions, we have a clear notion of what it means for the contestant to win any specific round $n$, and once the host strategy and the contestant strategy are fixed, we can talk about probabilities of winning and so forth. Now let me state a key definition:

A contestant strategy beats a host strategy if there exists $\delta>0$ such that $P_n$, the proportion of the first $n$ rounds won by the contestant, converges in probability to $1/2 + \delta$ as $n\to\infty$.

In my opinion, if you tell people that the contestant has a strategy that wins with probability greater than 1/2, many will instinctively interpret your claim in the above sense. That is, they imagine that if the game were played over and over again, the contestant would win more than 1/2 the time in the long run. This certainly seems impossible, especially in the absence of any conditions on the host strategy. If you then clarify that you mean that for any fixed choice of integers, there is a way to beat the host, then this is unsurprising but also seems to miss the point. After all, if the host is required to choose the same pair of integers in every round, aren't there much better strategies than random guessing? Like noticing the pattern after a while and always guessing correctly thereafter?

You may not buy my argument that my definition of "beats" is an intuitively reasonable one, but regardless, let me proceed to the mathematical question:

Is it true that

(a) for every fixed host strategy, there is a contestant strategy that beats it, and

(b) for every fixed contestant strategy, there is a host strategy that it does not beat?

My guess is that the answer to (a) is no and that the answer to (b) is yes, and that it can be proven by a minimax argument, but I don't actually know. Note, of course, that the "standard" contestant strategy that answers the other MO question fails to beat the simple host strategy of deterministically picking $n$ and $n+1$ in round $n$; even though the win probability in every round is strictly greater than 1/2, the probabilities cannot be bounded away from 1/2 and hence cannot yield the desired $\delta$. Note also that allowing randomized strategies is, as usual in game theory, crucial, since deterministic strategies can trivially be defeated.

If I were Lance Fortnow, I would next ask about computationally bounded strategies, but let's not get ahead of ourselves.

$\endgroup$
  • 1
    $\begingroup$ For what it's worth, might it be reasonable to define "success" as for a martingale? Permit the contestant a bet on their success, and the contestant's strategy wins if the contestant's expected bankroll grows without limit. At this point, I think it suffices to ensure that $\delta$ doesn't shrink too slowly - you don't actually need to bound the probabilities away from $1/2$ - but I suspect the classic strategy still loses vs. the $n$-$(n+1)$ deterministic strategy. $\endgroup$ – Eric Astor Oct 17 '14 at 3:16
4
$\begingroup$

Any time the game is played, the host can choose a distribution that makes the contestant's advantage as close to 0 as desired (although not actually equal to 0).

In your multi-round formulation, the host could, for example, behave as follows: in round $n$, choose $k$ uniformly at random from $\{1,2,\dots, n\}$ and declare $\{k, k+1\}$. If the revealed number is $1$ or $n+1$ the contestant can win for sure, and otherwise it's a 50-50 guess. So the contestant's optimal chance of winning in round $n$ (even knowing the host's strategy) is $\frac12+\frac1{2n}$. So indeed (a) no and (b) yes.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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