Thursday, December 29, 2011

138: You Can't Fool Bill Gates

Suppose I were to offer to play a game with you:  from a set of three six-sided dice labelled A, B, and C, we each choose a die.  We then have ten rounds in which we each roll our die, and the higher number wins.  Furthermore, the dice obey the following property:  die A beats die B 2/3 of the time, and die B beats die C 2/3 of the time.  And since I'm such a nice guy, I'll let you choose your die first.  According to a popular anecdote, Warren Buffet challenged Bill Gates to just such a game.  What do you think Bill did?

Intuitively, you might think this is easy.  If die A is better than die B, and die B is better than die C, then you should just choose die A, and you will kick my butt.  However, there is one piece of information you don't have:  die C will also beat die A 2/3 of the time!  So no matter which die you choose, I can then choose one which will probably beat it.   At first, this might seem very odd.  We are used to situations that obey the transitive law:  if A > B, and B > C, then A > C as well.  But there is no reason an arbitrary mathematical operation, such as "has a 2/3 probability of winning against", should obey a transitive law.  A set of three dice with circular victory odds, where die A is likely to beat die B, die B likely beats die C, and die C likely beats die A, are known as "non-transitive dice".

This is not merely theoretical-- it's pretty easy to construct a set of non-transitive dice.  One simple example consists of the following:  let die A contain the numbers 2, 4, and 9; die B contains 1, 6, and 8; and die C contains 3, 5, and 7.  We're repeating each number twice on the dice, so each roll is only selecting among 3 numbers.  The probabilities are easy to calculate:  if we roll two of the dice, there are 3 x 3 or 9 possible combinations.  By enumerating the possible results, we see that A beats B 5/9 of the time, B beats C 5/9 of the time, and C beats A 5/9 of the time.  For example, the five winning combinations of A vs B are (2,1),(4,1),(9,1),(9,6), and (9,8), and the losing ones are (2,6),(2,8), (4,6), and (4,8).

Doing the calculations shows that these numbers are indeed correct.  But why does this situation make sense?  Why don't the probabilities of victory obey a transitive law?  With simple numbers, A>B and B>C implies that A>C.  Why doesn't this work for probability?  The cheap, though accurate, answer is to say we just did the calculations, so trust them & stop bugging me.  But that does seem a bit unsatisfying.  I was actually suprrised how difficult it was to find an answer to this complaint on the web:  many pages describe examples and calculate the possibilities, but nobody seems to attempt a good common-sense explanation.   So here's my best attempt:

I think the intuition is that there are numerous low results which sometimes win locally, but are not great overall.  For example, a 2 on die A will sometimes win against die B, which has a 1, but always lose against die C, where all numbers are 3 or higher.  So the set of winning cases of A vs B does not directly overlap the winners in B vs C.  The high numbers on die A make up for some of the low
numbers. Since you can't accumulate your good results and carry them forward, the fact that A beats B most of the time cannot directly be rolled forward into saying that A beats anything B can beat.   Thus, a transitive law cannot be applied.  I know, a little messy to explain, but I think if you try to enumerate all the cases in the example I mentioned before it will kind of make sense.  If you can come up with a nicer explanation, please email erik@mathmutation.com to tell me about it!

Oh, and to complete the anecdote in my opening:  it turns out that Bill Gates was a little too smart to be fooled by the nontransitive dice.  After he looked at the numbers on them, he agreed to play the game-- as long as Warren Buffett chose first.  Hopefully, next time you are challenged at your local gathering of billionaires, you will be just as clever.

And this has been your math mutation for today.

• Nontransitive Dice at Wikipedia
• Another Article on Nontransitive Dice
• Site that sells nontransitive dice