The St. Petersburg Paradox: A Fresh Algorithmic Perspective

Ardavan Salehi Nobandegani, Thomas R. ShultzAAAI 2020 · DOI

Abstract

The St. Petersburg Paradox has long challenged normative economic theories, as individuals typically offer small bids for a gamble with infinite expected value. This paper, presented at AAAI-20, proposes a resolution rooted in "resource-rationality." By modeling the human mind as an algorithm that optimizes decision-making under strict computational constraints, the authors demonstrate that human "irrationality" is actually a hallmark of algorithmic efficiency.

The St. Petersburg Paradox

The St. Petersburg Paradox, first described in 1713, involves a simple coin-toss game where the stakes double with every consecutive "tails" until a "heads" appears.

The structure of the St. Petersburg gamble, showing trials, events, and corresponding payoffs.

Mathematically, the expected value (EV) of this game is infinite: $$EV = \sum_{n=1}^{\infty} \left(\frac{1}{2}\right)^n \cdot 2^{n-1} = \sum_{n=1}^{\infty} \frac{1}{2} = \infty$$ Standard rational choice theory suggests a person should be willing to pay any finite amount to play. However, in practice, most people bid only a few dollars. Traditional explanations like diminishing marginal utility or risk aversion often fail to capture specific experimental nuances, such as how bids change with game repetitions or different starting prizes.

Methods: The Rational Minimalist Program

The authors introduce the Rational Minimalist Program (RMP), suggesting that the mind strives for optimality while using the absolute minimum amount of computational resources. They implement this via the Sample-based Expected Utility (SbEU) model.

Instead of calculating an infinite sum, the agent estimates utility using self-normalized importance sampling. Key features include:

  • Optimal Importance Distribution ($q^*$): The algorithm uses a distribution designed to minimize mean-squared error (MSE). This naturally leads to over-weighting extreme, high-payoff events—a behavior often labeled as a cognitive bias but here shown to be mathematically optimal for variance reduction when samples are scarce.
  • Minimal Sampling: To simulate human cognitive constraints, the model uses a sample size of $s=1$.
  • Utility Function: A sublinear utility function is employed where the subjective value of a payoff increases more slowly as the payoff grows, ensuring the game's value remains grounded.

Key Results and Empirical Validation

The model's performance was benchmarked against major experimental findings from existing literature (e.g., Hayden & Platt, 2009; Cox et al., 2007). The SbEU model successfully replicated four major empirical trends.

Model predictions for (a) maximum reward truncation, (b) game repetitions, and (c) initial seed variations.
  1. Truncation Robustness: As seen in Figure (a), bids are only weakly affected by capping the maximum possible win (truncation). The model captures this because, with minimal sampling, the "infinite tail" is rarely encountered.
  2. Linear Scaling with Repetitions: Figure (b) shows that as the number of game repetitions increases, the predicted mean bid increases linearly (Pearson $r = .9998$), matching human data.
  3. Initial Seed Dependence: Figure (c) demonstrates that bids scale linearly with the starting prize but generally stay below the $y=2x$ threshold, consistent with experimental findings.

Discussion and Future Work

This research suggests that what appear to be "biases" in human judgment are often optimal strategies given a very limited "computational budget." By focusing on high-impact outcomes through importance sampling, the mind efficiently reduces the variance of its estimates.

The authors propose that this algorithmic perspective could serve as a blueprint for more human-like artificial intelligence—systems that make rational decisions under the same resource constraints humans face. Future work will explore if this resource-rational approach can resolve other long-standing anomalies, such as the Ellsberg Paradox.

Summary updated

BibTeX
@inproceedings{nobandegani2020st,
  author = {Ardavan Salehi Nobandegani and Thomas R. Shultz},
  title = {{The St. Petersburg Paradox: A Fresh Algorithmic Perspective}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.1609/aaai.v34i09.7122},
}
Figure