This module implements a class for normal form games (strategic form games) [NN2007]. At present 3 algorithms are implemented to compute equilibria of these games ('lrs' - interfaced with the ‘lrs’ library, 'LCP' interfaced with the ‘gambit’ library and support enumeration built in Sage). The architecture for the class is based on the gambit architecture to ensure an easy transition between gambit and Sage. At present the algorithms for the computation of equilibria only solve 2 player games.
A very simple and well known example of normal form game is referred to as the ‘Battle of the Sexes’ in which two players Amy and Bob are modeled. Amy prefers to play video games and Bob prefers to watch a movie. They both however want to spend their evening together. This can be modeled using the following two matrices:
Matrix represents the utilities of Amy and matrix
represents the
utility of Bob. The choices of Amy correspond to the rows of the matrices:
Similarly Bob’s choices are represented by the columns:
Thus, if both Amy and Bob choose to play video games: Amy receives a utility of 3 and Bob a utility of 2. If Amy is indeed going to stick with video games Bob has no incentive to deviate (and vice versa).
This situation repeats itself if both Amy and Bob choose to watch a movie: neither has an incentive to deviate.
This loosely described situation is referred to as a Nash Equilibrium. We can use Sage to find them, and more importantly, see if there is any other situation where Amy and Bob have no reason to change their choice of action:
Here is how we create the game in Sage:
sage: A = matrix([[3, 1], [0, 2]])
sage: B = matrix([[2, 1], [0, 3]])
sage: battle_of_the_sexes = NormalFormGame([A, B])
sage: battle_of_the_sexes
Normal Form Game with the following utilities: {(0, 1): [1, 1], (1, 0): [0, 0], (0, 0): [3, 2], (1, 1): [2, 3]}
To obtain the Nash equilibria we run the obtain_nash() method. In the first few examples, we will use the ‘support enumeration’ algorithm. A discussion about the different algorithms will be given later:
sage: battle_of_the_sexes.obtain_nash(algorithm='enumeration')
[[(0, 1), (0, 1)], [(3/4, 1/4), (1/4, 3/4)], [(1, 0), (1, 0)]]
If we look a bit closer at our output we see that a list of three pairs of tuples have been returned. Each of these correspond to a Nash Equilibrium, represented as a probability distribution over the available strategies:
We can use Sage to compute the expected utility for any mixed strategy
pair . The payoff to player 1 is given by the
vector/matrix multiplication:
The payoff to player 2 is given by:
To compute this in Sage we have:
sage: for ne in battle_of_the_sexes.obtain_nash(algorithm='enumeration'):
....: print "Utility for {}: ".format(ne)
....: print vector(ne[0]) * A * vector(ne[1]), vector(ne[0]) * B * vector(ne[1])
Utility for [(0, 1), (0, 1)]:
2 3
Utility for [(3/4, 1/4), (1/4, 3/4)]:
3/2 3/2
Utility for [(1, 0), (1, 0)]:
3 2
Allowing players to play mixed strategies ensures that there will always be a Nash Equilibrium for a normal form game. This result is called Nash’s Theorem ([N1950]).
Let us consider the game called ‘matching pennies’ where two players each present a coin with either HEADS or TAILS showing. If the coins show the same side then player 1 wins, otherwise player 2 wins:
It should be relatively straightforward to observe, that there is no situation, where both players always do the same thing, and have no incentive to deviate.
We can plot the utility of player 1 when player 2 is playing a mixed
strategy (so that the utility to player 1 for
playing strategy number
is given by the matrix/vector multiplication
, ie element in position
of the matrix/vector multiplication
)
sage: y = var('y')
sage: A = matrix([[1, -1], [-1, 1]])
sage: p = plot((A * vector([y, 1 - y]))[0], y, 0, 1, color='blue', legend_label='$u_1(r_1, (y, 1-y))$', axes_labels=['$y$', ''])
sage: p += plot((A * vector([y, 1 - y]))[1], y, 0, 1, color='red', legend_label='$u_1(r_2, (y, 1-y))$'); p
Graphics object consisting of 2 graphics primitives
We see that the only point at which player 1 is indifferent amongst
the available strategies is when .
If we compute the Nash equilibria we see that this corresponds to a point at which both players are indifferent:
sage: A = matrix([[1, -1], [-1, 1]])
sage: B = matrix([[-1, 1], [1, -1]])
sage: matching_pennies = NormalFormGame([A, B])
sage: matching_pennies.obtain_nash(algorithm='enumeration')
[[(1/2, 1/2), (1/2, 1/2)]]
The utilities to both players at this Nash equilibrium is easily computed:
sage: [vector([1/2, 1/2]) * M * vector([1/2, 1/2]) for M in matching_pennies.payoff_matrices()]
[0, 0]
Note that the above uses the payoff_matrices method which returns the payoff matrices for a 2 player game:
sage: matching_pennies.payoff_matrices()
(
[ 1 -1] [-1 1]
[-1 1], [ 1 -1]
)
One can also input a single matrix and then a zero sum game is constructed. Here is an instance of Rock-Paper-Scissors-Lizard-Spock:
sage: A = matrix([[0, -1, 1, 1, -1],
....: [1, 0, -1, -1, 1],
....: [-1, 1, 0, 1 , -1],
....: [-1, 1, -1, 0, 1],
....: [1, -1, 1, -1, 0]])
sage: g = NormalFormGame([A])
sage: g.obtain_nash(algorithm='enumeration')
[[(1/5, 1/5, 1/5, 1/5, 1/5), (1/5, 1/5, 1/5, 1/5, 1/5)]]
We can also study games where players aim to minimize their utility. Here is the Prisoner’s Dilemma (where players are aiming to reduce time spent in prison):
sage: A = matrix([[2, 5], [0, 4]])
sage: B = matrix([[2, 0], [5, 4]])
sage: prisoners_dilemma = NormalFormGame([A, B])
sage: prisoners_dilemma.obtain_nash(algorithm='enumeration', maximization=False)
[[(0, 1), (0, 1)]]
When obtaining Nash equilibrium there are 3 algorithms currently available:
Below we show how the three algorithms are called:
sage: matching_pennies.obtain_nash(algorithm='lrs') # optional - lrs
[[(1/2, 1/2), (1/2, 1/2)]]
sage: matching_pennies.obtain_nash(algorithm='LCP') # optional - gambit
[[(0.5, 0.5), (0.5, 0.5)]]
sage: matching_pennies.obtain_nash(algorithm='enumeration')
[[(1/2, 1/2), (1/2, 1/2)]]
Note that if no algorithm argument is passed then the default will be selected according to the following order (if the corresponding package is installed):
- 'lrs' (requires ‘lrs’)
- 'enumeration'
Here is a game being constructed using gambit syntax (note that a NormalFormGame object acts like a dictionary with pure strategy tuples as keys and payoffs as their values):
sage: f = NormalFormGame()
sage: f.add_player(2) # Adding first player with 2 strategies
sage: f.add_player(2) # Adding second player with 2 strategies
sage: f[0,0][0] = 1
sage: f[0,0][1] = 3
sage: f[0,1][0] = 2
sage: f[0,1][1] = 3
sage: f[1,0][0] = 3
sage: f[1,0][1] = 1
sage: f[1,1][0] = 4
sage: f[1,1][1] = 4
sage: f
Normal Form Game with the following utilities: {(0, 1): [2, 3], (1, 0): [3, 1], (0, 0): [1, 3], (1, 1): [4, 4]}
Once this game is constructed we can view the payoff matrices and solve the game:
sage: f.payoff_matrices()
(
[1 2] [3 3]
[3 4], [1 4]
)
sage: f.obtain_nash(algorithm='enumeration')
[[(0, 1), (0, 1)]]
We can add an extra strategy to the first player:
sage: f.add_strategy(0)
sage: f
Normal Form Game with the following utilities: {(0, 1): [2, 3], (0, 0): [1, 3], (2, 1): [False, False], (2, 0): [False, False], (1, 0): [3, 1], (1, 1): [4, 4]}
If we do this and try and obtain the Nash equilibrium or view the payoff matrices(without specifying the utilities), an error is returned:
sage: f.obtain_nash()
Traceback (most recent call last):
...
ValueError: utilities have not been populated
sage: f.payoff_matrices()
Traceback (most recent call last):
...
ValueError: utilities have not been populated
Here we populate the missing utilities:
sage: f[2, 1] = [5, 3]
sage: f[2, 0] = [2, 1]
sage: f.payoff_matrices()
(
[1 2] [3 3]
[3 4] [1 4]
[2 5], [1 3]
)
sage: f.obtain_nash()
[[(0, 0, 1), (0, 1)]]
We can use the same syntax as above to create games with more than 2 players:
sage: threegame = NormalFormGame()
sage: threegame.add_player(2) # Adding first player with 2 strategies
sage: threegame.add_player(2) # Adding second player with 2 strategies
sage: threegame.add_player(2) # Adding third player with 2 strategies
sage: threegame[0, 0, 0][0] = 3
sage: threegame[0, 0, 0][1] = 1
sage: threegame[0, 0, 0][2] = 4
sage: threegame[0, 0, 1][0] = 1
sage: threegame[0, 0, 1][1] = 5
sage: threegame[0, 0, 1][2] = 9
sage: threegame[0, 1, 0][0] = 2
sage: threegame[0, 1, 0][1] = 6
sage: threegame[0, 1, 0][2] = 5
sage: threegame[0, 1, 1][0] = 3
sage: threegame[0, 1, 1][1] = 5
sage: threegame[0, 1, 1][2] = 8
sage: threegame[1, 0, 0][0] = 9
sage: threegame[1, 0, 0][1] = 7
sage: threegame[1, 0, 0][2] = 9
sage: threegame[1, 0, 1][0] = 3
sage: threegame[1, 0, 1][1] = 2
sage: threegame[1, 0, 1][2] = 3
sage: threegame[1, 1, 0][0] = 8
sage: threegame[1, 1, 0][1] = 4
sage: threegame[1, 1, 0][2] = 6
sage: threegame[1, 1, 1][0] = 2
sage: threegame[1, 1, 1][1] = 6
sage: threegame[1, 1, 1][2] = 4
sage: threegame
Normal Form Game with the following utilities: {(0, 1, 1): [3, 5, 8], (1, 1, 0): [8, 4, 6], (1, 0, 0): [9, 7, 9], (0, 0, 1): [1, 5, 9], (1, 0, 1): [3, 2, 3], (0, 0, 0): [3, 1, 4], (0, 1, 0): [2, 6, 5], (1, 1, 1): [2, 6, 4]}
The above requires a lot of input that could be simplified if there is another data structure with our utilities and/or a structure to the utilities. The following example creates a game with a relatively strange utility function:
sage: def utility(strategy_triplet, player):
....: return sum(strategy_triplet) * player
sage: threegame = NormalFormGame()
sage: threegame.add_player(2) # Adding first player with 2 strategies
sage: threegame.add_player(2) # Adding second player with 2 strategies
sage: threegame.add_player(2) # Adding third player with 2 strategies
sage: for i, j, k in [(i, j, k) for i in [0,1] for j in [0,1] for k in [0,1]]:
....: for p in range(3):
....: threegame[i, j, k][p] = utility([i, j, k], p)
sage: threegame
Normal Form Game with the following utilities: {(0, 1, 1): [0, 2, 4], (1, 1, 0): [0, 2, 4], (1, 0, 0): [0, 1, 2], (0, 0, 1): [0, 1, 2], (1, 0, 1): [0, 2, 4], (0, 0, 0): [0, 0, 0], (0, 1, 0): [0, 1, 2], (1, 1, 1): [0, 3, 6]}
At present no algorithm has been implemented in Sage for games with more than 2 players:
sage: threegame.obtain_nash()
Traceback (most recent call last):
...
NotImplementedError: Nash equilibrium for games with more than 2 players have not been implemented yet. Please see the gambit website (http://gambit.sourceforge.net/) that has a variety of available algorithms
There are however a variety of such algorithms available in gambit, further compatibility between Sage and gambit is actively being developed: https://github.com/tturocy/gambit/tree/sage_integration.
Note that the Gambit implementation of LCP can only handle integer payoffs. If a non integer payoff is used an error will be raised:
sage: A = matrix([[2, 1], [1, 2.5]])
sage: B = matrix([[-1, 3], [2, 1]])
sage: g = NormalFormGame([A, B])
sage: g.obtain_nash(algorithm='LCP') # optional - gambit
Traceback (most recent call last):
...
ValueError: The Gambit implementation of LCP only allows for integer valued payoffs. Please scale your payoff matrices.
Other algorithms can handle these payoffs:
sage: g.obtain_nash(algorithm='enumeration')
[[(1/5, 4/5), (3/5, 2/5)]]
sage: g.obtain_nash(algorithm='lrs') # optional - lrs
[[(1/5, 4/5), (3/5, 2/5)]]
It can be shown that linear scaling of the payoff matrices conserves the equilibrium values:
sage: A = 2 * A
sage: g = NormalFormGame([A, B])
sage: g.obtain_nash(algorithm='LCP') # optional - gambit
[[(0.2, 0.8), (0.6, 0.4)]]
It is also possible to generate a Normal Form Game from a gambit Game:
sage: from gambit import Game # optional - gambit
sage: gambitgame= Game.new_table([2, 2]) # optional - gambit
sage: gambitgame[int(0), int(0)][int(0)] = int(8) # optional - gambit
sage: gambitgame[int(0), int(0)][int(1)] = int(8) # optional - gambit
sage: gambitgame[int(0), int(1)][int(0)] = int(2) # optional - gambit
sage: gambitgame[int(0), int(1)][int(1)] = int(10) # optional - gambit
sage: gambitgame[int(1), int(0)][int(0)] = int(10) # optional - gambit
sage: gambitgame[int(1), int(0)][int(1)] = int(2) # optional - gambit
sage: gambitgame[int(1), int(1)][int(0)] = int(5) # optional - gambit
sage: gambitgame[int(1), int(1)][int(1)] = int(5) # optional - gambit
sage: g = NormalFormGame(gambitgame) # optional - gambit
sage: g # optional - gambit
Normal Form Game with the following utilities: {(0, 1): [2.0, 10.0], (1, 0): [10.0, 2.0], (0, 0): [8.0, 8.0], (1, 1): [5.0, 5.0]}
For more information on using Gambit in Sage see: Using Gambit in Sage. This includes how to access Gambit directly using the version of iPython shipped with Sage and an explanation as to why the int calls are needed to handle the Sage preparser.
Here is a slightly longer game that would take too long to solve with 'enumeration'. Consider the following:
An airline loses two suitcases belonging to two different travelers. Both suitcases happen to be identical and contain identical antiques. An airline manager tasked to settle the claims of both travelers explains that the airline is liable for a maximum of 10 per suitcase, and in order to determine an honest appraised value of the antiques the manager separates both travelers so they can’t confer, and asks them to write down the amount of their value at no less than 2 and no larger than 100. He also tells them that if both write down the same number, he will treat that number as the true dollar value of both suitcases and reimburse both travelers that amount.
However, if one writes down a smaller number than the other, this smaller number will be taken as the true dollar value, and both travelers will receive that amount along with a bonus/malus: 2 extra will be paid to the traveler who wrote down the lower value and a 2 deduction will be taken from the person who wrote down the higher amount. The challenge is: what strategy should both travelers follow to decide the value they should write down?
In the following we create the game (with a max value of 10) and solve it:
sage: K = 10 # Modifying this value lets us play with games of any size
sage: A = matrix([[min(i,j) + 2 * sign(j-i) for j in range(2, K+1)] for i in range(2, K+1)])
sage: B = matrix([[min(i,j) + 2 * sign(i-j) for j in range(2, K+1)] for i in range(2, K+1)])
sage: g = NormalFormGame([A, B])
sage: g.obtain_nash(algorithm='lrs') # optional - lrs
[[(1, 0, 0, 0, 0, 0, 0, 0, 0), (1, 0, 0, 0, 0, 0, 0, 0, 0)]]
sage: g.obtain_nash(algorithm='LCP') # optional - gambit
[[(1.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0), (1.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0)]]
The output is a pair of vectors (as before) showing the Nash equilibrium. In particular it here shows that out of the 10 possible strategies both players should choose the first. Recall that the above considers a reduced version of the game where individuals can claim integer values between 2 and 10. The equilibrium strategy is thus for both players to state that the value of their suitcase is 2.
Note that degenerate games can cause problems for most algorithms. The following example in fact has an infinite quantity of equilibria which is evidenced by the various algorithms returning different solutions:
sage: A = matrix([[3,3],[2,5],[0,6]])
sage: B = matrix([[3,3],[2,6],[3,1]])
sage: degenerate_game = NormalFormGame([A,B])
sage: degenerate_game.obtain_nash(algorithm='lrs') # optional - lrs
[[(0, 1/3, 2/3), (1/3, 2/3)], [(1, 0, 0), (2/3, 1/3)], [(1, 0, 0), (1, 0)]]
sage: degenerate_game.obtain_nash(algorithm='LCP') # optional - gambit
[[(0.0, 0.3333333333, 0.6666666667), (0.3333333333, 0.6666666667)],
[(1.0, -0.0, 0.0), (0.6666666667, 0.3333333333)],
[(1.0, 0.0, 0.0), (1.0, 0.0)]]
sage: degenerate_game.obtain_nash(algorithm='enumeration')
[[(0, 1/3, 2/3), (1/3, 2/3)], [(1, 0, 0), (1, 0)]]
Note the ‘negative’ output by gambit. This is due to the numerical
nature of the algorithm used.
Here is an example with the trivial game where all payoffs are 0:
sage: g = NormalFormGame()
sage: g.add_player(3) # Adding first player with 3 strategies
sage: g.add_player(3) # Adding second player with 3 strategies
sage: for key in g:
....: g[key] = [0, 0]
sage: g.payoff_matrices()
(
[0 0 0] [0 0 0]
[0 0 0] [0 0 0]
[0 0 0], [0 0 0]
)
sage: g.obtain_nash(algorithm='enumeration')
[[(0, 0, 1), (0, 0, 1)], [(0, 0, 1), (0, 1, 0)], [(0, 0, 1), (1, 0, 0)], [(0, 1, 0), (0, 0, 1)], [(0, 1, 0), (0, 1, 0)], [(0, 1, 0), (1, 0, 0)], [(1, 0, 0), (0, 0, 1)], [(1, 0, 0), (0, 1, 0)], [(1, 0, 0), (1, 0, 0)]]
A good description of degenerate games can be found in [NN2007].
REFERENCES:
[N1950] | John Nash. Equilibrium points in n-person games. Proceedings of the National Academy of Sciences 36.1 (1950): 48-49. |
[NN2007] | (1, 2, 3) Nisan, Noam, et al., eds. Algorithmic game theory. Cambridge University Press, 2007. |
[A2000] | Avis, David. A revised implementation of the reverse search vertex enumeration algorithm. Polytopes-combinatorics and computation Birkhauser Basel, 2000. |
[MMAT2014] | McKelvey, Richard D., McLennan, Andrew M., and Turocy, Theodore L. Gambit: Software Tools for Game Theory, Version 13.1.2. http://www.gambit-project.org (2014). |
[SLB2008] | Shoham, Yoav, and Kevin Leyton-Brown. Multiagent systems: Algorithmic, game-theoretic, and logical foundations. Cambridge University Press, 2008. |
AUTHOR:
Bases: sage.structure.sage_object.SageObject, _abcoll.MutableMapping
An object representing a Normal Form Game. Primarily used to compute the Nash Equilibria.
INPUT:
blank.
Adds a player to a NormalFormGame.
INPUT:
EXAMPLES:
sage: g = NormalFormGame()
sage: g.add_player(2) # Adding first player with 2 strategies
sage: g.add_player(1) # Adding second player with 1 strategy
sage: g.add_player(1) # Adding third player with 1 strategy
sage: g
Normal Form Game with the following utilities: {(1, 0, 0): [False, False, False], (0, 0, 0): [False, False, False]}
Adds a strategy to a player, will not affect already completed strategy profiles.
INPUT:
EXAMPLES:
A simple example:
sage: s = matrix([[1, 0], [-2, 3]])
sage: t = matrix([[3, 2], [-1, 0]])
sage: example = NormalFormGame([s, t])
sage: example
Normal Form Game with the following utilities: {(0, 1): [0, 2], (1, 0): [-2, -1], (0, 0): [1, 3], (1, 1): [3, 0]}
sage: example.add_strategy(0)
sage: example
Normal Form Game with the following utilities: {(0, 1): [0, 2], (0, 0): [1, 3], (2, 1): [False, False], (2, 0): [False, False], (1, 0): [-2, -1], (1, 1): [3, 0]}
A function to return the Nash equilibrium for the game. Optional arguments can be used to specify the algorithm used. If no algorithm is passed then an attempt is made to use the most appropriate algorithm.
INPUT:
this function:
'lrs' - This algorithm is only suited for 2 player games. See the lrs web site (http://cgm.cs.mcgill.ca/~avis/C/lrs.html).
'LCP' - This algorithm is only suited for 2 player games. See the gambit web site (http://gambit.sourceforge.net/). Note that the output differs from the other algorithms: floats are returned.
'enumeration' - This is a very inefficient algorithm (in essence a brute force approach).
Solving the indifference conditions is done by building the
corresponding linear system. If are the
supports player 1 and 2 respectively. Then, indifference implies:
for all in the support of
. This corresponds to:
for all in the support of
where
is the payoff
matrix of player 1. Equivalently we can consider consecutive rows of
(instead of all pairs of strategies). Thus the corresponding
linear system can be written as:
for all (where
has been modified to only
contain the rows corresponding to
). We also require all
elements of
to sum to 1:
utility or minimize it.
EXAMPLES:
A game with 1 equilibrium when maximization is True and 3 when maximization is False:
sage: A = matrix([[10, 500, 44],
....: [15, 10, 105],
....: [19, 204, 55],
....: [20, 200, 590]])
sage: B = matrix([[2, 1, 2],
....: [0, 5, 6],
....: [3, 4, 1],
....: [4, 1, 20]])
sage: g=NormalFormGame([A, B])
sage: g.obtain_nash(algorithm='lrs') # optional - lrs
[[(0, 0, 0, 1), (0, 0, 1)]]
sage: g.obtain_nash(algorithm='lrs', maximization=False) # optional - lrs
[[(2/3, 1/12, 1/4, 0), (6333/8045, 247/8045, 293/1609)], [(3/4, 0, 1/4, 0), (0, 11/307, 296/307)], [(5/6, 1/6, 0, 0), (98/99, 1/99, 0)]]
This particular game has 3 Nash equilibria:
sage: A = matrix([[3,3],
....: [2,5],
....: [0,6]])
sage: B = matrix([[3,2],
....: [2,6],
....: [3,1]])
sage: g = NormalFormGame([A, B])
sage: g.obtain_nash(algorithm='enumeration')
[[(0, 1/3, 2/3), (1/3, 2/3)], [(4/5, 1/5, 0), (2/3, 1/3)], [(1, 0, 0), (1, 0)]]
Here is a slightly larger game:
sage: A = matrix([[160, 205, 44],
....: [175, 180, 45],
....: [201, 204, 50],
....: [120, 207, 49]])
sage: B = matrix([[2, 2, 2],
....: [1, 0, 0],
....: [3, 4, 1],
....: [4, 1, 2]])
sage: g=NormalFormGame([A, B])
sage: g.obtain_nash(algorithm='enumeration')
[[(0, 0, 3/4, 1/4), (1/28, 27/28, 0)]]
sage: g.obtain_nash(algorithm='lrs') # optional - lrs
[[(0, 0, 3/4, 1/4), (1/28, 27/28, 0)]]
sage: g.obtain_nash(algorithm='LCP') # optional - gambit
[[(0.0, 0.0, 0.75, 0.25), (0.0357142857, 0.9642857143, 0.0)]]
2 random matrices:
sage: player1 = matrix([[2, 8, -1, 1, 0],
....: [1, 1, 2, 1, 80],
....: [0, 2, 15, 0, -12],
....: [-2, -2, 1, -20, -1],
....: [1, -2, -1, -2, 1]])
sage: player2 = matrix([[0, 8, 4, 2, -1],
....: [6, 14, -5, 1, 0],
....: [0, -2, -1, 8, -1],
....: [1, -1, 3, -3, 2],
....: [8, -4, 1, 1, -17]])
sage: fivegame = NormalFormGame([player1, player2])
sage: fivegame.obtain_nash(algorithm='enumeration')
[[(1, 0, 0, 0, 0), (0, 1, 0, 0, 0)]]
sage: fivegame.obtain_nash(algorithm='lrs') # optional - lrs
[[(1, 0, 0, 0, 0), (0, 1, 0, 0, 0)]]
sage: fivegame.obtain_nash(algorithm='LCP') # optional - gambit
[[(1.0, 0.0, 0.0, 0.0, 0.0), (0.0, 1.0, 0.0, 0.0, 0.0)]]
Here is an example of a 3 by 2 game with 3 Nash equilibrium:
sage: A = matrix([[3,3],
....: [2,5],
....: [0,6]])
sage: B = matrix([[3,2],
....: [2,6],
....: [3,1]])
sage: g = NormalFormGame([A, B])
sage: g.obtain_nash(algorithm='enumeration')
[[(0, 1/3, 2/3), (1/3, 2/3)], [(4/5, 1/5, 0), (2/3, 1/3)], [(1, 0, 0), (1, 0)]]
Note that outputs for all algorithms are as lists of lists of tuples and the equilibria have been sorted so that all algorithms give a comparable output (although 'LCP' returns floats):
sage: enumeration_eqs = g.obtain_nash(algorithm='enumeration')
sage: [[type(s) for s in eq] for eq in enumeration_eqs]
[[<type 'tuple'>, <type 'tuple'>], [<type 'tuple'>, <type 'tuple'>], [<type 'tuple'>, <type 'tuple'>]]
sage: lrs_eqs = g.obtain_nash(algorithm='lrs') # optional - lrs
sage: [[type(s) for s in eq] for eq in lrs_eqs] # optional - lrs
[[<type 'tuple'>, <type 'tuple'>], [<type 'tuple'>, <type 'tuple'>], [<type 'tuple'>, <type 'tuple'>]]
sage: LCP_eqs = g.obtain_nash(algorithm='LCP') # optional - gambit
sage: [[type(s) for s in eq] for eq in LCP_eqs] # optional - gambit
[[<type 'tuple'>, <type 'tuple'>], [<type 'tuple'>, <type 'tuple'>], [<type 'tuple'>, <type 'tuple'>]]
sage: enumeration_eqs == sorted(enumeration_eqs)
True
sage: lrs_eqs == sorted(lrs_eqs) # optional - lrs
True
sage: LCP_eqs == sorted(LCP_eqs) # optional - gambit
True
sage: lrs_eqs == enumeration_eqs # optional - lrs
True
sage: enumeration_eqs == LCP_eqs # optional - gambit
False
sage: [[[round(float(p), 6) for p in str] for str in eq] for eq in enumeration_eqs] == [[[round(float(p), 6) for p in str] for str in eq] for eq in LCP_eqs] # optional - gambit
True
Returns 2 matrices representing the payoffs for each player.
EXAMPLES:
sage: p1 = matrix([[1, 2], [3, 4]])
sage: p2 = matrix([[3, 3], [1, 4]])
sage: g = NormalFormGame([p1, p2])
sage: g.payoff_matrices()
(
[1 2] [3 3]
[3 4], [1 4]
)
If we create a game with 3 players we will not be able to obtain payoff matrices:
sage: g = NormalFormGame()
sage: g.add_player(2) # Adding first player with 2 strategies
sage: g.add_player(2) # Adding second player with 2 strategies
sage: g.add_player(2) # Adding third player with 2 strategies
sage: g.payoff_matrices()
Traceback (most recent call last):
...
ValueError: Only available for 2 player games
If we do create a two player game but it is not complete then an error is also raised:
sage: g = NormalFormGame()
sage: g.add_player(1) # Adding first player with 1 strategy
sage: g.add_player(1) # Adding second player with 1 strategy
sage: g.payoff_matrices()
Traceback (most recent call last):
...
ValueError: utilities have not been populated
The above creates a 2 player game where each player has a single strategy. Here we populate the strategies and can then view the payoff matrices:
sage: g[0, 0] = [1,2]
sage: g.payoff_matrices()
([1], [2])