<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>Finding all equilibria of a two-player game
Step1:  Bagwell (1993) pointed out that the usual story of Stackelberg commitment to an action depends critically on the observability of the commitment to the action.  If there is any chance that the action might be misinterpreted, then the only equilibrium in pure strategies is the equilibrium of the simultaneous-move game.  He noted however that if the chance of misinterpreting the action is sufficiently small, then there is an equilibrium in mixed strategies in which the player chooses the Stackelberg action with probability arbitarily close to one.
We'll explore this example numerically, and use it as a vehicle for showing how to compute all equilibria of a two-player game.
We'll start with a quick overview of the "base" simultaneous-move game used by Bagwell in his example.  First we'll create the payoff matrix for the "leader" player
Step2:  And the payoff matrix for the "follower" player
Step3:  The constructor Game.from_arrays creates a game in normal form from a collection of payoff matrices, one per player.
Step4:  Here, we have set up the row player as the would-be "Leader" player (the one who would have an incentive to commit).  The strategy "S" (for both players) would be the subgame-perfect outcome if the row player had the opportunity to commit, where as we can see that "C" is going to be the unique equilibrium (obtainable by iterative elimination of strictly dominated strategies!) if players choose simultaneously.
Aside
Step5:  The function StrategySupportProfile.undominated() determines which strategies are (strictly) dominated (taking into account only those in the SupportProfile), and returns a new StrategySupportProfile containing only the undominated ones.
As we expect here, strategy S is dominated for the Leader player, so it does not appear in the returned support profile.
Step6:  Iterating on this allows you to implement iterative elimination of strictly dominated strategies, to whatever depth you would like.
Step7:  Of course after two rounds, we run out of things to eliminate!
Step8:  The other useful concept is the StrategicRestriction.  A StrategicRestriction is a full-fledged game in its own right, derived from another game by using only a subset of its strategies.  StrategySupportProfile objects have a .restrict() member that returns a restricted game.
Step9:  A StrategicRestriction remembers its "parent" or "unrestricted" game.  So while a StrategicRestriction is itself a game that can be manipulated in its own right, it is also possible to map e.g. mixed strategy profiles defined on a restriction of a game, to a mixed strategy profile on the corresponding unrestricted game.
Step10:  The game with imperfectly-observed commitment
Back to the main thrust of this example.  We now want to allow the Leader player to move first.  The Follower player, however, will observe the Leader's choice only with noise.  If Leader chooses S, then Follower will see a signal s with some probability $p$, and a signal c otherwise.  Similarly, if Leader chooses C, then follower will see a signal c with the same probability $p$, and a signal s otherwise.  If $p=1$ then we have the standard case of perfectly-observed Stackelberg-style commitment.
We've prepared in advance an extensive game file with $p=\frac{99}{100}$.  Here is the extensive game in pictures.
<center>
<img src="bagwell.jpg" width="70%">
</center>
Step11:  For this example, we want to be sure we compute all equilibria.  The lcp_solve method we used in the poker example computes "most" equilibria.  For many games, it actually finds all of them, but there do exist games for which it will miss some out.  Fortunately, for two-player games, there is an enumeration method which is guaranteed to find all of them.  This is implemented as gambit.nash.enummixed_solve().
From Gambit 16, this method (optionally) uses lrs by David Avis
Step12:  So, we have multiple equilibria.  Let's inspect them.  This method actually returns mixed strategies on the strategic game (a version that uses the sequence form to do enumeration directly on the extensive game is forthcoming!)
Step13:  We can view the behaviour equivalent using .as_behavior(), which does the Kuhn's Theorem calculation for us.  The first equilibrium is in pure strategies, and corresponds to the simultaneous-move outcome
Step14:  The second equilibrium is a low-commitment equilibrium
Step15:  And the third equilibrium is a high-commitment equilibrium
Step16:  We can then make a plot, in which we vary the probability the signal "correctly" transmits Leader's action, and ask what are the probabilities the leader plays $S$ as a function (technically, correspondance) of that accuracy.
Step17:  That's an interesting enough graph.  It shows there is a "high-commitment" equilibrium as long as $p\geq \frac{3}{4}$, or $p\leq \frac{1}{4}$.  However, game theorists will be surprised to see the two branches of the graph are not connected.  After all, we are essentially perturbing the payoffs of the game continuously as we move along the horizontal axis.
Let's have a closer look at the game when $p=\frac{3}{4}$.
Step18:  We have three equilibria listed, but note that the second and third both involve the Follower (column) player choosing the same pure strategy (which is to respond to s with S and c with C).  In the game, there is a degeneracy
Step19:  First, we'll run the gambit-enummixed tool on the game, and we'll see we get the same equilibria out.  The equilibria are written out in CSV for convenient parsing.
Step20:  The -h switch to any command-line tool gives a standard brief help synopsis.
Step21:  The option -c (output connectnedness information) is the one we want; it'll tell us how the three extreme equilibria listed are structured.
<ASSISTANT_TASK:>
Python Code:
import gambit
Explanation: <h1>Finding all equilibria of a two-player game: Bagwell's commitment example</h1>
<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
import numpy
L = numpy.array([[5,3], [6,4]])
L
Explanation: Bagwell (1993) pointed out that the usual story of Stackelberg commitment to an action depends critically on the observability of the commitment to the action.  If there is any chance that the action might be misinterpreted, then the only equilibrium in pure strategies is the equilibrium of the simultaneous-move game.  He noted however that if the chance of misinterpreting the action is sufficiently small, then there is an equilibrium in mixed strategies in which the player chooses the Stackelberg action with probability arbitarily close to one.
We'll explore this example numerically, and use it as a vehicle for showing how to compute all equilibria of a two-player game.
We'll start with a quick overview of the "base" simultaneous-move game used by Bagwell in his example.  First we'll create the payoff matrix for the "leader" player:
End of explanation
F = numpy.array([[2,1], [3,4]])
F
Explanation: And the payoff matrix for the "follower" player:
End of explanation
g = gambit.Game.from_arrays(L, F)
g.players[0].label = "Leader"
g.players[0].strategies[0].label = "S"
g.players[0].strategies[1].label = "C"
g.players[1].label = "Follower"
g.players[1].strategies[0].label = "S"
g.players[1].strategies[1].label = "C"
import IPython.display; IPython.display.HTML(g.write('html'))
Explanation: The constructor Game.from_arrays creates a game in normal form from a collection of payoff matrices, one per player.
End of explanation
sp = g.support_profile()
sp
Explanation: Here, we have set up the row player as the would-be "Leader" player (the one who would have an incentive to commit).  The strategy "S" (for both players) would be the subgame-perfect outcome if the row player had the opportunity to commit, where as we can see that "C" is going to be the unique equilibrium (obtainable by iterative elimination of strictly dominated strategies!) if players choose simultaneously.
Aside: dominated strategies and restrictions of a game
Did someone say something about dominated strategies?  Gambit 16 contains new features for manipulating dominance information.  (These do not yet appear in the documentation for 16.0.0.)
The first concept to introduce is the StrategySupportProfile.  (This is a name we believe we have coined, because we cannot think of a standard termfor it.  If you know of one, please suggest!)  A support profile is a subset of strategies of a game, subject to the requirement that each player must have at least one strategy in the profile.
The function Game.support_profile() returns a support profile, initialized to include all strategies in the game.
End of explanation
sp.undominated()
Explanation: The function StrategySupportProfile.undominated() determines which strategies are (strictly) dominated (taking into account only those in the SupportProfile), and returns a new StrategySupportProfile containing only the undominated ones.
As we expect here, strategy S is dominated for the Leader player, so it does not appear in the returned support profile.
End of explanation
sp.undominated().undominated()
Explanation: Iterating on this allows you to implement iterative elimination of strictly dominated strategies, to whatever depth you would like.
End of explanation
sp.undominated().undominated().undominated() == sp.undominated().undominated()
Explanation: Of course after two rounds, we run out of things to eliminate!
End of explanation
rest = sp.undominated().undominated().restrict()
rest
Explanation: The other useful concept is the StrategicRestriction.  A StrategicRestriction is a full-fledged game in its own right, derived from another game by using only a subset of its strategies.  StrategySupportProfile objects have a .restrict() member that returns a restricted game.
End of explanation
rest.unrestrict()
rest.unrestrict() == g
Explanation: A StrategicRestriction remembers its "parent" or "unrestricted" game.  So while a StrategicRestriction is itself a game that can be manipulated in its own right, it is also possible to map e.g. mixed strategy profiles defined on a restriction of a game, to a mixed strategy profile on the corresponding unrestricted game.
End of explanation
g = gambit.Game.read_game("bagwell.efg")
g
Explanation: The game with imperfectly-observed commitment
Back to the main thrust of this example.  We now want to allow the Leader player to move first.  The Follower player, however, will observe the Leader's choice only with noise.  If Leader chooses S, then Follower will see a signal s with some probability $p$, and a signal c otherwise.  Similarly, if Leader chooses C, then follower will see a signal c with the same probability $p$, and a signal s otherwise.  If $p=1$ then we have the standard case of perfectly-observed Stackelberg-style commitment.
We've prepared in advance an extensive game file with $p=\frac{99}{100}$.  Here is the extensive game in pictures.
<center>
<img src="bagwell.jpg" width="70%">
</center>
End of explanation
result = gambit.nash.enummixed_solve(g, use_lrs=True)
len(result)
Explanation: For this example, we want to be sure we compute all equilibria.  The lcp_solve method we used in the poker example computes "most" equilibria.  For many games, it actually finds all of them, but there do exist games for which it will miss some out.  Fortunately, for two-player games, there is an enumeration method which is guaranteed to find all of them.  This is implemented as gambit.nash.enummixed_solve().
From Gambit 16, this method (optionally) uses lrs by David Avis: http://cgm.cs.mcgill.ca/~avis/C/lrs.html, which is an excellent package (and much faster than the Gambit version written originally in the mid-1990s!).  We'll use it for this example (although for games of this size there's no meaningful speed differential.)
End of explanation
result[0]
Explanation: So, we have multiple equilibria.  Let's inspect them.  This method actually returns mixed strategies on the strategic game (a version that uses the sequence form to do enumeration directly on the extensive game is forthcoming!):
End of explanation
result[0].as_behavior()
Explanation: We can view the behaviour equivalent using .as_behavior(), which does the Kuhn's Theorem calculation for us.  The first equilibrium is in pure strategies, and corresponds to the simultaneous-move outcome:
End of explanation
result[1].as_behavior()
Explanation: The second equilibrium is a low-commitment equilibrium: the probability of choosing the Stackelberg action $S$ is small:
End of explanation
result[2].as_behavior()
Explanation: And the third equilibrium is a high-commitment equilibrium: the probability of choosing the Stackelberg action $S$ is large.  So while it is indeed true that there is no pure-strategy equilibrium with full commitment, there is a mixed-strategy equilibrium with a high probability of commitment.
End of explanation
probs = [ gambit.Rational(i, 100) for i in xrange(99, 0, -1) ]
eqa = [ ]
for prob in probs:
    g.players.chance.infosets[0].actions[0].prob = prob
    g.players.chance.infosets[0].actions[1].prob = 1-prob
    g.players.chance.infosets[1].actions[0].prob = 1-prob
    g.players.chance.infosets[1].actions[1].prob = prob
    eqa.append([ eqm.as_behavior()[g.players[0].infosets[0].actions[0]] 
                 for eqm in gambit.nash.enummixed_solve(g, use_lrs=True) ])
    
import pylab
%matplotlib inline
for (prob, solns) in zip(probs, eqa):
    pylab.plot([ prob for eqm in solns ], solns, 'ro')
pylab.xlabel("Probability signal is accurate")
pylab.ylabel("Equilibrium probability of choosing $S$")
pylab.show()
Explanation: We can then make a plot, in which we vary the probability the signal "correctly" transmits Leader's action, and ask what are the probabilities the leader plays $S$ as a function (technically, correspondance) of that accuracy.
End of explanation
g.players.chance.infosets[0].actions[0].prob = gambit.Rational(3,4)
g.players.chance.infosets[0].actions[1].prob = gambit.Rational(1,4)
g.players.chance.infosets[1].actions[0].prob = gambit.Rational(1,4)
g.players.chance.infosets[1].actions[1].prob = gambit.Rational(3,4)
IPython.display.HTML(g.write('html'))
result = gambit.nash.enummixed_solve(g)
len(result)
result[0]
result[1]
result[2]
Explanation: That's an interesting enough graph.  It shows there is a "high-commitment" equilibrium as long as $p\geq \frac{3}{4}$, or $p\leq \frac{1}{4}$.  However, game theorists will be surprised to see the two branches of the graph are not connected.  After all, we are essentially perturbing the payoffs of the game continuously as we move along the horizontal axis.
Let's have a closer look at the game when $p=\frac{3}{4}$.
End of explanation
with file("bagwell-75.nfg", "w") as f:
    f.write(g.write('nfg'))
Explanation: We have three equilibria listed, but note that the second and third both involve the Follower (column) player choosing the same pure strategy (which is to respond to s with S and c with C).  In the game, there is a degeneracy: Leader is indifferent between S and C when Follower chooses this strategy.  You should be able to convince yourself that any probability distribution over S and C for Leader, with probabilities between $\frac{1}{4}$ and $\frac{3}{4}$ (on S) forms an equilibrium.
The enumeration method in gambit.nash.enummixed_solve enumerates extreme points of the equilibrium set. In a two-player game, the set of equilibria can be expressed as a union of convex sets.  There is support in Gambit for computing these convex sets - but it is not yet exposed directly via Python.
What we will do instead is to write this game out to disk, and then use the Gambit command-line tools (via Jupyter's shell magic) to inspect the output.
End of explanation
!gambit-enummixed bagwell-75.nfg
Explanation: First, we'll run the gambit-enummixed tool on the game, and we'll see we get the same equilibria out.  The equilibria are written out in CSV for convenient parsing.
End of explanation
!gambit-enummixed -h
Explanation: The -h switch to any command-line tool gives a standard brief help synopsis.
End of explanation
!gambit-enummixed -c bagwell-75.nfg
Explanation: The option -c (output connectnedness information) is the one we want; it'll tell us how the three extreme equilibria listed are structured.
End of explanation
<END_TASK>