This puzzle, which appeared on the blog associated with the cute webcomic xkcd, would make a good exercise in a game-theory course:
Alice secretly picks two different real numbers by an unknown process and puts them in two (abstract) envelopes. Bob chooses one of the two envelopes randomly (with a fair coin toss), and shows you the number in that envelope. You must now guess whether the number in the other, closed envelope is larger or smaller than the one you’ve seen.
Is there a strategy which gives you a better than 50% chance of guessing correctly, no matter what procedure Alice used to pick her numbers?
A good start is to notice that the possibility that Alice may randomize is a red herring. You need a strategy with a greater than 50% chance of winning against any pair she may choose. If you can do this, it takes care of her randomized strategies for free. (A familiar argument to those who enjoy computing values of zero-sum games.)
The Leisure of the Theory Class 
9 comments
March 25, 2011 at 2:36 pm
Dave B
Just take any strictly increasing function p: R -> (0,1) and guess that the number in the other envelope is smaller with probability p(envelope). If the smaller and larger number are S and L respectively, the probability of getting it right is (1-p(S))/2 + p(L)/2 = 1/2 + (p(L)-p(S))/2, and p(L)-p(S) > 0 since p is strictly increasing.
March 28, 2011 at 10:46 am
anonymous
Hi
I just stumbled upon this page.. I don’t understand your answer. How do you know you’ve to choose a strictly increasing function? why do you expect a layman to understand the solution? can you please help me understand this?
Thanks in advance.
March 25, 2011 at 2:59 pm
Jonathan Weinstein
Exactly right. Here’s a follow-up exercise: For any
, give a strategy for Alice which prevents you from winning more than 
of the time. The game, which has a non-compact strategy space, does not exactly have a minimax value, but if you replace min and max by sup and inf it has value .5. Is there a term for this? Sup-inf value?
March 25, 2011 at 4:04 pm
Ori
value.
March 25, 2011 at 4:29 pm
Jonathan Weinstein
That *is* a good term for it :-). It just felt like some adjective might be appended to denote that you can only guarantee yourself
-close to the value. I’m not up on the most general forms of these theorems, but I guess there are results out there showing that sup-inf = inf-sup for a broader class of games than the classic minimax results. My excuse is that I think most of the interesting lessons come from games with finite or compact action spaces anyway :-).
We seem to have a sharper readership than xkcd, where people were still debating whether the answer above was really right after 300 comments :-).
March 25, 2011 at 6:11 pm
Dave B
Suppose you have n+1 values in increasing order: v1,v2,…,v(n+1). Choose one of the pairs vi,v(i+1) uniformly at random. If Bob says that vi is larger with probability p(i), then the probability that Bob wins is sum(1/2 + (p(i+1)-p(i))/2)/n, which is a telescoping sum that works out to 1/2 + p(n+1)/2n – p(1)/2n, which is at most 1/2 + 1/n. So set n to at least 1/epsilon.
Sorry about the ugly math above, but since there’s no preview button, I can’t be sure that my attempts at typesetting math properly would work.
I just checked out the XKCD post, and it’s crazy that people would still be arguing over something this simple (if a bit unintuitive) more than a year after the original post. Then again, it only takes a little searching to see people angrily disagreeing over the Monty Hall problem or whether the repeating decimal 0.(9) equals 1.
March 25, 2011 at 7:37 pm
Afinetheorem
Not too surprising…Erdos famously didn’t believe the Monty hall result! As for this problem, anything involving infinity is going to be nontrivial if you don’t have a good math background. E.g. Why would you suspect there even exists such a strictly increasing function from R? There is no way this is trivial to a laymen especially if it leads to “paradoxical” results of the type shown…
March 25, 2011 at 8:33 pm
Dave B
I am always surprised by the way people will reject the result of a simple, concise, valid proof in favor of their initial reaction. I by no means expect the average XKCD reader to be able to find a strategy with greater than 50% probability of success, but they should at least be able to accept the demonstration of such a strategy. From the bit I read, people weren’t arguing about whether strictly increasing functions from R to (0,1) exist or anything else to do with the proof itself. All I saw was people saying that the proof must be wrong because there’s no way to know whether the number in the other envelope is higher or lower.
March 26, 2011 at 11:29 am
Jonathan Weinstein
Dave,
Agree wholeheartedly…the first thing to teach people about probability is that the answers will often surprise them and they should change their intuition, not the answers :-). In this particular case, I have a little sympathy for someone who doesn’t see the proof as airtight, for the following reason: It is clear that the algorithm gives >.5 winning probability against any fixed pair chosen by Alice…but to show that it also does so against any randomization from Alice takes a little technical care. Basically you need to say that the set of pairs A can be partitioned so that A_n is the sets of pairs where your edge is between 1/(n+1) and 1/n, then by countable additivity she must assign positive mass m to some set A_n, then this gives you a strictly positive edge of at least m/(n+1).