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

beatsa 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.