normal_form_game

Authors: Tomohiro Kusano, Daisuke Oyama

Tools for normal form games.

Definitions and Basic Concepts

An \(N\)-player normal form game \(g = (I, (A_i)_{i \in I}, (u_i)_{i \in I})\) consists of

  • the set of players \(I = \{0, \ldots, N-1\}\),
  • the set of actions \(A_i = \{0, \ldots, n_i-1\}\) for each player \(i \in I\), and
  • the payoff function \(u_i \colon A_i \times A_{i+1} \times \cdots \times A_{i+N-1} \to \mathbb{R}\) for each player \(i \in I\),

where \(i+j\) is understood modulo \(N\). Note that we adopt the convention that the 0-th argument of the payoff function \(u_i\) is player \(i\)‘s own action and the \(j\)-th argument is player (\(i+j\))’s action (modulo \(N\)). A mixed action for player \(i\) is a probability distribution on \(A_i\) (while an element of \(A_i\) is referred to as a pure action). A pure action \(a_i \in A_i\) is identified with the mixed action that assigns probability one to \(a_i\). Denote the set of mixed actions of player \(i\) by \(X_i\). We also denote \(A_{-i} = A_{i+1} \times \cdots \times A_{i+N-1}\) and \(X_{-i} = X_{i+1} \times \cdots \times X_{i+N-1}\).

The (pure-action) best response correspondence \(b_i \colon X_{-i} \to A_i\) for each player \(i\) is defined by

\[b_i(x_{-i}) = \{a_i \in A_i \mid u_i(a_i, x_{-i}) \geq u_i(a_i', x_{-i}) \ \forall\,a_i' \in A_i\},\]

where \(u_i(a_i, x_{-i}) = \sum_{a_{-i} \in A_{-i}} u_i(a_i, a_{-i}) \prod_{j=1}^{N-1} x_{i+j}(a_j)\) is the expected payoff to action \(a_i\) against mixed actions \(x_{-i}\). A profile of mixed actions \(x^* \in X_0 \times \cdots \times X_{N-1}\) is a Nash equilibrium if for all \(i \in I\) and \(a_i \in A_i\),

\[\begin{split}x_i^*(a_i) > 0 \Rightarrow a_i \in b_i(x_{-i}^*),\end{split}\]

or equivalently, \(x_i^* \cdot v_i(x_{-i}^*) \geq x_i \cdot v_i(x_{-i}^*)\) for all \(x_i \in X_i\), where \(v_i(x_{-i})\) is the vector of player \(i\)‘s payoffs when the opponent players play mixed actions \(x_{-i}\).

Creating a NormalFormGame

There are three ways to construct a NormalFormGame instance.

The first is to pass an array of payoffs for all the players:

>>> matching_pennies_bimatrix = [[(1, -1), (-1, 1)], [(-1, 1), (1, -1)]]
>>> g = NormalFormGame(matching_pennies_bimatrix)
>>> print(g.players[0])
Player in a 2-player normal form game with payoff array:
[[ 1, -1],
 [-1,  1]]
>>> print(g.players[1])
Player in a 2-player normal form game with payoff array:
[[-1,  1],
 [ 1, -1]]

If a square matrix (2-dimensional array) is given, then it is considered to be a symmetric two-player game:

>>> coordination_game_matrix = [[4, 0], [3, 2]]
>>> g = NormalFormGame(coordination_game_matrix)
>>> print(g)
2-player NormalFormGame with payoff profile array:
[[[4, 4],  [0, 3]],
 [[3, 0],  [2, 2]]]

The second is to specify the sizes of the action sets of the players, which gives a NormalFormGame instance filled with payoff zeros, and then set the payoff values to each entry:

>>> g = NormalFormGame((2, 2))
>>> print(g)
2-player NormalFormGame with payoff profile array:
[[[ 0.,  0.],  [ 0.,  0.]],
 [[ 0.,  0.],  [ 0.,  0.]]]
>>> g[0, 0] = 1, 1
>>> g[0, 1] = -2, 3
>>> g[1, 0] = 3, -2
>>> print(g)
2-player NormalFormGame with payoff profile array:
[[[ 1.,  1.],  [-2.,  3.]],
 [[ 3., -2.],  [ 0.,  0.]]]

The third is to pass an array of Player instances, as explained in the next section.

Creating a Player

A Player instance is created by passing a payoff array:

>>> player0 = Player([[3, 1], [0, 2]])
>>> player0.payoff_array
array([[3, 1],
       [0, 2]])

Passing an array of Player instances is the third way to create a NormalFormGame instance.

>>> player1 = Player([[2, 0], [1, 3]])
>>> player1.payoff_array
array([[2, 0],
       [1, 3]])
>>> g = NormalFormGame((player0, player1))
>>> print(g)
2-player NormalFormGame with payoff profile array:
[[[3, 2],  [1, 1]],
 [[0, 0],  [2, 3]]]

Beware that in payoff_array[h, k], h refers to the player’s own action, while k refers to the opponent player’s action.

class quantecon.game_theory.normal_form_game.NormalFormGame(data)[source]

Bases: object

Class representing an N-player normal form game.

Parameters:

data : array_like(Player) or array_like(int, ndim=1) or

array_like(float, ndim=2 or N+1)

Data to initialize a NormalFormGame. data may be an array of Players, in which case the shapes of the Players’ payoff arrays must be consistent. If data is an array of N integers, then these integers are treated as the numbers of actions of the N players and a NormalFormGame is created consisting of payoffs all 0 with data[i] actions for each player i. data may also be an (N+1)-dimensional array representing payoff profiles. If data is a square matrix (2-dimensional array), then the game will be a symmetric two-player game where the payoff matrix of each player is given by the input matrix.

Attributes

players (tuple(Player)) Tuple of the Player instances of the game.
N (scalar(int)) The number of players.
nums_actions (tuple(int)) Tuple of the numbers of actions, one for each player.

Methods

is_nash(action_profile) Return True if action_profile is a Nash equilibrium.
is_nash(action_profile)[source]

Return True if action_profile is a Nash equilibrium.

Parameters:

action_profile : array_like(int or array_like(float))

An array of N objects, where each object must be an integer (pure action) or an array of floats (mixed action).

Returns:

bool

True if action_profile is a Nash equilibrium; False otherwise.

payoff_profile_array
class quantecon.game_theory.normal_form_game.Player(payoff_array)[source]

Bases: object

Class representing a player in an N-player normal form game.

Parameters:

payoff_array : array_like(float)

Array representing the player’s payoff function, where payoff_array[a_0, a_1, ..., a_{N-1}] is the payoff to the player when the player plays action a_0 while his N-1 opponents play actions a_1, ..., a_{N-1}, respectively.

Attributes

payoff_array (ndarray(float, ndim=N)) See Parameters.
num_actions (scalar(int)) The number of actions available to the player.
num_opponents (scalar(int)) The number of opponent players.

Methods

best_response(opponents_actions[, ...]) Return the best response action(s) to opponents_actions.
is_best_response(own_action, opponents_actions) Return True if own_action is a best response to opponents_actions.
payoff_vector(opponents_actions) Return an array of payoff values, one for each own action, given a profile of the opponents’ actions.
random_choice([actions, random_state]) Return a pure action chosen randomly from actions.
best_response(opponents_actions, tie_breaking='smallest', payoff_perturbation=None, random_state=None)[source]

Return the best response action(s) to opponents_actions.

Parameters:

opponents_actions : array_like(int or array_like(float)) or

array_like(int, ndim=1) or scalar(int)

A profile of N-1 opponents’ actions. If N=2, then it must be a 1-dimensional array of floats (in which case it is treated as the opponent’s mixed action) or a scalar of integer (in which case it is treated as the opponent’s pure action). If N>2, then it must be an array of N-1 objects, where each object must be an integer (pure action) or an array of floats (mixed action).

tie_breaking : {‘smallest’, ‘random’, False},

optional(default=’smallest’)

Control how, or whether, to break a tie (see Returns for details).

payoff_perturbation : array_like(float), optional(default=None)

Array of length equal to the number of actions of the player containing the values (“noises”) to be added to the payoffs in determining the best response.

random_state : scalar(int) or np.random.RandomState,

optional(default=None)

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. Relevant only when tie_breaking=’random’.

Returns:

scalar(int) or ndarray(int, ndim=1)

If tie_breaking=False, returns an array containing all the best response pure actions. If tie_breaking=’smallest’, returns the best response action with the smallest index; if tie_breaking=’random’, returns an action randomly chosen from the best response actions.

is_best_response(own_action, opponents_actions)[source]

Return True if own_action is a best response to opponents_actions.

Parameters:

own_action : scalar(int) or array_like(float, ndim=1)

An integer representing a pure action, or an array of floats representing a mixed action.

opponents_actions : see best_response

Returns:

bool

True if own_action is a best response to opponents_actions; False otherwise.

payoff_vector(opponents_actions)[source]

Return an array of payoff values, one for each own action, given a profile of the opponents’ actions.

Parameters:

opponents_actions : see best_response.

Returns:

payoff_vector : ndarray(float, ndim=1)

An array representing the player’s payoff vector given the profile of the opponents’ actions.

random_choice(actions=None, random_state=None)[source]

Return a pure action chosen randomly from actions.

Parameters:

actions : array_like(int), optional(default=None)

An array of integers representing pure actions.

random_state : scalar(int) or np.random.RandomState,

optional(default=None)

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:

scalar(int)

If actions is given, returns an integer representing a pure action chosen randomly from actions; if not, an action is chosen randomly from the player’s all actions.

quantecon.game_theory.normal_form_game.best_response_2p[source]

Numba-optimized version of Player.best_response compilied in nopython mode, specialized for 2-player games (where there is only one opponent).

Return the best response action (with the smallest index if more than one) to opponent_mixed_action under payoff_matrix.

Parameters:

payoff_matrix : ndarray(float, ndim=2)

Payoff matrix.

opponent_mixed_action : ndarray(float, ndim=1)

Opponent’s mixed action. Its length must be equal to payoff_matrix.shape[1].

quantecon.game_theory.normal_form_game.pure2mixed(num_actions, action)[source]

Convert a pure action to the corresponding mixed action.

Parameters:

num_actions : scalar(int)

The number of the pure actions (= the length of a mixed action).

action : scalar(int)

The pure action to convert to the corresponding mixed action.

Returns:

ndarray(float, ndim=1)

The mixed action representation of the given pure action.