The Problem of Points

Suppose that Bobby and Patty are playing a game of "Heads or Tails" by flipping a quarter (Patty wins with "Heads" while Bobby wins with "Tails").  They've decided that whoever is the first to win ten games will win the prize, in this case a dollar's worth of change that they found on the sidewalk.  Unfortunately, their parents call them in for dinner before they can finish the game.  Patty has 9 wins, while Bobby has only 7 wins.  What's the fairest way to divide up the dollar's worth of change now?  

Patty argues that because she is winning, she should take home all the money.  Bobby cries out "No fair!" and states that they should just split the money 50/50.  After a few more minutes of arguing, Patty suggests that because she has won 9 out of the 10 games needed to win, she should receive 9/10 of the dollar.  Bobby again cries out "No fair!" and states that using that argument, he should take home 7/10 of the dollar (and not 1/10 as Patty proposes).  Who's correct here?

Actually, mathematicians have been arguing about how to divide up the winnings going back as far as the 15th century.  It's called the "problem of points" or the "division of stakes", and it was first discussed by the mathematician Luca Pacioli (who was a contemporary of Leonardo da Vinci) in his 1494 book Summa de arithmetica, geometrica, proportioni et proportionalità.  Incidentally, this same book also contains the first published description of the double-entry system of accounting, so Pacioli is often referred to as the "father of accounting" (the book actually was plagiarized from the writings of  Piero della Francesca, but that is a topic for another day).  Pacioli solved the problem by dividing the stakes in proportion to the number of rounds won by each player (Patty would have been happy!).

Another Italian mathematician, Niccolò Fontana Tartaglia suggested that Pacioli's method would not be fair if the game was interrupted after the first round (in our example, Patty would have won the dollar after winning just the first game).  He proposed a different way of dividing the stakes based on the ratio between the size of the lead and the length of the game.  Unfortunately, mathematicians soon discovered that this wasn't a perfect solution either.

Here's where history gets even more interesting, at least for me.  The 17th century mathematicians Blaise Pascal and Pierre de Fermat (most famous for his eponymous last theorem) exchanged a series of letters in 1654 in which they discussed how to solve the "problem of points".  Pascal and Fermat started with the insight that the "division of stakes" shouldn't rely on what had already taken place during the interrupted game, but on the possible ways that the game could have finished if it had not been stopped prematurely.  For example, if Patty has a 9-7 lead over Bobby in a game to 10 versus a 19-17 lead in a game to 20, she has similar odds of winning in both games.  In other words, what matters is the number of rounds that each player still needs to win in order to win the game as opposed to the number of rounds he or she has won up to the point that the game is stopped.

Fermat's solution relied upon the fact that if one player needs r more rounds to win and the other needs s rounds to win, the game will have been won by someone after r + s - 1 rounds (work it out, he's absolutely correct!).  By the simple laws of mathematics, these rounds have 2^(r + s - 1) possible outcomes.   Fermat's solution then was to compute the odds for each player to win simply by writing down all of the possible outcomes and counting how many of them would lead to each player winning.  He would then divide the stakes accordingly.

So, to use our example, Patty needs only 1 more win, while Bobby needs 3 more wins.  If the game had not been interrupted, there would have been a winner after three rounds (1+3-1=4-1=3).  There would have been 8 possible outcomes (2^3 = 2 x 2 x 2 = 8), as follows:

In other words, Patty would win 7 out of the 8 possible outcomes (7/8), while Bobby would only win 1 out of the 8 possible outcomes (1/8).  Patty should therefore take home 7/8 of the prize, while Bobby should take home 1/8 of the prize.  But wait, that's kind of ridiculous too, isn't it?  For the first possible outcome in the Table above, why would they still continue to flip the coin since Patty already won?  Just to check that this still works, let's look at only the feasible outcomes:

Let's calculate the probability of Patty winning (remember, with a coin toss there is 1/2 chances of "Heads" and 1/2 chances "Tails"):

P(A) = 1/2

P(B) = 1/2 x 1/2 = 1/4

P(C) = 1/2 x 1/2 x 1/2 = 1/8

By the rules of probability, if you have mutually exclusive events, you add the probabilities.  Therefore, the probability of Patty winning, P(Patty) = 1/2 + 1/4 + 1/8 = 7/8, which is exactly what we found in the case above!

While Fermat's method of solving the "problem of points" works quite well, just imagine having to calculate the probabilities or listing out all of the possible outcomes when the number of rounds required to determine a winner becomes larger!  Here is where Pascal's solution makes things a little easier and involves something that is now called expected value and the arithmetic triangle that now bears his name (Pascal's Triangle).  We will cover Pascal's solution to the  "problem of points" next time.