2 Problem of Points

2.1 Overview

My brother once told me about a story from the early days of probability theory. It involved Blaise Pascal and Pierre de Fermat writing letters to each other in 1654 about how to settle a theoretical game that was prematurely ended before a winner could be declared. In one variation of the game, two gamblers have each wagered 32 pistoles (gold pieces) in a game where the first person to win 3 rounds wins. Each player has a 50/50 chance of winning each round, but the game is prematurely ended at a point where one player has 2 wins and the other has 1 win. The problem is: what is the fairest way to divide the 64 pistoles?

This question of how to divide the winnings of an unfinished game is called “the problem of points” or “the division of the stakes”. There is a good Wikipedia article on it here. It is mentioned that a naive solution such as “divide the winnings based on the proportion each player has won so far” is flawed because a player who has won only a single game will get the entire reward if his opponent has not won at all. This will be true even if there are many games left to play such that the overall advantage the first player has won is negligible.

Intuitively, it is reasoned that the answer must be based on the number of games left to play and the relative advantage one player has over the other. For instance, in a game to 10, if the first player has won 7 times and the second player has won 5 times, the situation is essentially the same as a game to 20 where the first player has 17 and the second has 15. In each case the first player needs to win 5 games to win and the second player needs to win 7. These are the numbers that intuitively should matter and the division of winnings should be the same in both of these scenarios.

2.2 Solution

The solution can be found by exploring every possible way that the remaining games could be played out and seeing how many of these result in each player winning. This was the method that Fermat used in his solution. We can write a simple recursive function in Python to compute this:

def get_expected_value(p1_wins, p2_wins, goal):
    """Return the probability that player 1 wins given that player 1 currently
    has p1_wins and player 2 has p2_wins and that the game is won when they
    reach "goal" number of wins.
    """

    if (p1_wins == goal):
        return 1
    elif (p2_wins == goal):
        return 0

    p1 = get_expected_value(p1_wins + 1, p2_wins, goal)
    p2 = get_expected_value(p1_wins, p2_wins + 1, goal)

    return (p1 + p2) / 2

This yields the following solutions for some of the cases we have discussed:

P1 Wins	P2 Wins	Goal	Pr(P1 Wins All)
7	5	10	77.34375%
17	15	20	77.34375%
2	1	3	75%
5	3	6	87.5%

In general, you can also use the following equation to find the probability of player 1 winning if player 1 has \(s_1\) rounds left to win and player 2 has \(s_2\) rounds left to win where \(p_1\) is the probability of player 1 winning a game and \(p_2\) is the probability of player 2 winning:

\[ \sum\limits_{k=s_1}^{s_1+s_2-1}{\frac{s_1+s_2-1}{k}(p_{1})^{k}(p_{2})^{s_1+s_2-1-k}} \]

2.3 Inferring a Player’s Advantage

In the classical form of the problem, we assume that each player has an equal chance of winning a round, but what if that was not the case? If we are playing to 1,000 and one player has won 750 times to the other player’s 100, should we infer that the first player is actually better than the second and more likely to win future matches?

This problem is essentially identical to the coin flipping problem. We want to estimate the probability of each player winning future rounds based on their past performance. We can use the maximum likelihood estimate that simply uses the percentage of past wins as the predictor of future probabilities. We could also start with a Bayesian prior and update that based upon the observed data. In this case there are an infinite number of ways to setup the prior probabilities, and thus an infinite number of ways to solve this problem based upon not only the observed data but our prior expectations about how fairly matched the players are.

2.4 Historical Notes

The actual text of the letters between Pascal and Fermat can be found here. There is also a good overview in the American Physical Society’s article “This Month in Physics History” subtitled “July 1654: Pascal’s Letters to Fermat on the Problem of Points”(Volume 18, Number 7, July 2009). This goes into more detail about how the problem was first proposed in 1494 by an Italian monk named Luca Paccioli. The question was being pondered in 1654 by an amateur mathematician who enjoyed gambling named Antoine Gombaud. It was Gombaud who asked his friend Pascal, who also had taken an interest in gambling, and it was this question that spurred the letters.

The original question that Paccioli asked concerned a game of “balla”, which requires six goals to win the game, shoul d be settled if the game is stopped when one player has 5 goals and the other has 3.