Note to the Teacher: This is just an introduction to both games with arbitrary parameters. the analyses are done later, seperately, either in student projects or in text pages.
Prerequisites: Chapters 1, 2, 3, 4, 5, 6, and 7.
Finally a chapter on poker! Now we will learn how to play it well and make a lot of money, right? If this was your thought, I am sorry that I have to disappoint you. Advice on poker is possible, but for a complete mathematical analysis, the game is again much too complex. What we can and will do is to analyze several toy variants, which can be analyzed. This chapter will just introduce the games, and do a few steps towards the analysis. Complete analysis of special cases will be done in later chapters.
The two families of games described and partially analyzed in this chapter are classics. What I call VNM POKER has been introduced by von Neumann and Morgenstern in their monograph [von Neumann/Morgenstern]. KUHN POKER (in the variant (3,1,1,2)) was introduced by Kuhn in [Kuhn 1950].
In both games we have four parameters, S, r, n, and m, with m < n. There are cards of value from 1 to S in a deck, and each value occurs r times. So overall there are S·r cards. There are only two players, Ann and Beth. Each player randomly gets a card from the deck, looks at her card, but doesn't show the value to the opponent. The ante is m, meaning that both player put m dollars into the pot as initial bet. The bet could be raised to the higher level n.
VNMPOKER(S,r,m,n): Ann moves first by either checking (playing for m) or raising (playing for n).
KUHNPOKER(S,r,m,n): These games extend VNMPOKER insofar as, if Ann checks, the players enter VNMPOKER with Ann and Beth playing reversed roles. Again Ann moves first by either checking or raising.
Both games are zero-sum. Before we find the reduced normal forms of both games, let us show the extensive form, since with them the descriptions above may become a little clearer. Actually let's look first at "modules", which describe the moves of Ann and Beth. Such modules are combined to give the full extensive form for the games.
 |
 |
Note that both VNMPOKER and KUHNPOKER start with the random move of giving both players a card. Ann can get any of the cards 1,2,...S, and Beth as well (provided r>1), thus there are S2 different alternatives if r>1, and S·(S-1) alternatives if r=1. The parameters S and r influence the shape of the game tree, the number of modules contained, and also the probabilities for the different options of the random move. The payoffs obviously depend on m and n.
The alternatives for the initial random move are not all equally likely. All alternatives with equal cards for Ann and Beth have the probability
Here are four examples of extensive forms of these games. Can you identify the modules? Note that the information sets span different modules and, like threads in a fabric, hold the whole game firmly together. There are no subgames.
What is a strategy for Ann and Beth? Although there are usually, if r > 1, S · S different ways of dealing one card to Ann and one to Beth, Ann can see only her card and has therefore S information sets. In each of these situations she can check or raise. Therefore Ann has 2S pure strategies, all of them reduced, since she has only one move. Again we display these strategies by sequences of "R"s and "C"s--- for instance "RCCR" for S=4 means that Ann raises with the lowest and the highest card and checks with the two middle-valued cards.
What pure strategies does Beth have? In case Ann checks, Beth doesn't have a choice, so it suffices to consider the other case, when Ann raises. Since Beth sees her own card but not Ann's card, Beth has S information sets. In each of them she will either call or fold. So she also has 2S pure strategies, again all reduced. Again the strategies are encoded by sequences of "C"s and "F"s---"FFCC" for S=4 means that she folds with the two lower-valued cards and calls with the two higher-valued cards.
In order to find the payoff for Ann if both players use a given pure strategy, we have to use the weighted average of Ann's payoffs in the S·S different card distribution cases, where the weights are the probabilities pXX or pXY described above. The payoffs are obviously m, 0, or -m in the case where Ann checks, m in case Ann raises and Beth folds, and n, 0, or -n in the case where Ann raises and Beth calls. For example, if S=2, and if Ann plays CR and Beth CC, Ann's expected payoff equals
To give another example, if S=3 and Ann plays RCR and Beth plays FCC, then Ann's expected payoff equals
Fortunately some of these pure strategies are weakly dominated. When Ann holds a highest valued card, raising is not worse than checking. Any of Ann's strategies "X...YC" where Ann would check with a card of highest value S would be weakly dominated by the strategy "X...YR" that coincides with "X...YC" in all information sets except the one for the card value S, where Ann would raise. When Beth holds a highest valued card, calling dominates folding. Any of Beth's strategies "X...YF" with Beth folding with a card of value S would be weakly dominated by "X...YC" the strategy identical to "X...YF" except for the information set holding a card of value S, where Ann would raise. Thus, in the case S=4, out of the 16 strategies for Ann and Beth, only the 8 strategies CCCR, CCRR, CRCR, CRRR, RCCR, RCRR, RRCR, RRRR, for Ann, and only the 8 pure strategies FFFC, FFCC, FCFC, FCCC, CFFC, CFCC, CCFC, CCCC, for Beth are not obviously weakly dominated.
Domination between Beth's strategies is even more frequent than that:
Proof: Actually we will show that a pure strategy for Beth, let's call it the original strategy, to call with card value "i" and fold with card value "i+1" is weakly dominated by the modified "flipped" strategy, where everything remains the same except that now Beth folds with a card value of "i" and calls with card value "i+1". For instance, "CCFC" is dominated by "CFCC" (i=2), which itself is dominated by "FCCC".
Out of the S·S terms that add to Beth's payoff, all are the same for the two strategies
except those 2S for card values "i" and "i+1" for Beth.
Let's call the term referring to a card of value x for Ann and a card of value y for Beth
the "(x,y)-term".
Since the two card values i and i+1 behave the same (both are larger or both are smaller)
towards cards of value k different to i and i+1,
every such (k,i)-term for one of the two strategies of Beth
equals the corresponding (k,i+1)-term for the other strategy.
Therefore all contributions to the payoff except the four where Ann and Beth
both have cards of value "i" and "i+1"
can be matched in both strategies.
All what remains to be done is to compare these four parts,
the (i,i)-term, the (i,i+1)-term, the (i+1,i)-term, and the (i+1,i+1)-term
of Beth's payoff in the two strategies.
Thus for S=3, only Ann's pure strategies CCR, CRR, RCR, and RRR are not necessarily dominated, and only Beth's 3 pure strategies FFC, FCC, and CCCC are not necessarily dominated. The matrix below shows Ann's payoff for S=3, r=4, m=1, n=4:
| . | FFC | FCC | CCC |
| CCR | 0.000 | 0.364 | 0.727 |
| CRR | -0.273 | 0.000 | 0.727 |
| RCR | -0.030 | -0.273 | 0.000 |
| RRR | -0.303 | -0.636 | 0.000 |
This game has a Nash equilibrium of CCR versus FFC. Another Nash equilibrium is CCC versus FFC---note that CCC is weakly dominated by CCR, but still that doesn't prevent it being part of a Nash equilibrium.
Why does Ann not bluff? The reason seems to be that the raised bet of value 4 is just too high, compared to the initial bet of value 1. For smaller ratios n/m, we will not get a pure Nash equilibrium.
For a second example, for S=4 only the 4 pure strategies FFFC, FFCC, FCCC, and CCCC remain for Beth. The matrix in that case, for r=4, m=3, n=5, is shown below.
| . | FFFC | FFCC | FCCC | CCCC |
| CCCR | 0 | 4/30 | 4/15 | 4/10 |
| CCRR | 1/60 | 0 | 4/15 | 8/15 |
| CRCR | 5/12 | 1/60 | 0 | 4/15 |
| CRRR | 13/30 | -7/60 | 0 | 4/10 |
| RCCR | 49/60 | 5/12 | 1/60 | 0 |
| RCRR | 5/6 | 17/60 | 1/60 | 4/30 |
| RRCR | 37/30 | 3/10 | -1/4 | -4/30 |
| RRRR | 5/4 | 1/6 | -1/4 | 0 |
| . | FFFC | FFCC | FCCC | CCCC |
| CCCR | 0 | 4/30 ≈ 0.133 | 4/15 ≈ 0.267 | 4/10 = 0.400 |
| CCRR | 1/60 0.017 | 0 | 4/15 ≈ 0.267 | 8/15 ≈ 0.533 |
| CRCR | 5/12 ≈ 0.417 | 1/60 ≈ 0.017 | 0 | 4/15 ≈ 0.267 |
| CRRR | 13/30 ≈ 0.433 | -7/60 ≈ -0.117 | 0 | 4/10 = 0.400 |
| RCCR | 49/60 ≈ 0.817 | 5/12 ≈ 0.417 | 1/60 ≈ 0.017 | 0 |
| RCRR | 5/6 ≈ 0.833 | 17/60 ≈ 0.283 | 1/60 ≈ 0.017 | 4/30 ≈ 0.133 |
| RRCR | 37/30 ≈ 1.233 | 3/10 = 0.300 | -1/4 = -0.250 | -4/30 ≈ -0.133 |
| RRRR | 5/4 ≈ 1.250 | 1/6 ≈ 0.167 | -1/4 = -0.250 | 0 |
Excel sheets VNMPoker2.xls, VNMPoker3.xls, and VNMPoker4.xls allow you to create bimatrices like this for different parameters, for S=2,3,4, and to look for domination, maximin moves, and Nash equilibria.
Ann has 2·S information sets in this game: Either she is supposed to make her first move, raise or check, or Ann has checked in her first move, Beth has raised, and Ann is supposed to call or fold. In each case she knows only her own card of value or 1 to S. Beth has also 2·S information sets, determined by her own card from 1 to S and whether Ann has raised (the first S information sets) or checked (the second S information sets).
Therefore Ann has 22·S pure strategies, indicated by S letters "R" or "C" for her choice of raising or checking, given her card from low to high, and then S letters "F" or "C" for folding or calling when she has checked at the beginning and Beth did raise, again given Ann's card from low to high. For instance, for S=2 we get the 16 pure strategies "CCFF", "CCFC", "CCCF", "CCCC", "CRFF", "CRFC", "CRCF", "CRCC", "RCFF", "RCFC", "RCCF", "RCCC", "RRFF", "RRFC", "RRCF", and "RRCC". But if Ann raises with a given card it doesn't matter if she would later check or fold with the same card. For this reason, the reduced strategy with an "R" in position x (1 ≤ x ≤S) would have a "•" in position S+x. In the case S=2 the 9 reduced pure strategies are CCFF, CCFC, CCCF, CCCC, CRF•, CRC•, RC•F, RC•C, and RR••.
Beth has also 22·S pure strategies, since she has 2·S information sets---S where Ann has raised, and S where S has checked---with two options in each. In the case S=2 these are FFCC, FFCR, FFRC, FFRR, FCCC, FCCR, FCRC, FCRR, CFCC, CFCR, CFRC, CFRR, CCCC, CCCR, CCRC, and CCRR. All these strategies are already reduced.
Again some of these (reduced) pure strategies can be eliminated because they are weakly dominated: If Ann holds a highest card, and checked while Beth did raise, it is always better for her to call. When she would fold, she would always lose m units, whereas with calling she cannot lose. Therefore, for S=2, Ann's strategies CCFF, CCCF, and RC•F are weakly dominated. But note that if Ann holds a highest value card, raising does not dominate checking. It all depends on Beth's pure strategy. Assume Beth would always fold when Ann raises, but does always raise when Ann checks. Then, in case Ann holds a highest valued card but Beth not, raising would give Ann a payoff of m units, but checking would give her a higher payoff of n.
If Beth holds a highest valued card, calling weakly dominates folding, and also raising weakly dominates checking.
Let's look into two examples for S=2: KUHN POKER(2,4,2,4) has a Nash equilibrium of CCFC versus FCCR. The increased bet of 4 seems too high, compared with the initial bet of 2, to dare bluffing: Ann and Beth both check with a lower card. Beth also always folds with a lower card, expecting Ann not to bluff. On the other hand, KUHN POKER(2,4,3,4) has the more aggressive Nash equilibrium of RR•• versus CCRR.
|
|
Let us also show an example for S=3:
| . | FFCCCR | FFCCRR | FFCRCR | FFCRRR | FCCCCR | FCCCRR | FCCRCR | FCCRRR | CFCCCR | CFCCRR | CFCRCR | CFCRRR | CCCCCR | CCCCRR | CCCRCR | CCCRRR | CCCFFC | 0.00 | -0.06 | -0.55 | -0.61 | 0.00 | -0.06 | -0.55 | -0.61 | 0.00 | -0.06 | -0.55 | -0.61 | 0.00 | -0.06 | -0.55 | -0.61 | CCCFCC | -0.12 | 0.00 | -0.06 | 0.06 | -0.12 | 0.00 | -0.06 | 0.06 | -0.12 | 0.00 | -0.06 | 0.06 | -0.12 | 0.00 | -0.06 | 0.06 | CCCCFC | -0.12 | -0.30 | -0.48 | -0.67 | -0.12 | -0.30 | -0.48 | -0.67 | -0.12 | -0.30 | -0.48 | -0.67 | -0.12 | -0.30 | -0.48 | -0.67 | CCCCCC | -0.24 | -0.24 | 0.00 | 0.00 | -0.24 | -0.24 | 0.00 | 0.00 | -0.24 | -0.24 | 0.00 | 0.00 | -0.24 | -0.24 | 0.00 | 0.00 | CCRFF• | 0.00 | -0.18 | -0.67 | -0.85 | 0.12 | -0.06 | -0.55 | -0.73 | 0.12 | -0.06 | -0.55 | -0.73 | 0.24 | 0.06 | -0.42 | -0.61 | CCRFC• | -0.12 | -0.12 | -0.18 | -0.18 | 0.00 | 0.00 | -0.06 | -0.06 | 0.00 | 0.00 | -0.06 | -0.06 | 0.12 | 0.12 | 0.06 | 0.06 | CCRCF• | -0.12 | -0.42 | -0.61 | -0.91 | 0.00 | -0.30 | -0.48 | -0.79 | 0.00 | -0.30 | -0.48 | -0.79 | 0.12 | -0.18 | -0.36 | -0.67 | CCRCC• | -0.24 | -0.36 | -0.12 | -0.24 | -0.12 | -0.24 | 0.00 | -0.12 | -0.12 | -0.24 | 0.00 | -0.12 | 0.00 | -0.12 | 0.12 | 0.00 | CRCF•C | 0.06 | 0.18 | 0.00 | 0.12 | -0.12 | 0.00 | -0.18 | -0.06 | 0.18 | 0.30 | 0.12 | 0.24 | 0.00 | 0.12 | -0.06 | 0.06 | CRCC•C | -0.06 | -0.06 | 0.06 | 0.06 | -0.24 | -0.24 | -0.12 | -0.12 | 0.06 | 0.06 | 0.18 | 0.18 | -0.12 | -0.12 | 0.00 | 0.00 | CRRF•• | 0.06 | 0.06 | -0.12 | -0.12 | 0.00 | 0.00 | -0.18 | -0.18 | 0.30 | 0.30 | 0.12 | 0.12 | 0.24 | 0.24 | 0.06 | 0.06 | CRRC•• | -0.06 | -0.18 | -0.06 | -0.18 | -0.12 | -0.24 | -0.12 | -0.24 | 0.18 | 0.06 | 0.18 | 0.06 | 0.12 | 0.00 | 0.12 | 0.00 | RCC•FC | 0.55 | 0.48 | 0.18 | 0.12 | -0.06 | -0.12 | -0.42 | -0.48 | 0.36 | 0.30 | 0.00 | -0.06 | -0.24 | -0.30 | -0.61 | -0.67 | RCC•CC | 0.42 | 0.55 | 0.67 | 0.79 | -0.18 | -0.06 | 0.06 | 0.18 | 0.24 | 0.36 | 0.48 | 0.61 | -0.36 | -0.24 | -0.12 | 0.00 | RCR•F• | 0.55 | 0.36 | 0.06 | -0.12 | 0.06 | -0.12 | -0.42 | -0.61 | 0.48 | 0.30 | 0.00 | -0.18 | 0.00 | -0.18 | -0.48 | -0.67 | RCR•C• | 0.42 | 0.42 | 0.55 | 0.55 | -0.06 | -0.06 | 0.06 | 0.06 | 0.36 | 0.36 | 0.48 | 0.48 | -0.12 | -0.12 | 0.00 | 0.00 | RRC••C | 0.61 | 0.73 | 0.73 | 0.85 | -0.18 | -0.06 | -0.06 | 0.06 | 0.55 | 0.67 | 0.67 | 0.79 | -0.24 | -0.12 | -0.12 | 0.00 | RRR••• | 0.61 | 0.61 | 0.61 | 0.61 | -0.06 | -0.06 | -0.06 | -0.06 | 0.67 | 0.67 | 0.67 | 0.67 | 0.00 | 0.00 | 0.00 | 0.00 |
Six of Ann's strategies in this bimatrix are still weakly dominated, and four of Beth's strategies as well. After eliminating them we arrive at
| . | FFCCCR | FFCCRR | FFCRCR | FFCRRR | FCCCCR | FCCCRR | FCCRCR | FCCRRR | CCCCCR | CCCCRR | CCCRCR | CCCRRR | CCCFFC | 0.00 | -0.06 | -0.55 | -0.61 | 0.00 | -0.06 | -0.55 | -0.61 | 0.00 | -0.06 | -0.55 | -0.61 | CCCFCC | -0.12 | 0.00 | -0.06 | 0.06 | -0.12 | 0.00 | -0.06 | 0.06 | -0.12 | 0.00 | -0.06 | 0.06 | CCRFF• | 0.00 | -0.18 | -0.67 | -0.85 | 0.12 | -0.06 | -0.55 | -0.73 | 0.24 | 0.06 | -0.42 | -0.61 | CCRFC• | -0.12 | -0.12 | -0.18 | -0.18 | 0.00 | 0.00 | -0.06 | -0.06 | 0.12 | 0.12 | 0.06 | 0.06 | CRCF•C | 0.06 | 0.18 | 0.00 | 0.12 | -0.12 | 0.00 | -0.18 | -0.06 | 0.00 | 0.12 | -0.06 | 0.06 | CRRF•• | 0.06 | 0.06 | -0.12 | -0.12 | 0.00 | 0.00 | -0.18 | -0.18 | 0.24 | 0.24 | 0.06 | 0.06 | RCC•FC | 0.55 | 0.48 | 0.18 | 0.12 | -0.06 | -0.12 | -0.42 | -0.48 | -0.24 | -0.30 | -0.61 | -0.67 | RCC•CC | 0.42 | 0.55 | 0.67 | 0.79 | -0.18 | -0.06 | 0.06 | 0.18 | -0.36 | -0.24 | -0.12 | 0.00 | RCR•F• | 0.55 | 0.36 | 0.06 | -0.12 | 0.06 | -0.12 | -0.42 | -0.61 | 0.00 | -0.18 | -0.48 | -0.67 | RCR•C• | 0.42 | 0.42 | 0.55 | 0.55 | -0.06 | -0.06 | 0.06 | 0.06 | -0.12 | -0.12 | 0.00 | 0.00 | RRC••C | 0.61 | 0.73 | 0.73 | 0.85 | -0.18 | -0.06 | -0.06 | 0.06 | -0.24 | -0.12 | -0.12 | 0.00 | RRR••• | 0.61 | 0.61 | 0.61 | 0.61 | -0.06 | -0.06 | -0.06 | -0.06 | 0.00 | 0.00 | 0.00 | 0.00 |
VNM Poker ... [FFG 2007] Ann: R· ... then CF ... then CC ... then R· Beth: FR ... FC ... CC ... CR
Kuhn Poker ... [FFG 2007] considers also a variant of Kuhn Poker played with cards random real numbers between 0 and 1. They also propose other, more complicated "modules", like ...
SIMULTANEOUS VNMPOKER(S,r,m,n): In the simultaneous version both players decide simultaneously whether they want to raise for m or for n. If one of them raises for n and the other for m, the one daring the higher amount (n) wins m from the other one, regardless what the cards show. If both raise the same amount, the one with the higher card wins n respectively m from the other one, again, no win for draws of identical cards.
Both player have four pure strategies: Betting low in both cases ("LL"), Betting low with a card of value "1" and high with a card of value "2" ("LH"), the counterintuitive strategy of raising with a card of value "1" and low with a card of "2" ("HL"), and raising high for both cards ("HH"). Remember that the probability of both having a card of calue "1" is (r-1)/(2(2r-1)), wheras the probability for Ann getting a "1" and Beth getting a "2" is the slightly higher r/(2(2r-1)). Then for each pair of strategies, the four cases of card distributions have to be condsidered, the payoffs noted, and the expected value as sum of probability multiplied by payoff, for all these four cases has to be computed. We get the following payoff matrix:
| LL | LH | HL | HH | |
| LL | 0 | -m(r-1)/(2(2r-1)) | -m(3r-1)/(2(2r-1)) | -m(4r-2)/(2(2r-1)) |
| LH | m(r-1)/(2(2r-1)) | 0 | r(n-m)/(2(2r-1)) | (nr-2mr+m)/(2(2r-1)) |
| HL | m(3r-1)/(2(2r-1)) | r(m-n)/(2(2r-1)) | 0 | (1-r(n+2m))/(2(2r-1)) |
| HH | m(4r-2)/(2(2r-1)) | (-nr+2mr-m)/(2(2r-1)) | (r(n+2m)-1)/(2(2r-1)) | 0 |
Choose m=1, n=3, r=4:
| LL | LH | HL | HH | |
| LL | 0 | -3/14 | -11/14 | -6/14 |
| LH | 3/14 | 0 | 8/14 | 6/14 |
| HL | 11/14 | -8/14 | 0 | (1-r(n+2m))/(2(2r-1)) |
| HH | 6/14 | -6/14 | (r(n+2m)-1)/(2(2r-1)) | 0 |