{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Getting started with the computational analysis of games:
\n",
"Playing \"stripped down\" poker
\n",
"Theodore L. Turocy
\n",
"University of East Anglia\n",
"
\n",
"EC'16 Workshop\n",
"24 July 2016
"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"import gambit"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Gambit version 16.0.0 is the current development version. You can get it from http://www.gambit-project.org."
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"'16.0.0'"
]
},
"execution_count": 2,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"gambit.__version__"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Inspecting a game"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The game that we will use as our starting point is one which many of you may have encountered in some variation. Myerson's (1991) textbook refers to this as a one-card poker game; Reiley et at (2008) call this \"stripped-down poker.\"\n",
"\n",
"There is a deck consisting of two types of cards: Ace and King. There are two players, Alice and Bob. Both start by putting 1 in the pot. One player (Alice) draws a card; initially assume the cards are in equal proportion in the deck. Alice sees her card, and then decides whether she wants to raise (add another 1 to the pot) or fold (and concede the pot to Bob). If she raises, play passes to Bob, who much decide whether to meet her raise (and add another 1 to the pot) or pass (and concede the pot to Alice). If Alice raises and Bob meets, Alice reveals her card: If it is an Ace, she takes the pot, whereas if it is a King, Bob does.\n",
"\n",
"\n",
"![](\"kingbob.jpg\")
\n",
""
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Here is what the game looks like in extensive form (as drawn by Gambit's graphical viewer, which we will touch on separately):\n",
"\n",
"![](\"poker.png\")
\n",
""
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"g = gambit.Game.read_game(\"poker.efg\")"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Gambit's .efg format is a serialisation of an extensive game. The format looks somewhat dated (and indeed it was finalised in 1994), but is fast: recently I loaded a game with about 1M nodes in under 2s."
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"EFG 2 R \"A simple poker example\" { \"Alice\" \"Bob\" }\n",
"\"\"\n",
"\n",
"c \"\" 1 \"\" { \"A\" 1/2 \"K\" 1/2 } 0\n",
"p \"\" 1 1 \"a\" { \"R\" \"F\" } 0\n",
"p \"\" 2 1 \"b\" { \"M\" \"P\" } 0\n",
"t \"\" 1 \"Alice wins big\" { 2, -2 }\n",
"t \"\" 2 \"Alice wins\" { 1, -1 }\n",
"t \"\" 3 \"Bob wins\" { -1, 1 }\n",
"p \"\" 1 2 \"k\" { \"R\" \"F\" } 0\n",
"p \"\" 2 1 \"b\" { \"M\" \"P\" } 0\n",
"t \"\" 4 \"Bob wins big\" { -2, 2 }\n",
"t \"\" 2 \"Alice wins\" { 1, -1 }\n",
"t \"\" 3 \"Bob wins\" { -1, 1 }"
]
},
"execution_count": 4,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"g"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The game offers a \"Pythonic\" interface. Most objects in a game can be accessed via iterable collections."
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"[, ]"
]
},
"execution_count": 5,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"g.players"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"All objects have an optional text label, which can be used to retrieve it from the collection:"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
""
]
},
"execution_count": 6,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"g.players[\"Alice\"]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"In this game, Alice has two information sets: when she has drawn the Ace, and when she has drawn the King:"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"[, ]"
]
},
"execution_count": 7,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"g.players[\"Alice\"].infosets"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The chance or nature player is a special player in the `players` collection."
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
""
]
},
"execution_count": 8,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"g.players.chance"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"[]"
]
},
"execution_count": 9,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"g.players.chance.infosets"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Gambit does sorting of the objects in each collection, so indexing collections by integer indices also works reliably if you save and load a game again."
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"[, ]"
]
},
"execution_count": 10,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"g.players.chance.infosets[0].actions"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We can assign particular game objects to variables for convenient referencing. In this case, we will explore the strategic effects of changing the relative probabilities of the Ace and King cards."
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"deal = g.players.chance.infosets[0]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"In the original version of the game, it was assumed that the Ace and King cards were equally likely to be dealt."
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/latex": [
"$\\frac{1}{2}$"
],
"text/plain": [
"Fraction(1, 2)"
]
},
"execution_count": 12,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"deal.actions[\"A\"].prob"
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/latex": [
"$\\frac{1}{2}$"
],
"text/plain": [
"Fraction(1, 2)"
]
},
"execution_count": 13,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"deal.actions[\"K\"].prob"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Computing Nash equilibria\n",
"\n",
"Gambit offers a variety of methods for computing Nash equilibria of games, which we will discuss in more detail separately. This is a two-player game in extensive form, for which we can use Lemke's algorithm applied to the *sequence form* of the game.\n",
"\n",
"In the Python interface, solution methods are offered in the `gambit.nash` module. Each method also is wrapped as a standalone command-line binary."
]
},
{
"cell_type": "code",
"execution_count": 14,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"result = gambit.nash.lcp_solve(g)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The result of this method is a list of (mixed) *behaviour profiles*. (Future: the return value will be encapsulated in a results class retaining more detailed metadata about the run of the algorithm.)\n",
"\n",
"In this game, there is a unique (Bayes-)Nash equilibrium."
]
},
{
"cell_type": "code",
"execution_count": 15,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"1"
]
},
"execution_count": 15,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"len(result)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"A behaviour profile looks like a nested list. Entries are of the form `profile[player][infoset][action]`."
]
},
{
"cell_type": "code",
"execution_count": 16,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/latex": [
"$\\left[\\left[\\left[1,0\\right],\\left[\\frac{1}{3},\\frac{2}{3}\\right]\\right],\\left[\\left[\\frac{2}{3},\\frac{1}{3}\\right]\\right]\\right]$"
],
"text/plain": [
"[[[Fraction(1, 1), Fraction(0, 1)], [Fraction(1, 3), Fraction(2, 3)]], [[Fraction(2, 3), Fraction(1, 3)]]]"
]
},
"execution_count": 16,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"result[0]"
]
},
{
"cell_type": "code",
"execution_count": 17,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/latex": [
"$\\left[\\left[1,0\\right],\\left[\\frac{1}{3},\\frac{2}{3}\\right]\\right]$"
],
"text/plain": [
"[[Fraction(1, 1), Fraction(0, 1)], [Fraction(1, 3), Fraction(2, 3)]]"
]
},
"execution_count": 17,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"result[0][g.players[\"Alice\"]]"
]
},
{
"cell_type": "code",
"execution_count": 18,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/latex": [
"$\\left[\\left[\\frac{2}{3},\\frac{1}{3}\\right]\\right]$"
],
"text/plain": [
"[[Fraction(2, 3), Fraction(1, 3)]]"
]
},
"execution_count": 18,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"result[0][g.players[\"Bob\"]]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We can compute various interesting quantities about behaviour profiles. Most interesting is perhaps the payoff to each player; because this is a constant-sum game, this is the value of the game."
]
},
{
"cell_type": "code",
"execution_count": 19,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/latex": [
"$\\frac{1}{3}$"
],
"text/plain": [
"Fraction(1, 3)"
]
},
"execution_count": 19,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"result[0].payoff(g.players[\"Alice\"])"
]
},
{
"cell_type": "code",
"execution_count": 20,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/latex": [
"$\\frac{-1}{3}$"
],
"text/plain": [
"Fraction(-1, 3)"
]
},
"execution_count": 20,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"result[0].payoff(g.players[\"Bob\"])"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Bob is randomising at his information set, so he must be indifferent between his actions there. We can check this."
]
},
{
"cell_type": "code",
"execution_count": 21,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/latex": [
"$-1$"
],
"text/plain": [
"Fraction(-1, 1)"
]
},
"execution_count": 21,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"result[0].payoff(g.players[\"Bob\"].infosets[0].actions[0])"
]
},
{
"cell_type": "code",
"execution_count": 22,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/latex": [
"$-1$"
],
"text/plain": [
"Fraction(-1, 1)"
]
},
"execution_count": 22,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"result[0].payoff(g.players[\"Bob\"].infosets[0].actions[1])"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"As we teach our students, the key to understanding this game is that Alice plays so as to manipulate Bob's beliefs about the likelihood she has the Ace. We can examine Bob's beliefs over the nodes (members) of his one information set.\n",
"\n",
"Given the structure of the betting rules, Bob becomes indifferent to his actions when he thinks there is a 3/4 chance Alice has the Ace."
]
},
{
"cell_type": "code",
"execution_count": 23,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/latex": [
"$\\frac{3}{4}$"
],
"text/plain": [
"Fraction(3, 4)"
]
},
"execution_count": 23,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"result[0].belief(g.players[\"Bob\"].infosets[0].members[0])"
]
},
{
"cell_type": "code",
"execution_count": 24,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/latex": [
"$\\frac{1}{4}$"
],
"text/plain": [
"Fraction(1, 4)"
]
},
"execution_count": 24,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"result[0].belief(g.players[\"Bob\"].infosets[0].members[1])"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Construction of the reduced normal form\n",
"\n",
"The call to `lcp_solve` above uses the sequence form rather than the (reduced) strategic form of the game. This representation takes advantage of the tree structure, and can avoid (in many games of interest) the exponential blowup of the size of the strategic form relative to the extensive form. (More details on this in a while!)\n",
"\n",
"Nevertheless, the reduced strategic form of a game can be of interest. Gambit implements transparently the conversions between the extensive and strategic representations. For games in extensive form, the reduced strategic form is computed on-the-fly from the game tree; that is, the full normal form payoff tables are not stored in memory.\n",
"\n",
"Each player has a data member `strategies` which lists the reduced normal form strategies (s)he has."
]
},
{
"cell_type": "code",
"execution_count": 25,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"[, , , ]"
]
},
"execution_count": 25,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"g.players[\"Alice\"].strategies"
]
},
{
"cell_type": "code",
"execution_count": 26,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"[, ]"
]
},
"execution_count": 26,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"g.players[\"Bob\"].strategies"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We can also do a quick visualisation of the payoff matrix of the game using the built-in HTML output (plus Jupyter's inline rendering of HTML!)\n",
"\n",
"**Disclaimer**: There's a bug in the 16.0.0 release which prevents the correct generation of HTML; this will be corrected in 16.0.1 (and is corrected in the 'master' branch of the git repository already)."
]
},
{
"cell_type": "code",
"execution_count": 27,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/html": [
"A simple poker example
\n",
" | 1 | 2 |
| 11 | 0,0 | 1,-1 |
| 12 | 1/2,-1/2 | 0,0 |
| 21 | -3/2,3/2 | 0,0 |
| 22 | -1,1 | -1,1 |
\n"
],
"text/plain": [
""
]
},
"execution_count": 27,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"import IPython.display; IPython.display.HTML(g.write('html'))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Bonus note**: Gambit also supports writing out games using Martin Osborne's sgame LaTeX style: https://www.economics.utoronto.ca/osborne/latex/. This doesn't have auto-rendering magic in Jupyter, but it's all ready to cut-and-paste to your favourite editor."
]
},
{
"cell_type": "code",
"execution_count": 28,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"\\begin{game}{4}{2}[Alice][Bob]\n",
"&1 & 2\\\\\n",
"11 & $0,0$ & $1,-1$ \\\\\n",
"12 & $1/2,-1/2$ & $0,0$ \\\\\n",
"21 & $-3/2,3/2$ & $0,0$ \\\\\n",
"22 & $-1,1$ & $-1,1$ \n",
"\\end{game}\n",
"\n"
]
}
],
"source": [
"print g.write('sgame')"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We can convert our behaviour profile to a corresponding mixed strategy profile. This is indexable as a nested list with elements `[player][strategy]`."
]
},
{
"cell_type": "code",
"execution_count": 29,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/latex": [
"$\\left[\\left[\\frac{1}{3},\\frac{2}{3},0,0\\right],\\left[\\frac{2}{3},\\frac{1}{3}\\right]\\right]$"
],
"text/plain": [
"[[Fraction(1, 3), Fraction(2, 3), Fraction(0, 1), Fraction(0, 1)], [Fraction(2, 3), Fraction(1, 3)]]"
]
},
"execution_count": 29,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"msp = result[0].as_strategy()\n",
"msp"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Of course, Alice will receive the same expected payoff from this mixed strategy profile as she would in the original behaviour profile."
]
},
{
"cell_type": "code",
"execution_count": 30,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/latex": [
"$\\frac{1}{3}$"
],
"text/plain": [
"Fraction(1, 3)"
]
},
"execution_count": 30,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"msp.payoff(g.players[\"Alice\"])"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We can also ask what the expected payoffs to each of the strategies are. Alice's last two strategies correspond to folding when she has the Ace, which is dominated."
]
},
{
"cell_type": "code",
"execution_count": 31,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"[Fraction(1, 3), Fraction(1, 3), Fraction(-1, 1), Fraction(-1, 1)]"
]
},
"execution_count": 31,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"msp.strategy_values(g.players[\"Alice\"])"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Automating/scripting analysis\n",
"\n",
"The real gain in having libraries for doing computation in game theory is to be able to script computations. For example, we can explore how the solution to the game changes, as we change the probability that Alice is dealt the Ace.\n",
"\n",
"Payoffs and probabilities are represented in games in Gambit as exact-precision numbers, which can be either rational numbers of (exact-precision) decimals. These are called `gambit.Rational` and `gambit.Decimal`, and are compatible with the Python `fractions.Fraction` and `decimal.Decimal` classes, respectively. (In Gambit 16.0.0, they are derived from them.)\n",
"\n",
"**Caveat/Tip**: This means one cannot set a payoff or probability to be a floating-point number. We justify this based on the principle \"explicit is better than implicit.\" In two-player games, the extreme points of the set of Nash equilibria are rational numbers, whenever the data of the game are rational, and the Gambit equilibrium computation methods take advantage of this. If the payoff of a game were specified as a floating-point number, e.g. 0.333333 instead of 1/3, surprising results can occur due to rounding. "
]
},
{
"cell_type": "code",
"execution_count": 32,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/html": [
"\n",
"
\n",
" \n",
" \n",
" | \n",
" alice_payoff | \n",
" belief | \n",
" bluff | \n",
" prob | \n",
"
\n",
" \n",
" \n",
" \n",
" | 0 | \n",
" -13/15 | \n",
" 1/4 | \n",
" 1/57 | \n",
" 1/20 | \n",
"
\n",
" \n",
" | 1 | \n",
" -11/15 | \n",
" 1/4 | \n",
" 1/27 | \n",
" 1/10 | \n",
"
\n",
" \n",
" | 2 | \n",
" -3/5 | \n",
" 1/4 | \n",
" 1/17 | \n",
" 3/20 | \n",
"
\n",
" \n",
" | 3 | \n",
" -7/15 | \n",
" 1/4 | \n",
" 1/12 | \n",
" 1/5 | \n",
"
\n",
" \n",
" | 4 | \n",
" -1/3 | \n",
" 1/4 | \n",
" 1/9 | \n",
" 1/4 | \n",
"
\n",
" \n",
" | 5 | \n",
" -1/5 | \n",
" 1/4 | \n",
" 1/7 | \n",
" 3/10 | \n",
"
\n",
" \n",
" | 6 | \n",
" -1/15 | \n",
" 1/4 | \n",
" 7/39 | \n",
" 7/20 | \n",
"
\n",
" \n",
" | 7 | \n",
" 1/15 | \n",
" 1/4 | \n",
" 2/9 | \n",
" 2/5 | \n",
"
\n",
" \n",
" | 8 | \n",
" 1/5 | \n",
" 1/4 | \n",
" 3/11 | \n",
" 9/20 | \n",
"
\n",
" \n",
" | 9 | \n",
" 1/3 | \n",
" 1/4 | \n",
" 1/3 | \n",
" 1/2 | \n",
"
\n",
" \n",
" | 10 | \n",
" 7/15 | \n",
" 1/4 | \n",
" 11/27 | \n",
" 11/20 | \n",
"
\n",
" \n",
" | 11 | \n",
" 3/5 | \n",
" 1/4 | \n",
" 1/2 | \n",
" 3/5 | \n",
"
\n",
" \n",
" | 12 | \n",
" 11/15 | \n",
" 1/4 | \n",
" 13/21 | \n",
" 13/20 | \n",
"
\n",
" \n",
" | 13 | \n",
" 13/15 | \n",
" 1/4 | \n",
" 7/9 | \n",
" 7/10 | \n",
"
\n",
" \n",
" | 14 | \n",
" 1 | \n",
" 1/4 | \n",
" 1 | \n",
" 3/4 | \n",
"
\n",
" \n",
" | 15 | \n",
" 1 | \n",
" 1/5 | \n",
" 1 | \n",
" 4/5 | \n",
"
\n",
" \n",
" | 16 | \n",
" 1 | \n",
" 3/20 | \n",
" 1 | \n",
" 17/20 | \n",
"
\n",
" \n",
" | 17 | \n",
" 1 | \n",
" 1/10 | \n",
" 1 | \n",
" 9/10 | \n",
"
\n",
" \n",
" | 18 | \n",
" 1 | \n",
" 1/20 | \n",
" 1 | \n",
" 19/20 | \n",
"
\n",
" \n",
"
\n",
"