%poker.tex: 
%%a Plain TeX file by   Aek, Mint, and Doron Zeilberger (x pages)
 
%begin macros
\def\L{{\cal L}}
\baselineskip=14pt
\parskip=10pt
\def\halmos{\hbox{\vrule height0.15cm width0.01cm\vbox{\hrule height
  0.01cm width0.2cm \vskip0.15cm \hrule height 0.01cm width0.2cm}\vrule
  height0.15cm width 0.01cm}}
\font\eightrm=cmr8 \font\sixrm=cmr6
\font\eighttt=cmtt8
\magnification=\magstephalf
\def\P{{\cal P}}
\def\Q{{\cal Q}}
\def\1{{\overline{1}}}
\def\2{{\overline{2}}}
\parindent=0pt
\overfullrule=0in
\def\Tilde{\char126\relax}
\def\frac#1#2{{#1 \over #2}}
%\headline={\rm  \ifodd\pageno  \RightHead  \else  \LeftHead  \fi}
%\def\RightHead{\centerline{
%Title
%}}
%\def\LeftHead{ \centerline{Doron Zeilberger}}
%end macros
\centerline
{\bf 
von Neumann and Newman Pokers for Finite Decks
}
\bigskip
\centerline
{\it  Tipaluck KRITAKIERNE, Thotsaporn "Aek" THANTIPANONDA and Doron ZEILBERGER}


{\bf 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 {\it Theory of Games and Economic Behavior} [NM], 
which laid the foundation for groundbreaking mathematical theory of economic and social organization.


{\bf 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 {\it ante}), so now the pot
has two dollars.

Player I looks at his card, and decides whether to {\it 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 {\it bet}, putting 
$b$ additional dollars in the pot. Now the game turns to Player II. He can decide to {\it 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 {\bf brave} and {\it call}, putting
his own $b$ dollars into the pot, that now  has $2b+2$ dollars. The cards are compared in {\it 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 {\it 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.


{\bf The von Neumann advice}:

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

Player II: If $0<x< \frac{b \left(b +3\right)}{\left(b +4\right) \left(b +1\right)}$ you should {\bf fold}, otherwise {\bf call}.

Note that Player II's strategy corresponds to {\it honest common sense}, there is some {\it 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 {\it go for it}.

Now a {\it 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 {\bf not} optimal. If Player I has
a low card, he may {\bf bluff}, and `pretend' that he has a high card, and player II would be intimidated into folding.

{\bf Sad but true}, ``honesty is {\bf not} the best policy''.  Indeed the game favors Player I, and
his expected gain is $\frac{b}{\left(b +4\right) \left(b +1\right)}$ \quad.

When $b=2$, then the advice is 

Player I: if $0<x<\frac{1}{9}$ or $\frac{7}{9}<x<1$ you should {\bf bet}, otherwise {\bf check}.

Player II: If $0<x< \frac{5}{9}$ you should {\bf fold}, otherwise {\bf call}.

The expected value (to Player I) is  $\frac{1}{9}$.

{\bf Finitely Many cards}

What we {\it 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 {\tt FinitePoker.txt}, available, free of charge, from

{\tt https://sites.math.rutgers.edu/\~{}zeilberg/tokhniot/FinitePoker.txt} \quad .


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 

{\tt read `FinitePoker.txt`} \quad.


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

\vfill\eject

{\bf Finding all pure NE}

We didn't make {\it any} assumptions about `plausible' strategies, so {\it a priori}, a strategy for player I can be {\it any} subset, $S_1$, of $\{1, \dots , n\}$,
that advises: `If your card belongs to $S_1$ you should {\bf bet}', otherwise, {\bf check}. Similarly a strategy for player II, $S_2$, can be any such subset,
that tells him to call iff $y \in 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

{\tt EnS1S2(n,S1,S2,b)} .

Using this, we can construct the {\it paytable}, implemented in procedure  {\tt 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 {\it 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, {\tt NE(2,2);} gives
$$
\{[\{\}, \{2\}, 0], [\{2\}, \{2\}, 0]\} \quad,
$$
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$.

{\tt vnME(3,2)} is equally boring, giving the two trivial pairs $[\phi,\{3\}]$ and $[\{3\},\{3\}]$

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

But now comes a nice surprise, {\tt 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, {\tt 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 {\it any} {\it plausability assumptions}, there is only so far we can
go with this naive {\it 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:

{\tt https://sites.math.rutgers.edu/~zeilberg/tokhniot/oFinitePoker1.txt} \quad.

To overcome the {\it exponential explosion}, we can stipulate that Player I strategy {\bf must} be of the form:

``Check iff $x \in \{a,a+1, \dots,b\}$ for some $1\leq a<b \leq n$, ''

while Player II's must be of the form:

``Call iff $x \in \{c,c+1, \dots,n\}$ for some $1\leq c  \leq n$.''

Now we can go much further, see the output file

{\tt https://sites.math.rutgers.edu/~zeilberg/tokhniot/oFinitePoker1A.txt} \quad.

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\leq \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}$.


{\bf Finding mixed NEs}

Thanks to {\bf linear programming} we can go much further by looking at mixed strategy.

A strategy for Player I is given by a vector $[p_1, \dots, 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, \dots, 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 {\it expected payoff} (for Player I), implemented in procedure {\tt PayOffP1P2(n,b,P1,P2)}, as a bilinear form in the $p_x$'s and $q_y$'s.

$$
\frac{1}{n(n-1)}
(\quad \sum_{x=1}^{n} \sum_{y=1}^{x-1} (1-p_x) \, 
-\sum_{x=1}^{n} \sum_{y=x+1}^{n} (1-p_x) \,
+\sum_{x=1}^{n} \sum_{y=1}^{x-1} p_x (1-q_y) \,
$$
$$
+\sum_{x=1}^{n} \sum_{y=x+1}^{n} p_x (1-q_y) \,
+(b+1)  \sum_{x=1}^{n} \sum_{y=1}^{x-1} p_x q_y \,
-(b+1)  \sum_{x=1}^{n} \sum_{y=x+1}^{n} p_x q_y \quad ) \quad .
$$


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

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

{\tt [1/18, .5555555556e-1, [1/3, 0, 1], [0, 1/3, 1]]} \quad .


Translation: 

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

$\bullet$ 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 {\bf definitely check}, while if your card is $3$ then
you should {\bf definitely bet}.

$\bullet$ Player II's strategy is: If your card is $1$, {\bf 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 {\bf definitely call}.

So even with three cards, Player I should bluff!, but only with probability $\frac{1}{3}$.

The output file

{\tt 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 {\tt vnMNE(n,b);} is {\tt 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

{\tt lprint(vnMNE(9,2));} gives:

{\tt [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 {\it much faster} than
{\tt vnNE(9,2)}.

While {\tt vnNE(18,2)} would take for ever (and run out of memory), {\tt lprint(vnMNE(18,2);)} gives  you right away:

{\tt [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$, {\tt lprint(vnMNE(28,4));} gives:

{\tt
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]]} \quad .


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

{\bf 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 {\it Operations Research}, he proposes his own version
of poker, where the bet size is {\bf not} fixed, but can be decided by Player I, including  betting $0$, that is the same as {\it checking}.

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

{\it
\quad 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.
\quad A bets any amount he chooses ($\geq 0$)
\quad B `sees' him (if. calls, betting the same amount) or folds.
\quad 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\geq 2$ and $b\geq 1$ where each player is dealt a card from $\{1, \dots, n\}$ (and the cards are different) and Player I's
option, after looking at his card $x$, what amount in $\{0, \dots, 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, {\it 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 \times (b+1)$ matrix, let's call it $M_1$, $1 \leq x \leq n, 0 \leq j \leq 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 \times (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 {\tt djnMNE(n,b)}; , and the verbose version is {\tt 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

{\tt https://sites.math.rutgers.edu/\~zeilberg/tokhniot/oFinitePoker4.txt}

contains one mixed NE for $1\leq n \leq 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}$.

{\bf References}

[N] Donald J. Newman, {\it A model for `real' poker}, Oper. Res. {\bf 7} (1959), 557-560.

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



\bigskip
\hrule
\bigskip
Tipaluck Kritakierne, Department of Mathematics, Mahidol University, Thailand \hfil\break
Email:{\tt  tipaluck.kri at mahidol dot edu}
\bigskip
Thotsaporn "Aek" Thanatipanonda, Department of Mathematics, Mahidol University, Thailand \hfil\break
Email:{\tt thotsaporn at gmail dot com}
\bigskip
Doron Zeilberger, Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen
Rd., Piscataway, NJ 08854-8019, USA. \hfill\break
Email: {\tt DoronZeil at gmail  dot com}   \quad .
\bigskip

{\bf July 15, 2024} \quad .

\end




















