A paper I wrote for my game theory class about a fascinating paradox.

The St. Petersburg paradox is a famous problem in decision theory about a simple game, played as follows:

1. A coin is flipped repeatedly until, on turn n, it lands on heads.

2. The player is awarded $2ⁿ.

Therefore, in each round the player has a 50% chance of winning $2, a 25% chance of winning $4, a 12.5% chance of winning $8 and so on.

The question is simple: what is a reasonable amount of money to pay to play a round of this game?

Well, a core tenet of decision theory is that any rational person should be willing to pay an amount up to the average payout of the game. However, the St. Petersburg Game is paradoxial: the average payout (expected utility) is infinite.

\[ \begin{aligned} EU &= \sum_{n=1}^{\infty} \frac{1}{2^{n}}\$2^n \\ &= \sum_{n=1}^{\infty}1 \$\\ &= \$\infty\end{aligned} \]

Of course, no reasonable person expects to win an infinite sum. The probability of large payouts is incredibly low and it’s easy to see that most rounds will award less than $10.

On the surface, the answer is simple. It’s irrational to pay a lot to play because the odds of winning a large sum are extremely low. In fancier terms, because the distribution of possible winnings is long-tailed, the mean is a poor measure of central tendency. To illustrate, the following figure and table show the distribution of payouts when one round of the game is simulated for n = 7,900,000 or approximately the global population. While half a dozen people win a billion dollars or more, the overwhelming majority take home only small change.

Clearly, expected utility maximization—a core tenet of classical decision theory—fails for this game. However, if the rational price to pay is not infinite, then what is it?

Historical Solutions

Finite funds

In 1754, Alexis Fontaine presented the paradox to the French Académie royale des sciences . He made the case that since the house cannot possibly have infinite funds the expected value may be calculated. For example, if the house has a bankroll of $1,000,000:

$$\begin{aligned} \text{Rounds}_{\text{max}} &= \log_2{1000,000,000} \\ &\approx 30 \\ EU &= \sum_{n=1}^{30}1 \\ &\approx 30\end{aligned}$$

This solution is sensible albeit dissatisfying. Sure, no real-life house can offer an infinite reward. However, the paradox is that even if they could, no one would be willing to pay the expected value to play.

Expected Utility

A classic resolution, introduced by , makes the important observation that in general, EU ≠ EMV. He proposed a logarithmic utility function where U = ln (MV). Consequently, the paradox can be reformulated as follows:

$$\begin{aligned} EU &= \sum_{n=1}^{\infty}\left(\frac{1}{2}\right)^n\ln\left(2^n\right) \\ &= 2\ln 2 \\\end{aligned}$$ Thus one should be willing to pay e^2ln 2 = $4 to play. Others have extended this idea to consider the player’s existing wealth . $$\Delta EU=\sum_{n=1}^{\infty}\left(\frac{1}{2}\right)^{n}\left[\overbrace{\ln \left(w-c+2^{n-1}\right)}^{\text {utility after the game }}-\underbrace{\ln (w)}_{\text {utility before the game }}\right],$$ where w is the player’s wealth and c is the cost of a round of play.

These solutions and other variations are again sensible. However, they all may be defeated by increasing the payouts. For example, if the utility function is defined to be U = ln (MV), then the payouts are simply increased to $e²ⁿ:

$$\begin{aligned} EU &= \sum_{n=1}^{\infty}\left(\frac{1}{2}\right)^n\ln\left(e^{2n}\right) \\ &= \infty \\\end{aligned}$$

Towards a Better Solution

One may wonder whether a better strategy may be divised when multiple rounds of the game are played. Clearly, in this scenario a rational player should be willing to pay more per round as they have more chance to get lucky.

The figure below plots the average payout per round against the number of rounds played for 5 random simulations. It is interesting to note that while the results vary greatly, in general they seem to follow a linear trendline.

The Steinhaus Sequence

To understand why, it is necessary to restate the problem. To do so, consider an empty sequence of infinite length. Now fill every other empty space with a 2…

$$\begin{bmatrix}{\color{RawSienna} 2} & \_ & {\color{RawSienna} 2} & \_ & {\color{RawSienna} 2} & \_ & {\color{RawSienna} 2} & \_ & {\color{RawSienna} 2} & \_ & {\color{RawSienna} 2} & \_ & {\color{RawSienna} 2}\dots\end{bmatrix}$$

Again, fill every other empty space with a 4…

$$\begin{bmatrix}2 & {\color{RawSienna} 4} & 2 & \_ & 2 & {\color{RawSienna} 4} & 2 & \_ & 2 & {\color{RawSienna} 4} & 2 & \_ & 2\dots\end{bmatrix}$$

Once more, now with 8s…

$$\begin{bmatrix}2 & 4 & 2 & {\color{RawSienna} 8} & 2 & 4 & 2 & \_ & 2 & 4 & 2 & {\color{RawSienna} 8} & 2\dots\end{bmatrix}$$

And so on…

This approach was first proposed by H. Steinhaus, whose sequence represents exactly the expected payouts of the St. Petersburg game. A random draw from elements in the sequence will produce a 2 half the time, a 4 one-quarter of the time, an 8 one-eighth of the time, and so forth. What’s more, values are spaced as they are likely to appear at random. While two large values could in theory appear adjacent to one another, entropy favours an even distribution.

Now, the important observation to make is that if this sequence represents expected payouts of the game then it should also represent a fair price to play. For example, if a rational agent has the opportunity to play 3 rounds then he should be willing to pay $2+$4+$2=$8, or $2.70 per round to play.

The Table below records these values for numbers of rounds equal to powers of two. At 4 rounds, the fair price is $4. At 8 rounds, it’s $5. At 16, $6. Clearly, at pattern has emerged—the fair price is given by \(\log_2n+2\), where n is the number of rounds played. This result is verified by Figure 4. While the cumulative average is less than this value when n is not a power of 2, it is always within $1.

Naturally, these findings should be tested experimentally. Figure 5 overlays the simulated mean payouts over n rounds from Figure 3 with the fair price \(\log_2n+2\) It is remarkably accurate.

Simulations

The following simulations presented in Figure 6 plot the wealth of 1,000 players over 10,000 rounds of the game with per-round fees of (a) $2 and (b) $100.

Clearly, $2 is too low while $100 is too high. However, it is interesting to note the asymmetry in their evolution. At $2, players’ wealth always increases. At $100, however, only the very lucky—represented by horizontal lines on the positive y-axis—can weather the attraction towards debt. However, at the limit, they too will suffer the inevitable s-shaped fall from grace.

By contrast, Figure 7 plots the same simulations with a per-round fee set to \(\log_2n+2\approx\$15\). While players lose money on most rounds, this is offset by the occasional large payout. Consequently, wealth is asymptotically stable—the game is fair.

Conclusion

As with any game of chance, there will never be a completely “correct” solution to the St. Petersburg Paradox. Strategy will always depend on an individual player’s risk tolerance, wealth, and other factors. However, the strategy presented in this paper—that a rational person should be willing to pay $\(\log_2n+2\) per-round—is convincing. While the intersection of people with an interest in logical paradoxes and those will unlimited finances may be too limited to test these strategies in the real world, it is at least a fascinating idea to explore.

Source code for all figures and simulations is available at https://github.com/akoen/petersburg. Made using Julia and Gadfly ¹.