import numpy as np
import quantecon.game_theory as gt


In our module, a normal form game and a player are represented by the classes NormalFormGame and Player, respectively.

A Player carries the player’s payoff function and implements in particular a method that returns the best response action(s) given an action of the opponent player, or a profile of actions of the opponents if there are more than one.

A NormalFormGame is in effect a container of Player instances.

matching_pennies_bimatrix = [[(1, -1), (-1, 1)],
[(-1, 1), (1, -1)]]
g_MP = gt.NormalFormGame(matching_pennies_bimatrix)

print(g_MP)
print("Player Instance; \n",g_MP.players[1])  # Player instance for player 1
print("Player 1's payoff array\n",g_MP.players[1].payoff_array)  # Player 1's payoff array
print("payoff profile for action profile (0, 0)\n",g_MP[0, 0])  # payoff profile for action profile (0, 0)


2-player NormalFormGame with payoff profile array:
[[[ 1, -1],  [-1,  1]],
[[-1,  1],  [ 1, -1]]]
Player Instance;
Player in a 2-player normal form game with payoff array:
[[-1,  1],
[ 1, -1]]
Player 1's payoff array
[[-1  1]
[ 1 -1]]
payoff profile for action profile (0, 0)
[ 1 -1]


The game_theory module also supports games with more than two players.

Let us consider the following version of N -player Cournot Game.

from quantecon import cartesian

def cournot(a, c, N, q_grid):
"""
Create a NormalFormGame instance for the symmetric N-player Cournot game
with linear inverse demand a - Q and constant marginal cost c.

Parameters
----------
a : scalar
Intercept of the demand curve

c : scalar
Common constant marginal cost

N : scalar(int)
Number of firms

q_grid : array_like(scalar)
Array containing the set of possible quantities

Returns
-------
NormalFormGame
NormalFormGame instance representing the Cournot game

"""
q_grid = np.asarray(q_grid)
payoff_array = \
cartesian([q_grid]*N).sum(axis=-1).reshape([len(q_grid)]*N) * (-1) + \
(a - c)
payoff_array *= q_grid.reshape([len(q_grid)] + [1]*(N-1))
payoff_array += 0  # To get rid of the minus sign of -0

player = gt.Player(payoff_array)
return gt.NormalFormGame([player for i in range(N)])


Here’s a simple example with three firms, marginal cost 20, and inverse demand function 80−Q, where the feasible quantity values are assumed to be 10 and 15.



a, c = 80, 20
N = 3
q_grid = [10, 15]  # [1/3 of Monopoly quantity, Nash equilibrium quantity]

g_Cou = cournot(a, c, N, q_grid)


print(g_Cou)

3-player NormalFormGame with payoff profile array:
[[[[300, 300, 300],   [250, 250, 375]],
[[250, 375, 250],   [200, 300, 300]]],

[[[375, 250, 250],   [300, 200, 300]],
[[300, 300, 200],   [225, 225, 225]]]]


Finding Nash equilibria

There are several algorithms implemented to compute Nash equilibria:

Brute force Find all pure-action Nash equilibria of an N player game (if any). Sequential best response Find one pure-action Nash equilibrium of an N player game (if any). Support enumeration Find all mixed-action Nash equilibria of a two-player nondegenerate game. Vertex enumeration Find all mixed-action Nash equilibria of a two-player nondegenerate game. Lemke-Howson Find one mixed-action Nash equilibrium of a two-player game. McLennan-Tourky Find one mixed-action Nash equilibrium of an N player game.

For more variety of algorithms, one should look at Gambit.

def print_pure_nash_brute(g):
"""
Print all pure Nash equilibria of a normal form game found by brute force.

Parameters
----------
g : NormalFormGame

"""
NEs = gt.pure_nash_brute(g)
num_NEs = len(NEs)
if num_NEs == 0:
msg = 'no pure Nash equilibrium'
elif num_NEs == 1:
msg = '1 pure Nash equilibrium:\n{0}'.format(NEs)
else:
msg = '{0} pure Nash equilibria:\n{1}'.format(num_NEs, NEs)

print('The game has ' + msg)

print_pure_nash_brute(g_Cou)

The game has 1 pure Nash equilibrium:
[(1, 1, 1)]

def sequential_best_response(g, init_actions=None, tie_breaking='smallest',
verbose=True):
"""
Find a pure Nash equilibrium of a normal form game by sequential best
response.

Parameters
----------
g : NormalFormGame

init_actions : array_like(int), optional(default=[0, ..., 0])
The initial action profile.

tie_breaking : {'smallest', 'random'}, optional(default='smallest')

verbose: bool, optional(default=True)
If True, print the intermediate process.

"""
N = g.N  # Number of players
a = np.empty(N, dtype=int)  # Action profile
if init_actions is None:
init_actions = [0] * N
a[:] = init_actions

if verbose:
print('init_actions: {0}'.format(a))

new_a = np.empty(N, dtype=int)
max_iter = np.prod(g.nums_actions)

for t in range(max_iter):
new_a[:] = a
for i, player in enumerate(g.players):
if N == 2:
a_except_i = new_a[1-i]
else:
a_except_i = new_a[np.arange(i+1, i+N) % N]
new_a[i] = player.best_response(a_except_i,
tie_breaking=tie_breaking)
if verbose:
print('player {0}: {1}'.format(i, new_a))
if np.array_equal(new_a, a):
return a
else:
a[:] = new_a

print('No pure Nash equilibrium found')
return None


A Cournot game with linear demand is known to be a potential game, for which sequential best response converges to a Nash equilibrium.

Let us try a bigger instance:



a, c = 80, 20
N = 3
q_grid = np.linspace(0, a-c, 13)  # [0, 5, 10, ..., 60]
g_Cou = cournot(a, c, N, q_grid)


a_star = sequential_best_response(g_Cou)  # By default, start with (0, 0, 0)
print('Nash equilibrium indices: {0}'.format(a_star))
print('Nash equilibrium quantities: {0}'.format(q_grid[a_star]))

init_actions: [0 0 0]
player 0: [6 0 0]
player 1: [6 3 0]
player 2: [6 3 1]
player 0: [4 3 1]
player 1: [4 3 1]
player 2: [4 3 2]
player 0: [3 3 2]
player 1: [3 3 2]
player 2: [3 3 3]
player 0: [3 3 3]
player 1: [3 3 3]
player 2: [3 3 3]
Nash equilibrium indices: [3 3 3]
Nash equilibrium quantities: [15. 15. 15.]



sequential_best_response(g_Cou, init_actions=(12, 12, 12))


init_actions: [12 12 12]
player 0: [ 0 12 12]
player 1: [ 0  0 12]
player 2: [0 0 6]
player 0: [3 0 6]
player 1: [3 1 6]
player 2: [3 1 4]
player 0: [3 1 4]
player 1: [3 2 4]
player 2: [3 2 3]
player 0: [3 2 3]
player 1: [3 3 3]
player 2: [3 3 3]
player 0: [3 3 3]
player 1: [3 3 3]
player 2: [3 3 3]

array([3, 3, 3])

# The limit action profile is indeed a Nash equilibrium:
g_Cou.is_nash(a_star)

True

# In fact, the game has other Nash equilibria (because of our choice of grid points and parameter values):

print_pure_nash_brute(g_Cou)

The game has 7 pure Nash equilibria:
[(2, 3, 4), (2, 4, 3), (3, 2, 4), (3, 3, 3), (3, 4, 2), (4, 2, 3), (4, 3, 2)]


Next, let us study the All-Pay Acution, where, unlike standard auctions, bidders pay their bids regardless of whether or not they win. Situations modeled as all-pay auctions include job promotion, R&D, and rent seeking competitions, among others.

Here we consider a version of All-Pay Auction with complete information, symmetric bidders, discrete bids, bid caps, and “full dissipation” (where the prize is materialized if and only if there is only one bidder who makes a highest bid).

from numba import jit

def all_pay_auction(r, c, N, dissipation=True):
"""
Create a NormalFormGame instance for the symmetric N-player
All-Pay Auction game with common reward r and common bid cap e.

Parameters
----------
r : scalar(float)
Common reward value.

c : scalar(int)
Common bid cap.

N : scalar(int)
Number of players.

dissipation : bool, optional(default=True)
If True, the prize fully dissipates in case of a tie. If False,
the prize is equally split among the highest bidders (or given
to one of the highest bidders with equal probabilities).

Returns
-------
NormalFormGame
NormalFormGame instance representing the All-Pay Auction game.

"""
player = gt.Player(np.empty((c+1,)*N))
populate_APA_payoff_array(r, dissipation, player.payoff_array)
return gt.NormalFormGame((player,)*N)

@jit(nopython=True)
def populate_APA_payoff_array(r, dissipation, out):
"""
Populate the payoff array for a player in an N-player All-Pay
Auction game.

Parameters
----------
r : scalar(float)
Reward value.

dissipation : bool, optional(default=True)
If True, the prize fully dissipates in case of a tie. If False,
the prize is equally split among the highest bidders (or given
to one of the highest bidders with equal probabilities).

out : ndarray(float, ndim=N)
NumPy array to store the payoffs. Modified in place.

Returns
-------
out : ndarray(float, ndim=N)
View of out.

"""
nums_actions = out.shape
N = out.ndim
for bids in np.ndindex(nums_actions):
out[bids] = -bids[0]
num_ties = 1
for j in range(1, N):
if bids[j] > bids[0]:
num_ties = 0
break
elif bids[j] == bids[0]:
if dissipation:
num_ties = 0
break
else:
num_ties += 1
if num_ties > 0:
out[bids] += r / num_ties
return out

# Consider the two-player case with the following parameter values:

N = 2
c = 5  # odd
r = 8

g_APA_odd = all_pay_auction(r, c, N)
print(g_APA_odd)

2-player NormalFormGame with payoff profile array:
[[[ 0.,  0.],  [ 0.,  7.],  [ 0.,  6.],  [ 0.,  5.],  [ 0.,  4.],  [ 0.,  3.]],
[[ 7.,  0.],  [-1., -1.],  [-1.,  6.],  [-1.,  5.],  [-1.,  4.],  [-1.,  3.]],
[[ 6.,  0.],  [ 6., -1.],  [-2., -2.],  [-2.,  5.],  [-2.,  4.],  [-2.,  3.]],
[[ 5.,  0.],  [ 5., -1.],  [ 5., -2.],  [-3., -3.],  [-3.,  4.],  [-3.,  3.]],
[[ 4.,  0.],  [ 4., -1.],  [ 4., -2.],  [ 4., -3.],  [-4., -4.],  [-4.,  3.]],
[[ 3.,  0.],  [ 3., -1.],  [ 3., -2.],  [ 3., -3.],  [ 3., -4.],  [-5., -5.]]]

## no pure nash

gt.pure_nash_brute(g_APA_odd)

[]


As pointed out by Dechenaux et al. (2006), there are three Nash equilibria when the bid cap c is odd (so that there are an even number of actions for each player):

gt.support_enumeration(g_APA_odd)


[(array([0.5 , 0.  , 0.25, 0.  , 0.25, 0.  ]),
array([0.  , 0.25, 0.  , 0.25, 0.  , 0.5 ])),
(array([0.  , 0.25, 0.  , 0.25, 0.  , 0.5 ]),
array([0.5 , 0.  , 0.25, 0.  , 0.25, 0.  ])),
(array([0.125, 0.125, 0.125, 0.125, 0.125, 0.375]),
array([0.125, 0.125, 0.125, 0.125, 0.125, 0.375]))]

c = 6  # even
g_APA_even = all_pay_auction(r, c, N)
gt.support_enumeration(g_APA_even)

[(array([0.125, 0.125, 0.125, 0.125, 0.125, 0.125, 0.25 ]),
array([0.125, 0.125, 0.125, 0.125, 0.125, 0.125, 0.25 ]))]