von Neumann and Newman Pokers for Finite Decks

Tipaluck KRITAKIERNE, Thotsaporn ”Aek” THANTIPANONDA and Doron ZEILBERGER

Abstract: In his classic book, joint with Oskar Morgenstern, the great John von Neumann, who created game theory, introduced and analyzed a simplified version of Poker. Alas, the ”deck” consisted of infinitely many cards, in fact of all the real numbers between 0 and 1. Here we show the power, of another, even more important, discovery, co-pioneered by von Neumann, the mighty computer, to study, at depth, von Neumann poker with finitely many cards. We also study finite versions of another kind of simplified poker, due to Donald J. Newman.

Welcome to the world of poker, where strategy and probability rule. Picture yourself at the poker table, every decision a crucial step toward victory or defeat. Poker is not just a game of luck; it is a battlefield where strategy and probability rule. It was analyzed by the Hungarian-American mathematician John von Neumann, who believed that real life mirrors poker, involving bluffing and strategic thinking. Together with Oskar Morgenstern, he analyzed poker, resulting in their 1944 book Theory of Games and Economic Behavior [NM], which laid the foundation for groundbreaking mathematical theory of economic and social organization.

von Neumann Poker

In the original version, von Neumann [NM] proposed, and solved, the following game of poker with an uncountably infinite deck, namely all the real numbers between 0 and 1.

Fix a bet size, b.

Player I and Player II are dealt (uniformly at random) two ”cards”, real numbers x and y, in the interval [0, 1]. They each see their own card, but have no clue about the oponent’s card. At the start they each put one dollar into the pot (the so called ante), so now the pot has two dollars.

Player I looks at his card, and decides whether to check, in which case each of the players show their cards, and whoever has the largest card wins the pot. On the other hand he has an option to bet, putting b additional dollars in the pot. Now the game turns to Player II. He can decide to fold, in which case player I gets the pot, resulting with a gain of 1 dollar for Player I, (and a loss of 1 dollar for player II), or be brave and call, putting his own b dollars into the pot, that now has 2b + 2 dollars. The cards are compared in showdown and whoever has the larger card, wins the whole pot, resulting of a gain of b + 1 dollar for the winner, and a loss of b + 1 for the loser.

von Neumann proved that the following pair of strategies is a pure Nash Equilibrium, i.e. if the players both follow their chosen strategy, neither of them can do better (on average) by doing a different strategy.

The von Neumann advice:

Player I: if 0 < x < \frac{b}{(b+4)(b+1)} or \frac{b^{2}+4b+2}{(b+4)(b+1)} < x < 1 you should bet, otherwise check.

Player II: If 0 < x < \frac{b(b+3)}{(b+4)(b+1)} you should fold, otherwise call. Note that Player II’s strategy corresponds to honest common sense, there is some cut-off that below it you should be conservative, and “cut your losses” giving up the one dollar, and not risking losing b additional dollars, and above it, be brave, and go for it. Now a honest common sense would tell you that Player I would also have his own cutoff, check if you card is below it, and bet if it exceeds it. But this is not optimal. If Player I has a low card, he may bluff, and ‘pretend’ that he has a high card, and player II would be intimidated into folding. Sad but true, “honesty is not the best policy”. Indeed the game favors Player I, and his expected gain is \frac{b}{(b+4)(b+1)} . When b = 2, then the advice is Player I: if 0 < x < \frac{1}{9} or \frac{7}{9} < x < 1 you should bet, otherwise check. Player II: If 0 < x < \frac{5}{9} you should fold, otherwise call. The expected value (to Player I) is \frac{1}{9}. Finitely Many cards What we don’t like about this original von Neumann version is that the deck is infinite. In real life there are only finitely many cards, and in fact, not that many. Also von Neumann uses calculus, and integration, way too advanced for us simple folks. We were wondering whether there exists pure Nash equilibria with small decks. We hope that you would download the Maple package FinitePoker.txt, available, free of charge, from

https://sites.math.rutgers.edu/~zeilberg/tokhniot/FinitePoker.txt .

Once you downloaded our Maple package to your laptop, that has Maple, and set the directory to be the one where the package resides, start a worksheet and type

read `FinitePoker.txt` .

we wrote procedure vnNE(n,b), that inputs a positive integer n, at least 2, and a positive integer b, at least 1, and outputs the set of all Nash equilibria. Recall that this set may be empty, since we are talking about pure NEs (from now on NE:=Nash Equilibrium), and we are only guaranteed the existence of mixed NEs. We will talk about mixed NEs later. But for now, let’s explore, taking the bet size, b, to be 2.

Finding all pure NE

We didn’t make any assumptions about ‘plausible’ strategies, so a priori, a strategy for player I can be any subset, S_{1}, of {1, …, n}, that advises: ‘If your card belongs to S_{1} you should bet’, otherwise, check. Similarly a strategy for player II, S_{2}, can be any such subset, that tells him to call iff y ∈ S_{2}. For each conceivable Strategy pair [S_{1}, S_{2}] we can easily compute the expected payoff following these strategies. This is implemented in procedure

EnS1S2(n,S1,S2,b) .

Using this, we can construct the paytable, implemented in procedure PayTable(n,b), that is a 2^{n} by 2^{n} matrix. Now we look for pure NEs, the usual way, but finding, for each strategy of each player the best response of the other player, and looking for pairs [S_{1}, S_{2}] that are best responses to each other.

Let’s fix b = 2.

If the card has only 2 cards, NE(2,2); gives

{[{}, {2}, 0], [{2}, {2}, 0]} ,

so there are two pure NEs. In both of them Player II bets if his card is 2 and folds if his card is 1, while Player I: always check in the first strategy, and checks if his card is 1 in the second.

This is not very interesting, since the expected gain is 0.

vnME(3,2) is equally boring, giving the two trivial pairs [ϕ, {3}] and [{3}, {3}]

vnME(4,2), vnME(5,2), and vnME(6,2) are even more boring, they are empty!

But now comes a nice surprise, vnNE(7,2); gives three pure NEs. For all of them Player I bets iff his card belongs to {1, 6, 7}, but Player II calls if his card is in either {3, 6, 7}, {4, 6, 7}, or {5, 6, 7}. The value is \frac{2}{21}.

Moving right along, vnNE(8,2); also gives you three pure NEs.

For all of them Player I bets iff his card belongs to {1, 7, 8}, but Player II calls if his card is in either \{4, 7, 8\}, \{5, 7, 8\}, or \{6, 7, 8\}. The value is \frac{3}{28}, getting tantalizingly close to von Neumann’s \frac{1}{9}.

Since the sizes of the pay-off matrices grow exponentially, and we didn’t make any plausability assumptions, there is only so far we can go with this naive vanilla approach. But nine cards are still doable. Indeed there are seven pure NEs in this case. For all of them S_{1} = {1, 8, 9}, but Player II has seven choices, all with four members, including, of course, {6, 7, 8, 9}.

For all pure NEs for n from 2 to 10 and bet-sizes from 1 to 5 look at the output file:

https://sites.math.rutgers.edu/ zeilberg/tokhniot/oFinitePoker1.txt .

To overcome the exponential explosion, we can stipulate that Player I strategy must be of the form: “Check iff x ∈ {a, a + 1, …, b} for some 1 ≤ a < b ≤ n, ” while Player II’s must be of the form: “Call iff x ∈ {c, c + 1, …, n} for some 1 ≤ c ≤ n.” Now we can go much further, see the output file

https://sites.math.rutgers.edu/ zeilberg/tokhniot/oFinitePoker1A.txt .

if n is a multiple of 9 then the (restricted) pure NEs are as expected, namely for player I, check if \frac{1}{9}n < x ≤ \frac{7}{9}n, bet otherwise and for Player II call iff x > \frac{5}{9}n. If n is not a multiple of 9, then the values are close, but a little less. For example for n = 26 the value is \frac{36}{325} = 0.110769. For n = 25 the value is \frac{11}{100} = 0.11, for n = 24 it is \frac{61}{552} = 0.1105072464, for n = 23 it is \frac{28}{253} = 0.1106719368, for n = 22 it is \frac{17}{154} = 0.1103896104, while for n = 18 it is exactly \frac{1}{9}. Finding mixed NEs Thanks to linear programming we can go much further by looking at mixed strategy. A strategy for Player I is given by a vector [p_{1}, …, p_{n}] that tells him: if your card is x, bet with probability p_{x}, and check with probability 1 − p_{x}. A strategy for Player II is a vector [q_{1}, …, q_{n}] that tells him: if you card is y, call with probability q_{y}, and fold with probability 1 − q_{y}. It is easy to compute the expected payoff (for Player I), implemented in procedure PayOffP1P2(n,b,P1,P2), as a bilinear form in the p_{x}’s and q_{y}’s.

\frac{1}{n(n − 1)}( ∑_{x=1}^{n} ∑_{y=1}^{x−1}(1 − p_{x}) − ∑_{x=1}^{n} ∑_{y=x+1}^{n}(1 − p_{x}) + ∑_{x=1}^{n} ∑_{y=1}^{x−1} p_{x}(1 − q_{y})

+ ∑_{x=1}^{n} ∑_{y=x+1}^{n} p_{x}(1 − q_{y}) + (b + 1) ∑_{x=1}^{n} ∑_{y=1}^{x−1} p_{x}q_{y} − (b + 1) ∑_{x=1}^{n} ∑_{y=x+1}^{n} p_{x}q_{y} ) .

We now use the commands maximize and minimize in the Maple package simplex, to very efficiently, in each case, find one mixed NE. The procedure is vnMNE(n,b); . Now things get interesting sooner.

Already with three cards, we have bluffing! With bet size 1, typing lprint(vnMNE(3,1)); outputs:

[1/18, .5555555556e-1, [1/3, 0, 1], [0, 1/3, 1]] .

Translation:

• The value of this pair is \frac{1}{18},

• Player I’s strategy is: If your card is 1, bet with probability \frac{1}{3} and check with probability \frac{2}{3}. If your card is 2 then definitely check, while if your card is 3 then you should definitely bet.

• Player II’s strategy is: If your card is 1, definitely fold, if your card is 2, call with probability \frac{1}{3} and fold with probability \frac{2}{3}, while if your card is 3 then definitely call. So even with three cards, Player I should bluff!, but only with probability \frac{1}{3}. The output file

https://sites.math.rutgers.edu/~zeilberg/tokhniot/oFinitePoker3.txt

contains one mixed NE for each of the cases n (size of the deck) from 2 to 40 and b, (size of the bet) from 1 to 10. The verbose form of vnMNE(n,b); is vnMNEv(n,b);, spelling out the advice. Note that a pure NE is also a mixed one, and indeed sometimes we get pure NEs. For example

lprint(vnMNE(9,2)); gives:
[1/9, .1111111111, [1, 0, 0, 0, 0, 0, 0, 1, 1], [0, 0, 0, 0, 0, 1, 1, 1, 1]]

Translation: the value is \frac{1}{9}, Player I: bet iff your card is in \{1, 8, 9\}. Player II: Call iff your card is in {6, 7, 8, 9}. This is much faster than vnNE(9,2). While vnNE(18,2) would take for ever (and run out of memory), lprint(vnMNE(18,2);) gives you right away:

[1/9, .1111111111, [1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1], [0,0, 0,
0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1]].

Again a pure NE, exactly in the von Neumann mold. One more example before we move on to DJ Newman’s poker. With 28 cards and bet size 4, lprint(vnMNE(28,4)); gives:

113/1134, .9964726631e-1, [1, 1, 2/3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 , 0,

0, 0, 0, 0, 0, 0, 1, 1, 1, 1], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 1/3, 1, 1, 1, 1, 1, 1, 1, 1]] .

We will let you, dear reader, do the translation.

DJ Newman Poker

Not as famous as John von Neumann, but at least as brilliant, is Donald J. Newman, the first person to be Putnam fellow in three consecutive years. He was a good friend of John Nash. In a fascinating four page paper [N] in Operations Research, he proposes his own version of poker, where the bet size is not fixed, but can be decided by Player I, including betting 0, that is the same as checking.

In his own words (now the players are A and B) :

A and B each ante 1 unit and are each dealt a ‘hand,’ namely a randomly chosen real number in (0, 1). Each sees his, but not the other’s hand. A bets any amount he chooses (≥ 0) B ‘sees’ him (if. calls, betting the same amount) or folds. The payoff is as usual

But in real life, there is always a finite amount of cards, and no one can bet arbitrarily large values.

We are interested in the finite version.

Input: Integers n ≥ 2 and b ≥ 1 where each player is dealt a card from {1, …, n} (and the cards are different) and Player I’s option, after looking at his card x, what amount in {0, …, b} to bet. In this game the strategies are even larger Player I has (b + 1)^{n} possible strategies, and Player II has 2^{b+1} strategies, so the naive, vanilla way of looking for pure NEs can’t go far. Instead, we will look for mixed strategies right away.

Player I’s strategy space consists of n × (b + 1) matrix, let’s call it M_{1}, 1 ≤ x ≤ n, 0 ≤ j ≤ b, where M_{x,j} is the probability that if he has card x, he would bet j dollars (of course they have to add up to 1). Player’s II’s strategy is also an n × (b + 1) matrix, let’s call it M_{2}, where M_{2}[y, j] is the probability of calling if his card is y and the bet proposed by Player I is j. So now we have 2n(b + 1) variables for the minmax problem rather than 2n. We can still go pretty far. Once again, it is easy to compute the expected payoff as a bilinear expression in all these variables, subject to the appropriate constraints.

This is implemented in procedure djnMNE(n,b); , and the verbose version is djnMNEv(n,b);.

We noticed that for any given n, there exists a maximal bet size after which the game as the same value. The output file

https://sites.math.rutgers.edu/~ zeilberg/tokhniot/oFinitePoker4.txt

contains one mixed NE for 1 ≤ n ≤ 10 and for all b until it saturates. As n grows larger, and b reaches its saturation value, the value of the game seems to converge to the DJ Newman ‘continuous’ value \frac{1}{7}.

References

[N] Donald J. Newman, A model for ‘real’ poker, Oper. Res. 7 (1959), 557-560.

[NM] John von Neumann and Oskar Mrogenstern, “ Theory of Games and Economic Behavior (1944) , John Wiley 1964, 189-219.

Tipaluck Kritakierne, Department of Mathematics, Mahidol University, Thailand

Email:tipaluck.kri at mahidol dot edu

Thotsaporn ”Aek” Thanatipanonda, Department of Mathematics, Mahidol University, Thailand

Email:thotsaporn at gmail dot com

Doron Zeilberger, Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen Rd., Piscataway, NJ 08854-8019, USA.

Email: DoronZeil at gmail dot com .

July 15, 2024 .