bimatrix_generators¶
This module contains functions that generate NormalFormGame instances of the 2player games studied by Fearnley, Igwe, and Savani (2015):
 Colonel Blotto Games (blotto_game): A nonzero sum extension of the Blotto game as studied by HortalaVallve and LlorenteSaguer (2012), where opposing parties have asymmetric and heterogeneous battlefield valuations.
 Ranking Games (ranking_game): In these games, as studied by Goldberg et al. (2013), each player chooses an effort level associated with a cost and a score. The players are ranked according to their scores, and the player with the higher score wins the prize. Each player’s payoff is given by the value of the prize minus the cost of the effort.
 SGC Games (sgc_game): These games were introduced by Sandholm, Gilpin, and Conitzer (2005) as a worst case scenario for support enumeration as it has a unique equilibrium where each player uses half of his actions in his support.
 Tournament Games (tournament_game): These games are constructed by Anbalagan et al. (2013) as games that do not have interim epsilonNash equilibria with constant cardinality supports for epsilon smaller than a certain threshold.
 Unit Vector Games (unit_vector_game): These games are games where the payoff matrix of one player consists of unit (column) vectors, used by Savani and von Stengel (2016) to construct instances that are hard, in terms of computational complexity, both for the LemkeHowson and support enumeration algorithms.
Large part of the code here is based on the C code available at https://github.com/bimatrixgames/bimatrixgenerators distributed under BSD 3Clause License.
References¶
 Y. Anbalagan, S. Norin, R. Savani, and A. Vetta, “Polylogarithmic Supports Are Required for Approximate WellSupported Nash Equilibria below 2/3,” WINE, 2013.
 J. Fearnley, T. P. Igwe, and R. Savani, “An Empirical Study of Finding Approximate Equilibria in Bimatrix Games,” International Symposium on Experimental Algorithms (SEA), 2015.
 L. A. Goldberg, P. W. Goldberg, P. Krysta, and C. Ventre, “Ranking Games that have Competitivenessbased Strategies”, Theoretical Computer Science, 2013.
 R. HortalaVallve and A. LlorenteSaguer, “Pure Strategy Nash Equilibria in NonZero Sum Colonel Blotto Games”, International Journal of Game Theory, 2012.
 T. Sandholm, A. Gilpin, and V. Conitzer, “MixedInteger Programming Methods for Finding Nash Equilibria,” AAAI, 2005.
 R. Savani and B. von Stengel, “Unit Vector Games,” International Journal of Economic Theory, 2016.

quantecon.game_theory.game_generators.bimatrix_generators.
blotto_game
(h, t, rho, mu=0, random_state=None)[source]¶ Return a NormalFormGame instance of a 2player nonzero sum Colonel Blotto game (HortalaVallve and LlorenteSaguer, 2012), where the players have an equal number t of troops to assign to h hills (so that the number of actions for each player is equal to (t+h1) choose (h1) = (t+h1)!/(t!*(h1)!)). Each player has a value for each hill that he receives if he assigns strictly more troops to the hill than his opponent (ties are broken uniformly at random), where the values are drawn from a multivariate normal distribution with covariance rho. Each player’s payoff is the sum of the values of the hills won by that player.
Parameters:  h : scalar(int)
Number of hills.
 t : scalar(int)
Number of troops.
 rho : scalar(float)
Covariance of the players’ values of each hill. Must be in [1, 1].
 mu : scalar(float), optional(default=0)
Mean of the players’ values of each hill.
 random_state : int or np.random.RandomState, optional
Random seed (integer) or np.random.RandomState instance to set the initial state of the random number generator for reproducibility. If None, a randomly initialized RandomState is used.
Returns:  g : NormalFormGame
Examples
>>> g = blotto_game(2, 3, 0.5, random_state=1234) >>> g.players[0] Player([[0.44861083, 1.08443468, 1.08443468, 1.08443468], [ 0.18721302, 0.44861083, 1.08443468, 1.08443468], [ 0.18721302, 0.18721302, 0.44861083, 1.08443468], [ 0.18721302, 0.18721302, 0.18721302, 0.44861083]]) >>> g.players[1] Player([[1.20042463, 1.39708658, 1.39708658, 1.39708658], [1.00376268, 1.20042463, 1.39708658, 1.39708658], [1.00376268, 1.00376268, 1.20042463, 1.39708658], [1.00376268, 1.00376268, 1.00376268, 1.20042463]])

quantecon.game_theory.game_generators.bimatrix_generators.
ranking_game
(n, steps=10, random_state=None)[source]¶ Return a NormalFormGame instance of (the 2player version of) the “ranking game” studied by Goldberg et al. (2013), where each player chooses an effort level associated with a score and a cost which are both increasing functions with randomly generated step sizes. The player with the higher score wins the first prize, whose value is 1, and the other player obtains the “second prize” of value 0; in the case of a tie, the first prize is split and each player receives a value of 0.5. The payoff of a player is given by the value of the prize minus the cost of the effort.
Parameters:  n : scalar(int)
Number of actions, i.e, number of possible effort levels.
 steps : scalar(int), optional(default=10)
Parameter determining the upper bound for the size of the random steps for the scores and costs for each player: The step sizes for the scores are drawn from 1, …, steps, while those for the costs are multiples of 1/(n*steps), where the cost of effort level 0 is 0, and the maximum possible cost of effort level n1 is less than or equal to 1.
 random_state : int or np.random.RandomState, optional
Random seed (integer) or np.random.RandomState instance to set the initial state of the random number generator for reproducibility. If None, a randomly initialized RandomState is used.
Returns:  g : NormalFormGame
Examples
>>> g = ranking_game(5, random_state=1234) >>> g.players[0] Player([[ 0. , 0. , 0. , 0. , 0. ], [ 0.82, 0.18, 0.18, 0.18, 0.18], [ 0.8 , 0.8 , 0.2 , 0.2 , 0.2 ], [ 0.68, 0.68, 0.68, 0.32, 0.32], [ 0.66, 0.66, 0.66, 0.66, 0.34]]) >>> g.players[1] Player([[ 1. , 0. , 0. , 0. , 0. ], [ 0.8 , 0.8 , 0.2 , 0.2 , 0.2 ], [ 0.66, 0.66, 0.66, 0.34, 0.34], [ 0.6 , 0.6 , 0.6 , 0.6 , 0.4 ], [ 0.58, 0.58, 0.58, 0.58, 0.58]])

quantecon.game_theory.game_generators.bimatrix_generators.
sgc_game
(k)[source]¶ Return a NormalFormGame instance of the 2player game introduced by Sandholm, Gilpin, and Conitzer (2005), which has a unique Nash equilibrium, where each player plays half of the actions with positive probabilities. Payoffs are normalized so that the minimum and the maximum payoffs are 0 and 1, respectively.
Parameters:  k : scalar(int)
Positive integer determining the number of actions. The returned game will have 4*k1 actions for each player.
Returns:  g : NormalFormGame
Examples
>>> g = sgc_game(2) >>> g.players[0] Player([[ 0.75, 0.5 , 1. , 0.5 , 0.5 , 0.5 , 0.5 ], [ 1. , 0.75, 0.5 , 0.5 , 0.5 , 0.5 , 0.5 ], [ 0.5 , 1. , 0.75, 0.5 , 0.5 , 0.5 , 0.5 ], [ 0. , 0. , 0. , 0.75, 0. , 0. , 0. ], [ 0. , 0. , 0. , 0. , 0.75, 0. , 0. ], [ 0. , 0. , 0. , 0. , 0. , 0.75, 0. ], [ 0. , 0. , 0. , 0. , 0. , 0. , 0.75]]) >>> g.players[1] Player([[ 0.75, 0.5 , 1. , 0.5 , 0.5 , 0.5 , 0.5 ], [ 1. , 0.75, 0.5 , 0.5 , 0.5 , 0.5 , 0.5 ], [ 0.5 , 1. , 0.75, 0.5 , 0.5 , 0.5 , 0.5 ], [ 0. , 0. , 0. , 0. , 0.75, 0. , 0. ], [ 0. , 0. , 0. , 0.75, 0. , 0. , 0. ], [ 0. , 0. , 0. , 0. , 0. , 0. , 0.75], [ 0. , 0. , 0. , 0. , 0. , 0.75, 0. ]])

quantecon.game_theory.game_generators.bimatrix_generators.
tournament_game
(n, k, random_state=None)[source]¶ Return a NormalFormGame instance of the 2player winlose game, whose payoffs are either 0 or 1, introduced by Anbalagan et al. (2013). Player 0 has n actions, which constitute the set of nodes {0, …, n1}, while player 1 has n choose k actions, each corresponding to a subset of k elements of the set of n nodes. Given a randomly generated tournament graph on the n nodes, the payoff for player 0 is 1 if, in the tournament, the node chosen by player 0 dominates all the nodes in the ksubset chosen by player 1. The payoff for player 1 is 1 if player 1’s ksubset contains player 0’s chosen node.
Parameters:  n : scalar(int)
Number of nodes in the tournament graph.
 k : scalar(int)
Size of subsets of nodes in the tournament graph.
 random_state : int or np.random.RandomState, optional
Random seed (integer) or np.random.RandomState instance to set the initial state of the random number generator for reproducibility. If None, a randomly initialized RandomState is used.
Returns:  g : NormalFormGame
Notes
The actions of player 1 are ordered according to the combinatorial number system [1], which is different from the order used in the original library in C.
References
[1] (1, 2) Combinatorial number system, Wikipedia. Examples
>>> g = tournament_game(5, 2, random_state=1234) >>> g.players[0] Player([[ 0., 0., 0., 0., 1., 0., 0., 0., 0., 0.], [ 0., 0., 0., 0., 0., 0., 0., 0., 0., 1.], [ 1., 0., 0., 0., 0., 0., 0., 0., 0., 0.], [ 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.], [ 0., 1., 0., 1., 0., 1., 0., 0., 0., 0.]]) >>> g.players[1] Player([[ 1., 1., 0., 0., 0.], [ 1., 0., 1., 0., 0.], [ 0., 1., 1., 0., 0.], [ 1., 0., 0., 1., 0.], [ 0., 1., 0., 1., 0.], [ 0., 0., 1., 1., 0.], [ 1., 0., 0., 0., 1.], [ 0., 1., 0., 0., 1.], [ 0., 0., 1., 0., 1.], [ 0., 0., 0., 1., 1.]])

quantecon.game_theory.game_generators.bimatrix_generators.
unit_vector_game
(n, avoid_pure_nash=False, random_state=None)[source]¶ Return a NormalFormGame instance of the 2player game “unit vector game” (Savani and von Stengel, 2016). Payoffs for player 1 are chosen randomly from the [0, 1) range. For player 0, each column contains exactly one 1 payoff and the rest is 0.
Parameters:  n : scalar(int)
Number of actions.
 avoid_pure_nash : bool, optional(default=False)
If True, player 0’s payoffs will be placed in order to avoid pure Nash equilibria. (If necessary, the payoffs for player 1 are redrawn so as not to have a dominant action.)
 random_state : int or np.random.RandomState, optional
Random seed (integer) or np.random.RandomState instance to set the initial state of the random number generator for reproducibility. If None, a randomly initialized RandomState is used.
Returns:  g : NormalFormGame
Examples
>>> g = unit_vector_game(4, random_state=1234) >>> g.players[0] Player([[ 1., 0., 1., 0.], [ 0., 0., 0., 1.], [ 0., 0., 0., 0.], [ 0., 1., 0., 0.]]) >>> g.players[1] Player([[ 0.19151945, 0.62210877, 0.43772774, 0.78535858], [ 0.77997581, 0.27259261, 0.27646426, 0.80187218], [ 0.95813935, 0.87593263, 0.35781727, 0.50099513], [ 0.68346294, 0.71270203, 0.37025075, 0.56119619]])
With avoid_pure_nash=True:
>>> g = unit_vector_game(4, avoid_pure_nash=True, random_state=1234) >>> g.players[0] Player([[ 1., 1., 0., 0.], [ 0., 0., 0., 0.], [ 0., 0., 1., 1.], [ 0., 0., 0., 0.]]) >>> g.players[1] Player([[ 0.19151945, 0.62210877, 0.43772774, 0.78535858], [ 0.77997581, 0.27259261, 0.27646426, 0.80187218], [ 0.95813935, 0.87593263, 0.35781727, 0.50099513], [ 0.68346294, 0.71270203, 0.37025075, 0.56119619]]) >>> pure_nash_brute(g) []