<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 <h1>Getting started with the computational analysis of games
Step1:  Gambit version 16.0.0 is the current development version.  You can get it from http
Step2:  Inspecting a game
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."
There is a deck consisting of two types of cards
Step3:  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
Step4:  The game offers a "Pythonic" interface.  Most objects in a game can be accessed via iterable collections.
Step5:  All objects have an optional text label, which can be used to retrieve it from the collection
Step6:  In this game, Alice has two information sets
Step7:  The chance or nature player is a special player in the players collection.
Step8:  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.
Step9:  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.
Step10:  In the original version of the game, it was assumed that the Ace and King cards were equally likely to be dealt.
Step11:  Computing Nash equilibria
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.
In the Python interface, solution methods are offered in the gambit.nash module.  Each method also is wrapped as a standalone command-line binary.
Step12:  The result of this method is a list of (mixed) behaviour profiles.  (Future
Step13:  A behaviour profile looks like a nested list.  Entries are of the form profile[player][infoset][action].
Step14:  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.
Step15:  Bob is randomising at his information set, so he must be indifferent between his actions there.  We can check this.
Step16:  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.
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.
Step17:  Construction of the reduced normal form
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!)
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.
Each player has a data member strategies which lists the reduced normal form strategies (s)he has.
Step18:  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!)
Disclaimer
Step19:  Bonus note
Step20:  We can convert our behaviour profile to a corresponding mixed strategy profile.  This is indexable as a nested list with elements [player][strategy].
Step21:  Of course, Alice will receive the same expected payoff from this mixed strategy profile as she would in the original behaviour profile.
Step22:  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.
Step23:  Automating/scripting analysis
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.
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.)
Caveat/Tip
Step24:  As a final experiment, we can also change the payoff structure instead of the probability of the high card.  How would the equilibrium change if a Raise/Meet required putting 2 into the pot instead of 1?
Step25:  The outcomes member of the game lists all of the outcomes.  An outcome can appear at multiple nodes.  Outcomes, like all other objects, can be given text labels for easy reference.
Step26:  Once again, solve the revised game using Lemke's algorithm on the sequence form.
Step27:  The value of the game to Alice is now higher
Step28:  Bob's equilibrium belief about Alice's hand is also different of course, as he now is indifferent between meeting and passing Alice's raise when he thinks the chance she has the Ace is 2/3 (instead of 3/4 before).
Step29:  Serialising the game in other formats
We already saw above some of the formats that can be used to serialise games.  There are a few other standard options.  For example, Gambit also has a format for games in strategic (or normal) form.  You can get the reduced normal form of the extensive game in this format directly
Step30:  Also, we can write the game out in the XML format used by Game Theory Explorer
<ASSISTANT_TASK:>
Python Code:
import gambit
Explanation: <h1>Getting started with the computational analysis of games:</h1>
<h2>Playing "stripped down" poker</h2>
<i>Theodore L. Turocy</i><br/>
<i>University of East Anglia</i>
<br/><br/>
<h3>EC'16 Workshop
24 July 2016</h3>
End of explanation
gambit.__version__
Explanation: Gambit version 16.0.0 is the current development version.  You can get it from http://www.gambit-project.org.
End of explanation
g = gambit.Game.read_game("poker.efg")
Explanation: Inspecting a game
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."
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.
<center>
<img src="kingbob.jpg" width="30%">
</center>
Here is what the game looks like in extensive form (as drawn by Gambit's graphical viewer, which we will touch on separately):
<center>
<img src="poker.png" width="60%">
</center>
End of explanation
g
Explanation: 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.
End of explanation
g.players
Explanation: The game offers a "Pythonic" interface.  Most objects in a game can be accessed via iterable collections.
End of explanation
g.players["Alice"]
Explanation: All objects have an optional text label, which can be used to retrieve it from the collection:
End of explanation
g.players["Alice"].infosets
Explanation: In this game, Alice has two information sets: when she has drawn the Ace, and when she has drawn the King:
End of explanation
g.players.chance
g.players.chance.infosets
Explanation: The chance or nature player is a special player in the players collection.
End of explanation
g.players.chance.infosets[0].actions
Explanation: 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.
End of explanation
deal = g.players.chance.infosets[0]
Explanation: 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.
End of explanation
deal.actions["A"].prob
deal.actions["K"].prob
Explanation: In the original version of the game, it was assumed that the Ace and King cards were equally likely to be dealt.
End of explanation
result = gambit.nash.lcp_solve(g)
Explanation: Computing Nash equilibria
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.
In the Python interface, solution methods are offered in the gambit.nash module.  Each method also is wrapped as a standalone command-line binary.
End of explanation
len(result)
Explanation: 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.)
In this game, there is a unique (Bayes-)Nash equilibrium.
End of explanation
result[0]
result[0][g.players["Alice"]]
result[0][g.players["Bob"]]
Explanation: A behaviour profile looks like a nested list.  Entries are of the form profile[player][infoset][action].
End of explanation
result[0].payoff(g.players["Alice"])
result[0].payoff(g.players["Bob"])
Explanation: 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.
End of explanation
result[0].payoff(g.players["Bob"].infosets[0].actions[0])
result[0].payoff(g.players["Bob"].infosets[0].actions[1])
Explanation: Bob is randomising at his information set, so he must be indifferent between his actions there.  We can check this.
End of explanation
result[0].belief(g.players["Bob"].infosets[0].members[0])
result[0].belief(g.players["Bob"].infosets[0].members[1])
Explanation: 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.
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.
End of explanation
g.players["Alice"].strategies
g.players["Bob"].strategies
Explanation: Construction of the reduced normal form
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!)
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.
Each player has a data member strategies which lists the reduced normal form strategies (s)he has.
End of explanation
import IPython.display; IPython.display.HTML(g.write('html'))
Explanation: 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!)
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).
End of explanation
print g.write('sgame')
Explanation: 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.
End of explanation
msp = result[0].as_strategy()
msp
Explanation: We can convert our behaviour profile to a corresponding mixed strategy profile.  This is indexable as a nested list with elements [player][strategy].
End of explanation
msp.payoff(g.players["Alice"])
Explanation: Of course, Alice will receive the same expected payoff from this mixed strategy profile as she would in the original behaviour profile.
End of explanation
msp.strategy_values(g.players["Alice"])
Explanation: 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.
End of explanation
import pandas
probs = [ gambit.Rational(i, 20) for i in xrange(1, 20) ]
results = [ ]
for prob in probs:
    g.players.chance.infosets[0].actions[0].prob = prob
    g.players.chance.infosets[0].actions[1].prob = 1-prob
    result = gambit.nash.lcp_solve(g)[0]
    results.append({ "prob": prob,
                     "alice_payoff": result.payoff(g.players["Alice"]),
                     "bluff": result[g.players["Alice"].infosets[1].actions[0]],
                     "belief": result.belief(g.players["Bob"].infosets[0].members[1]) })
df = pandas.DataFrame(results)
df
import pylab
%matplotlib inline
pylab.plot(df.prob, df.bluff, '-')
pylab.xlabel("Probability Alice gets ace")
pylab.ylabel("Probability Alice bluffs with king")
pylab.show()
pylab.plot(df.prob, df.alice_payoff, '-')
pylab.xlabel("Probability Alice gets ace")
pylab.ylabel("Alice's equilibrium payoff")
pylab.show()
pylab.plot(df.prob, df.belief, '-')
pylab.xlabel("Probability Alice gets ace")
pylab.ylabel("Bob's equilibrium belief")
pylab.ylim(0,1)
pylab.show()
Explanation: Automating/scripting analysis
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.
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.)
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.
End of explanation
deal.actions[0].prob = gambit.Rational(1,2)
deal.actions[1].prob = gambit.Rational(1,2)
Explanation: As a final experiment, we can also change the payoff structure instead of the probability of the high card.  How would the equilibrium change if a Raise/Meet required putting 2 into the pot instead of 1?
End of explanation
g.outcomes["Alice wins big"]
g.outcomes["Alice wins big"][0] = 3
g.outcomes["Alice wins big"][1] = -3
g.outcomes["Bob wins big"][0] = -3
g.outcomes["Bob wins big"][1] = 3
Explanation: The outcomes member of the game lists all of the outcomes.  An outcome can appear at multiple nodes.  Outcomes, like all other objects, can be given text labels for easy reference.
End of explanation
result = gambit.nash.lcp_solve(g)
len(result)
result[0]
Explanation: Once again, solve the revised game using Lemke's algorithm on the sequence form.
End of explanation
result[0].payoff(g.players["Alice"])
Explanation: The value of the game to Alice is now higher: 1/2 instead of 1/3 with the original payoffs.
End of explanation
result[0].belief(g.players["Bob"].infosets[0].members[0])
Explanation: Bob's equilibrium belief about Alice's hand is also different of course, as he now is indifferent between meeting and passing Alice's raise when he thinks the chance she has the Ace is 2/3 (instead of 3/4 before).
End of explanation
print g.write('nfg')
Explanation: Serialising the game in other formats
We already saw above some of the formats that can be used to serialise games.  There are a few other standard options.  For example, Gambit also has a format for games in strategic (or normal) form.  You can get the reduced normal form of the extensive game in this format directly:
End of explanation
print g.write('gte')
Explanation: Also, we can write the game out in the XML format used by Game Theory Explorer:
End of explanation
<END_TASK>