{"id":1726,"date":"2017-01-01T18:11:49","date_gmt":"2017-01-02T00:11:49","guid":{"rendered":"http:\/\/www.laurentlessard.com\/bookproofs\/?p=1726"},"modified":"2018-02-18T15:02:40","modified_gmt":"2018-02-18T21:02:40","slug":"baby-poker","status":"publish","type":"post","link":"https:\/\/laurentlessard.com\/bookproofs\/baby-poker\/","title":{"rendered":"Baby poker"},"content":{"rendered":"

Another game theory problem from the Riddler<\/a>. This game is a simplified version of poker, but captures some interesting behaviors!<\/p>\n

\nBaby poker is played by two players, each holding a single die in a cup. The game starts with each player anteing \\$1. Then both shake their die, roll it, and look at their own die only. Player A can then either “call,” in which case both dice are shown and the player with the higher number wins the \\$2 on the table, or Player A can “raise,” betting one more dollar. If A raises, then B has the option to either “call” by matching A\u2019s second dollar, after which the higher number wins the \\$4 on the table, or B can “fold,” in which case A wins but B is out only his original \\$1. No other plays are made, and if the dice match, a called pot is split equally.<\/p>\n

What is the optimal strategy for each player? Under those strategies, how much is a game of baby poker worth to Player A? In other words, how much should A pay B beforehand to make it a fair game?\n<\/p><\/blockquote>\n

If you’re interested in the derivation (and maybe learning about some game theory along the way), you can read my full solution here:
\n[Show Solution]<\/a><\/p>\n

\n

Our first task will be to figure out the payout of the game as a function of the players’ strategies. For each possible dice roll, the Player A must decide whether to call ($0$) or raise ($1$). Similarly, Player B must decide whether to call ($0$) or fold ($1$). An example strategy for Player A is:
\n\\[
\np = \\begin{bmatrix} 0 & 0 & 0 & 0 & 1 & 1 \\end{bmatrix}
\n\\]This corresponds to Player A calling if they roll $\\{1,2,3,4\\}$ and raising if they roll $\\{5,6\\}.$ This is an example of a pure strategy<\/a> because it completely determines what the player does as a function of the information available. We can encode each pure strategy as a six-digit binary number. There are $2^6 = 64$ possible pure strategies for each player and we can number them from $0$ to $63$ based on the decimal representation. For example, strategy $44$ corresponds to $101100$ in binary, i.e. strategy $p = \\begin{bmatrix}1 & 0 & 1 & 1 & 0 & 0\\end{bmatrix}$. We can also consider mixed strategies<\/a>, where actions are probabilistic. An example of a mixed strategy for Player A is:
\n\\[
\np = \\begin{bmatrix} 0.3 & 0 & 1 & 1 & 0 & 0 \\end{bmatrix}
\n\\]This strategy is identical to the previous example, except if Player A rolls a $1$, they will raise $30$% of the time and call $70$% of the time. Mixed strategies allows players to play randomly if they so desire! Pure strategies are special cases of mixed strategies in which the probabilities are either $0$ or $1$ (deterministic).<\/p>\n

Let’s call $0 \\le p_i \\le 1$ the strategy of Player A if they roll $i \\in \\{1,\\dots,6\\}.$ Likewise, let’s call $0 \\le q_j \\le 1$ the strategy of Player B if they roll $j \\in \\{1,\\dots,6\\}.$ Define the $6\\times 6$ matrix $E$ as:
\n\\[
\nE_{ij} = \\begin{cases}
\n1 &\\text{if }i > j \\\\
\n0 &\\text{if }i = j \\\\
\n-1 &\\text{if }i < j\n\\end{cases}\n\\]This matrix tells us how much Player A wins if they call with an $i$ and the opponent rolls $j.$ Player A raises with probability $p_i$ and calls with probability $1-p_i.$ Similarly, Player B folds with probability $q_j$ and calls with probability $1-q_j.$ Since each pair $(i,j)$ is equally likely, the expected winnings for Player A are:\n\\[\nW = \\frac{1}{36} \\sum_{i=1}^6 \\sum_{j=1}^6 \\bigl( (1-p_i)E_{ij} + p_i\\left( 2(1-q_j) E_{ij} + q_j \\right) \\bigr)\n\\]The last term looks the way it does because if Player B folds, Player A wins $+1$ with certainty. If Player B calls, then we use the $E_{ij}$ matrix to determine the payoff, but with a factor of 2 because the stakes were doubled.\n\n\n\n

Pure strategy equilibria<\/h3>\n

Define $P_{ab}$ to be the winnings of Player A from the $W$ formula above when players adopt pure strategies $a,b \\in \\{0,1,\\dots,63\\}$ respectively. This yields the $64 \\times 64$ matrix $P$ corresponding to the winnings for all possible combinations of pure strategies. Here is what $P$ looks like:<\/p>\n

\"\"<\/p>\n

Player A is trying to maximize $P_{ab}$ while Player B is trying to minimize it (it’s a zero-sum game<\/a>, so minimizing the winnings of one player is equivalent to maximizing the losses of the other player). Put another way, Player A selects a row of the matrix $P$ (corresponding to a choice among 64 pure strategies), while Player B selects a column (again, corresponding to a choice among pure strategies). The number in the chosen cell determines how much Player A will win. A Nash Equilibrium<\/a> is a cell $P_{ab}$ that satisfies
\n\\[
\nP_{\\bar a b} \\le P_{ab} \\le P_{a \\bar b}\\qquad \\text{for all }\\bar a,\\bar b \\in \\{1,\\dots,64\\}
\n\\]In other words, $P_{ab}$ is the largest element in its column (so Player A has no incentive to pick a different row) and it’s also the smallest element in its row (so Player B has no incentive to pick a different column).<\/p>\n

A natural question is to ask is: is there an optimal pair of pure strategies? This amounts to searching the above $P$ matrix for an element that is simultaneously the largest in its column and smallest in its row. A quick search reveals that no such element exists. In other words, there are no pure equilibria for this game!<\/p>\n

Mixed strategy equilibria<\/h3>\n

Every mixed strategy can be expressed as a convex combination<\/a> of pure strategies. For example:
\n\\[
\n\\begin{bmatrix}1\\\\\\tfrac{1}{3}\\\\0\\\\0\\\\\\tfrac{3}{4}\\\\1\\end{bmatrix} =
\n\\frac{1}{3}\\begin{bmatrix}1\\\\1\\\\0\\\\0\\\\1\\\\1\\end{bmatrix} +
\n\\frac{5}{12}\\begin{bmatrix}1\\\\0\\\\0\\\\0\\\\1\\\\1\\end{bmatrix} +
\n\\frac{1}{4}\\begin{bmatrix}1\\\\0\\\\0\\\\0\\\\0\\\\1\\end{bmatrix}
\n\\]This follows from the fact that each mixed strategies lies in the convex hull<\/a> of all pure strategies. Also, since the winnings $W$ are bilinear in $p$ and $q$, the winnings for a convex combination of strategies is the convex combination of the corresponding winnings.<\/p>\n

Now let $u \\in [0,1]^{64}$ and $v \\in [0,1]^{64}$ be the coefficients of the convex combinations of the pure strategies for Players 1 and 2 respectively. The winnings of Player A can be written compactly as $u^\\textsf{T} P v$. Player A would like to select $u$ in order to maximize this quantity, while Player B would like to select $v$ in order to minimize it. All this is subject to the constraint that $0 \\le u_i \\le 1$ for all $i$ and $u_1 + \\dots + u_{64} = 1$, and similarly for $v$. Note that in the special case where $u$ and $v$ contain a single “1” and the rest is “0”, we recover the case of seeking pure strategies.<\/p>\n

Nash famously proved that every game with finitely many players and actions has a mixed strategy equilibrium. So all that’s left to do is find it! The set of Nash equilibria can be expressed as the optimal set of a linear program<\/a>. In particular, the optimal strategies $u,v$ are solutions to the dual linear programs:
\n\\[
\n\\begin{aligned}
\n\\underset{u,\\mu}{\\max}\\quad& \\mu \\\\
\n\\text{s.t.}\\quad& u\\ge 0,\\quad \\mathbf{1}^\\textsf{T} u = 1 \\\\
\n& P^\\textsf{T} u \\ge \\mu \\mathbf{1}
\n\\end{aligned}
\n\\qquad
\n\\begin{aligned}
\n= \\qquad
\n\\underset{v,t}{\\min}\\quad& t \\\\
\n\\text{s.t.}\\quad& v\\ge 0,\\quad \\mathbf{1}^\\textsf{T} v = 1 \\\\
\n& P v \\le t \\mathbf{1}
\n\\end{aligned}
\n\\]The first program (Player A) has a unique solution, which is the mixture:
\n\\[
\np_\\text{opt} =
\n\\frac{1}{3}\\begin{bmatrix} 0 \\\\ 0 \\\\ 0 \\\\ 0 \\\\ 1 \\\\ 1 \\end{bmatrix} +
\n\\frac{2}{3}\\begin{bmatrix} 1 \\\\ 0 \\\\ 0 \\\\ 0 \\\\ 1 \\\\ 1 \\end{bmatrix} =
\n\\begin{bmatrix} \\tfrac{2}{3} \\\\ 0 \\\\ 0 \\\\ 0 \\\\ 1 \\\\ 1 \\end{bmatrix}
\n\\]The second program (Player B) the solution is not unique, and is rather complicated. As with any linear program, the solution set is a polytope. In this case, the polytope has 15 vertices and lives in a 7-dimensional subspace of $\\mathbb{R}^{64}$ (neat, huh?). Projected back down to $\\mathbb{R}^6$ where $q$ lives, every optimal solution occupies a 3-dimensional subspace. Specifically,
\n\\[
\nq_\\text{opt} \\sim
\n\\begin{bmatrix} 1 \\\\ x \\\\ y \\\\ z \\\\ 0 \\\\ 0 \\end{bmatrix}
\n\\]where $0 \\le x,y \\le 1$ and $0 \\le z \\le \\tfrac{2}{3}$ and $x+y+z =\\tfrac{4}{3}$.<\/p>\n

Each optimal solution has the same optimal value (i.e. the optimal value of $\\mu$ or $t$ in the linear programs for $u$ and $v$). The optimal value is $\\tfrac{5}{54} \\approx 0.0926$. So on average, Player A comes out ahead to the tune of about 9.26 cents when both players are playing optimally.<\/p>\n<\/div>\n

This alternate solution was proposed by a commenter named Chris. Same answer, but a simpler argument!
\n[Show Solution]<\/a><\/p>\n

\n

The solution proceeds much like the previous solution, but this time, we rewrite the cost as a quadratic form in the vectors $p$ and $q$:
\n\\begin{align}
\nW &= \\frac{1}{36} \\sum_{i=1}^6 \\sum_{j=1}^6 \\bigl( (1-p_i)E_{ij} + p_i\\left( 2(1-q_j) E_{ij} + q_j \\right) \\bigr) \\\\
\n&= \\frac{1}{36} \\left( p^\\textsf{T}(E \\mathbf{1}) + p^\\textsf{T}(\\textbf{1}\\textbf{1}^\\textsf{T}-2E)q \\right) \\\\
\n&= p^\\textsf{T} b + p^\\textsf{T} A q
\n\\end{align}where $b = \\tfrac{1}{36}E\\mathbf{1}$, and $A = \\tfrac{1}{36}\\left(\\textbf{1}\\textbf{1}^\\textsf{T}-2E\\right)$, and $\\textbf{1}$ is the vector of all ones. We can now directly<\/em> write linear programs for $p$ and $q$. The first player is trying to maximize $W$ under the assumption that the second player is trying to minimize $W$. In other words, we should solve:
\n\\begin{align}
\n&\\phantom{=}\\underset{\\textbf{0} \\le p \\le \\textbf{1}}{\\max}\\quad\\underset{\\textbf{0} \\le q \\le \\textbf{1}}{\\min}\\quad p^\\textsf{T} b + p^\\textsf{T} A q\\\\
\n&= \\underset{\\textbf{0} \\le p \\le \\textbf{1}}{\\max} \\left( p^\\textsf{T} b + \\sum_{j=1}^6 \\underset{0\\le q_j \\le 1}{\\min} q_j (A^\\textsf{T}p)_j \\right) \\\\
\n&= \\underset{\\textbf{0} \\le p \\le \\textbf{1}}{\\max} \\left( p^\\textsf{T} b + \\sum_{j=1}^6 \\min\\left( 0, (A^\\textsf{T}p)_j \\right) \\right) \\\\
\n&= \\left\\{\\begin{aligned}
\n\\underset{p,t}{\\text{maximize}}&\\quad p^\\textsf{T} b + t^\\textsf{T} \\textbf{1} \\\\
\n\\text{subject to:}&\\quad \\textbf{0} \\le p \\le \\textbf{1} \\\\
\n& t \\le \\textbf{0},\\quad t \\le A^\\textsf{T} p
\n\\end{aligned}\\right.
\n\\end{align}Likewise, the second player is trying to minimize $W$ under the assumption that the first player is trying to maximize $W$. We can proceed in a similar manner to above and we obtain:
\n\\begin{align}
\n&\\phantom{=}\\underset{\\textbf{0} \\le q \\le \\textbf{1}}{\\min}\\quad\\underset{\\textbf{0} \\le p \\le \\textbf{1}}{\\max}\\quad p^\\textsf{T} b + p^\\textsf{T} A q\\\\
\n&= \\underset{\\textbf{0} \\le q \\le \\textbf{1}}{\\min} \\left( \\sum_{i=1}^6 \\max_{0\\le p_i \\le 1} p_i(Aq+b)_i \\right) \\\\
\n&= \\underset{\\textbf{0} \\le q \\le \\textbf{1}}{\\min} \\left( \\sum_{i=1}^6 \\max\\left( 0, (Aq+b)_i \\right) \\right) \\\\
\n&= \\left\\{\\begin{aligned}
\n\\underset{q,\\mu}{\\text{minimize}}&\\quad \\mu^\\textsf{T} \\textbf{1} \\\\
\n\\text{subject to:}&\\quad \\textbf{0} \\le q \\le \\textbf{1} \\\\
\n& \\mu \\ge \\textbf{0},\\quad \\mu \\ge A q + b
\n\\end{aligned}\\right.
\n\\end{align}Solving these two linear programs yields the same optimal $p$ and $q$ vectors as in the previous approach, but this time our linear programs have far fewer variables! The objective values of both LPs match as well and are both equal to $\\tfrac{5}{54} \\approx 0.926$, as before. In fact, we can check algebraically that the two LPs are dual to one another<\/a>. Since both are clearly feasible (easy to check that the feasible set is compact and nonempty), strong duality holds and the two LPs must have the same optimal value<\/em>. This is in essence Nash’s celebrated result; that the minimax and maximin formulations are equivalent!<\/p>\n<\/div>\n

If you’d just like to know the answer along with a brief explanation, here is the tl;dr version:
\n[Show Solution]<\/a><\/p>\n

\n

Player A’s optimal strategy:<\/strong><\/p>\n