Simulating uncertain decisions with python and petersburg

In the 17th century, salon mathematicians wrestled with a puzzle called the problem of points. In this puzzle, two players are playing some game, but must quit early, and therefore have to divide the remaining pot in a fair way. Over the centuries, many proposed different solutions with no consensus on a true solution. Eventually in 1654 Blaise Pascal proposed that the value of a future gain is directly proportional to the chance of getting it. More formally: the expected value is the sum of all potential outcomes multiplied by their probability of occurring. This method is referred to today as the Expected Value.

In 1738 Daniel Bernoulli published an argument in Commentaries of the Imperial Academy of Science of Saint Petersburg with counterpoints against Pascal's wager. He wrote of a game where a casino tosses a fair coin repeatedly. The pot starts at 2 dollars, and is double every time the coin comes up heads. When the coin comes up tails, the game ends, and the player receives whatever has accumulated in the pot. So if the first toss results in tails, the player receives 2 dollars, and if the first tail comes up on the 10th toss, the player receives 2^{10} dollars.

The question Bernoulli then posited was: what is a fair price to pay to play this game?

Using Pascal's method, the expected value of the game can be calculated easily:

E= frac{1}{2}cdot 2+frac{1}{4}cdot 4 + frac{1}{8}cdot 8 + frac{1}{16}cdot 16 + cdots

E = 1 + 1 + 1 + 1 + cdots

E=infty

 

This of course, is absurd. No rational player would ever play the game if the entrance fee were 1 million dollars, but Pascal's expected value indicates that this would be a shrewd investment. This is because if you have an infinite amount of money to play over and over, and the casino has an infinite amount of money to pay you with, and you have an infinite amount of time to play, you will eventually find that the unbounded potential gain dominates any finite cost to play.

In reality, the casino likely has some maximum payout per hand, at which jackpots are capped.  In these cases, there is a finite expected value, that can be calculated directly.

In order to explore these kinds of problems, I wrote a small python library: petersburg.  In petersburg, these kinds of games are represented as Directed Acyclic Graphs, where each node is a state with some payoff (positive, negative or zero), and the states/nodes are connected by edges with weights and costs.  The weights describe the likelihood of that path being taken, while the cost describes the cost (positive, negative, or zero) of traveling along that path.

In this way, we can model finite versions of the St. Petersburg game for different bankrolls.  Each node is a flip, which has 2 edges of equal weight coming out of it (representing the fair coin flip).  One edge leads to a payoff and the end of the game (for a tails flip) and the other leads to the next node, with 0 cost.  This whole graph is pre-pended by a node with 1 edge to add in the entrance fee as an edge cost.  So to cap the bankroll of the casino, we simply limit the depth of this graph.  Then by simply simulating the game until convergence, we get an approximate expected value for the game.

In code (using a small bankroll):

from petersburg import Graph

g = Graph()

bankroll = 100
entrance_fee = 0
gd = {1: {'payoff': 0, 'after': []}, 2: {'payoff': 0, 'after': [{'node_id': 1, 'cost': entrance_fee}]}}
nn = 3
idx = 0
payoff = 2 ** (idx + 1)
while payoff <= bankroll:
    node_id = 2 * (idx + 1)
    gd[nn] = {'payoff': payoff, 'after': [{'node_id': node_id, 'cost': 0, 'weight': 1}]}
    nn += 1
    gd[nn] = {'payoff': 0, 'after': [{'node_id': node_id, 'cost': 0, 'weight': 1}]}
    nn += 1
    idx += 1
    payoff = 2 ** (idx + 1)

g.from_dict(gd)

outcomes = []
for _ in range(10000000):
    outcomes.append(g.get_outcome())

print('nnExpected value of game with a $%d bankroll' % (bankroll, ))
print(float(sum(outcomes)) / len(outcomes))

We get an output of about $6.  In fact, using this logic (the casino has an infinite amount of money in the basement, but has a maximum jackpot per hand, allowing many instances of that jackpot), we can calculate the expected value at a few scales:

Max Jackpot Expected Value
$100 $6.00
$1,000,000 $21.61
$10,000,000,000 $23.47
$79,200,000,000 $32.97

It turns out, we can model many things with this framework, which is still under active development, so check out https://github.com/wdm0006/petersburg and let me know what you think, or what I messed up (more likely).

Will

Will has a background in Mechanical Engineering from Auburn, but mostly just writes software now. He was the first employee at Predikto, and is currently building out the premiere platform for predictive maintenance in heavy industry there. When not working on that, he is generally working on something related to python, data science or cycling.

7 Comments

Leave a Reply