**Daisuke Oyama**

*Faculty of Economics, University of Tokyo*

This notebook demonstrates the functionalities of the `game_theory`

module.

In [1]:

```
import numpy as np
import quantecon.game_theory as gt
```

An $N$-player *normal form game* is a triplet $g = (I, (A_i)_{i \in I}, (u_i)_{i \in I})$ where

- $I = \{0, \ldots, N-1\}$ is the set of players,
- $A_i = \{0, \ldots, n_i-1\}$ is the set of actions of player $i \in I$, and
- $u_i \colon A_i \times A_{i+1} \times \cdots \times A_{i+N-1} \to \mathbb{R}$ is the payoff function of 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, $j = 1, \ldots, N-1$, is player ($i+j$)'s action (modulo $N$).

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.

`NormalFormGame`

¶There are several ways to create a `NormalFormGame`

instance.

As an example, consider the following game ("**Matching Pennies**"):

$ \begin{bmatrix} 1, -1 & -1, 1 \\ -1, 1 & 1, -1 \end{bmatrix} $

In [2]:

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

In [3]:

```
print(g_MP)
```

In [4]:

```
print(g_MP.players[0]) # Player instance for player 0
```

In [5]:

```
print(g_MP.players[1]) # Player instance for player 1
```

In [6]:

```
g_MP.players[0].payoff_array # Player 0's payoff array
```

Out[6]:

In [7]:

```
g_MP.players[1].payoff_array # Player 1's payoff array
```

Out[7]:

In [8]:

```
g_MP[0, 0] # payoff profile for action profile (0, 0)
```

Out[8]:

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

Consider the following game (symmetric $2 \times 2$ "**Coordination Game**"):

$ \begin{bmatrix} 4, 4 & 0, 3 \\ 3, 0 & 2, 2 \end{bmatrix} $

In [9]:

```
coordination_game_matrix = [[4, 0],
[3, 2]] # square matrix
g_Coo = gt.NormalFormGame(coordination_game_matrix)
```

In [10]:

```
print(g_Coo)
```

In [11]:

```
g_Coo.players[0].payoff_array # Player 0's payoff array
```

Out[11]:

In [12]:

```
g_Coo.players[1].payoff_array # Player 1's payoff array
```

Out[12]:

Another example ("**Rock-Paper-Scissors**"):

$ \begin{bmatrix} 0, 0 & -1, 1 & 1, -1 \\ 1, -1 & 0, 0 & -1, 1 \\ -1, 1 & 1, -1 & 0, 0 \end{bmatrix} $

In [13]:

```
RPS_matrix = [[ 0, -1, 1],
[ 1, 0, -1],
[-1, 1, 0]]
g_RPS = gt.NormalFormGame(RPS_matrix)
```

In [14]:

```
print(g_RPS)
```

The second is to specify the sizes of the action sets of the players
to create a `NormalFormGame`

instance filled with payoff zeros,
and then set the payoff values to each entry.

Let us construct the following game ("**Prisoners' Dilemma**"):

$ \begin{bmatrix} 1, 1 & -2, 3 \\ 3, -2 & 0, 0 \end{bmatrix} $

In [15]:

```
g_PD = gt.NormalFormGame((2, 2)) # There are 2 players, each of whom has 2 actions
g_PD[0, 0] = 1, 1
g_PD[0, 1] = -2, 3
g_PD[1, 0] = 3, -2
g_PD[1, 1] = 0, 0
```

In [16]:

```
print(g_PD)
```

`NormalFormGame`

instance can be constructed by giving an array of `Player`

instances,
as explained in the next section.

`Player`

¶A `Player`

instance is created by passing an array of dimension $N$
that represents the player's payoff function ("payoff array").

Consider the following game (a variant of "**Battle of the Sexes**"):

$ \begin{bmatrix} 3, 2 & 1, 1 \\ 0, 0 & 2, 3 \end{bmatrix} $

In [17]:

```
player0 = gt.Player([[3, 1],
[0, 2]])
player1 = gt.Player([[2, 0],
[1, 3]])
```

`payoff_array[h, k]`

, `h`

refers to the player's own action,
while `k`

refers to the opponent player's action.

In [18]:

```
player0.payoff_array
```

Out[18]:

In [19]:

```
player1.payoff_array
```

Out[19]:

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

instance:

In [20]:

```
g_BoS = gt.NormalFormGame((player0, player1))
```

In [21]:

```
print(g_BoS)
```

The `game_theory`

module also supports games with more than two players.

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

There are $N$ firms (players) which produce a homogeneous good with common constant marginal cost $c \geq 0$. Each firm $i$ simultaneously determines the quantity $q_i \geq 0$ (action) of the good to produce. The inverse demand function is given by the linear function $P(Q) = a - Q$, $a > 0$, where $Q = q_0 + \cdots + q_{N-1}$ is the aggregate supply. Then the profit (payoff) for firm $i$ is given by $$ u_i(q_i, q_{i+1}, \ldots, q_{i+N-1}) = P(Q) q_i - c q_i = \left(a - c - \sum_{j \neq i} q_j - q_i\right) q_i. $$

Theoretically, the set of actions, i.e., available quantities, may be the set of all nonnegative real numbers $\mathbb{R}_+$ (or a bounded interval $[0, \bar{q}]$ with some upper bound $\bar{q}$), but for computation on a computer we have to discretize the action space and only allow for finitely many grid points.

The following script creates a `NormalFormGame`

instance of the Cournot game as described above,
assuming that the (common) grid of possible quantity values is stored in an array `q_grid`

.

In [22]:

```
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)])
```

In [23]:

```
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)
```

In [24]:

```
print(g_Cou)
```

In [25]:

```
print(g_Cou.players[0])
```

In [26]:

```
g_Cou.nums_actions
```

Out[26]:

*Nash equilibrium* of a normal form game is a profile of actions
where the action of each player is a best response to the others'.

The `Player`

object has a method `best_response`

.

Consider the Matching Pennies game `g_MP`

defined above.
For example, player 0's best response to the opponent's action 1 is:

In [27]:

```
g_MP.players[0].best_response(1)
```

Out[27]:

Player 0's best responses to the opponent's mixed action `[0.5, 0.5]`

(we know they are 0 and 1):

In [28]:

```
# By default, returns the best response action with the smallest index
g_MP.players[0].best_response([0.5, 0.5])
```

Out[28]:

In [29]:

```
# With tie_breaking='random', returns randomly one of the best responses
g_MP.players[0].best_response([0.5, 0.5], tie_breaking='random') # Try several times
```

Out[29]:

In [30]:

```
# With tie_breaking=False, returns an array of all the best responses
g_MP.players[0].best_response([0.5, 0.5], tie_breaking=False)
```

Out[30]:

For this game, we know that `([0.5, 0.5], [0.5, 0.5])`

is a (unique) Nash equilibrium.

In [31]:

```
g_MP.is_nash(([0.5, 0.5], [0.5, 0.5]))
```

Out[31]:

In [32]:

```
g_MP.is_nash((0, 0))
```

Out[32]:

In [33]:

```
g_MP.is_nash((0, [0.5, 0.5]))
```

Out[33]:

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. - 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.

`pure_nash_brute`

.
It visits all the action profiles and check whether each is a Nash equilibrium
by the `is_nash`

method.

In [34]:

```
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)
```

Matching Pennies:

In [35]:

```
print_pure_nash_brute(g_MP)
```

Coordination game:

In [36]:

```
print_pure_nash_brute(g_Coo)
```

Rock-Paper-Scissors:

In [37]:

```
print_pure_nash_brute(g_RPS)
```

Battle of the Sexes:

In [38]:

```
print_pure_nash_brute(g_BoS)
```

Prisoners' Dillema:

In [39]:

```
print_pure_nash_brute(g_PD)
```

Cournot game:

In [40]:

```
print_pure_nash_brute(g_Cou)
```

Here's a script to find *one* pure Nash equilibrium by sequential best response, if it converges.

In [41]:

```
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:

In [42]:

```
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)
```

In [43]:

```
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]))
```

In [44]:

```
# Start with the largest actions (12, 12, 12)
sequential_best_response(g_Cou, init_actions=(12, 12, 12))
```

Out[44]:

The limit action profile is indeed a Nash equilibrium:

In [45]:

```
g_Cou.is_nash(a_star)
```

Out[45]:

In [46]:

```
print_pure_nash_brute(g_Cou)
```

Make it bigger:

In [47]:

```
N = 4
q_grid = np.linspace(0, a-c, 61) # [0, 1, 2, ..., 60]
g_Cou = cournot(a, c, N, q_grid)
```

In [48]:

```
sequential_best_response(g_Cou)
```

Out[48]:

In [49]:

```
sequential_best_response(g_Cou, init_actions=(0, 0, 0, 30))
```

Out[49]:

Sequential best response does not converge in all games:

In [50]:

```
print(g_MP) # Matching Pennies
```

In [51]:

```
sequential_best_response(g_MP)
```

`support_enumeration`

,
which is for two-player games,
visits all equal-size support pairs and
checks whether each pair has a Nash equilibrium (in mixed actions)
by the indifference condition.
(This should thus be used only for small games.)
For nondegenerate games, this routine returns all Nash equilibria.

Matching Pennies:

In [52]:

```
gt.support_enumeration(g_MP)
```

Out[52]:

Coordination game:

In [53]:

```
print(g_Coo)
```

In [54]:

```
gt.support_enumeration(g_Coo)
```

Out[54]:

Rock-Paper-Scissors:

In [55]:

```
print(g_RPS)
```

In [56]:

```
gt.support_enumeration(g_RPS)
```

Out[56]:

Consider the $6 \times 6$ game by von Stengel (1997), page 12:

In [57]:

```
player0 = gt.Player(
[[ 9504, -660, 19976, -20526, 1776, -8976],
[ -111771, 31680, -130944, 168124, -8514, 52764],
[ 397584, -113850, 451176, -586476, 29216, -178761],
[ 171204, -45936, 208626, -263076, 14124, -84436],
[ 1303104, -453420, 1227336, -1718376, 72336, -461736],
[ 737154, -227040, 774576, -1039236, 48081, -300036]]
)
player1 = gt.Player(
[[ 72336, -461736, 1227336, -1718376, 1303104, -453420],
[ 48081, -300036, 774576, -1039236, 737154, -227040],
[ 29216, -178761, 451176, -586476, 397584, -113850],
[ 14124, -84436, 208626, -263076, 171204, -45936],
[ 1776, -8976, 19976, -20526, 9504, -660],
[ -8514, 52764, -130944, 168124, -111771, 31680]]
)
g_vonStengel = gt.NormalFormGame((player0, player1))
```

In [58]:

```
len(gt.support_enumeration(g_vonStengel))
```

Out[58]:

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).

*fully dissipated* and all the players receive nothing.
Thus, player $i$'s payoff function is
$$
u_i(b_i, b_{i+1}, \ldots, b_{i+N-1}) =
\begin{cases}
r - b_i & \text{if $b_i > b_j$ for all $j \neq i$}, \\ - b_i & \text{otherwise}.
\end{cases}
$$

`NormalFormGame`

instance
for the All-Pay Auction game,
where we use Numba
to speed up the loops:

In [59]:

```
from numba import jit
def all_pay_auction(r, e, 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.
e : 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((e+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:

In [60]:

```
N = 2
e = 5 # odd
r = 8
```

In [61]:

```
g_APA_odd = all_pay_auction(r, e, N)
print(g_APA_odd)
```

Clearly, this game has no pure-action Nash equilibrium. Indeed:

In [62]:

```
gt.pure_nash_brute(g_APA_odd)
```

Out[62]:

`e`

is odd
(so that there are an even number of actions for each player):

In [63]:

```
gt.support_enumeration(g_APA_odd)
```

Out[63]:

If `e`

is even, there is a unique equilibrium, which is symmetric and totally mixed.
For example:

In [64]:

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

Out[64]:

`lemke_howson`

implements the Lemke-Howson algorithm (Lemke and Howson 1964),
which returns one Nash equilibrium of a two-player normal form game.
For the details of the algorithm, see, e.g., von Stengel (2007).

Matching Pennies:

In [65]:

```
gt.lemke_howson(g_MP)
```

Out[65]:

Coordination game:

In [66]:

```
gt.lemke_howson(g_Coo)
```

Out[66]:

`init_pivot`

,
which should be an integer $k$ such that $0 \leq k \leq n_1 + n_2 - 1$ (default to `0`

),
where $0, \ldots, n_1-1$ correspond to player 0's actions,
while $n_1 \ldots, n_1+n_2-1$ to player 1's actions.

In [67]:

```
gt.lemke_howson(g_Coo, init_pivot=1)
```

Out[67]:

All-Pay Auction:

In [68]:

```
gt.lemke_howson(g_APA_odd, init_pivot=0)
```

Out[68]:

In [69]:

```
gt.lemke_howson(g_APA_odd, init_pivot=1)
```

Out[69]:

Additional information is returned if the option `full_output`

is set `True`

:

In [70]:

```
NE, res = gt.lemke_howson(g_APA_odd, full_output=True)
res
```

Out[70]:

`lemke_howson`

runs fast,
with a reasonable time amount for games with up to several hundreds actions.
(In fact, this is the only routine among the Nash equilibrium computation routines in the `game_theory`

submodule
that scales to large-size games.)
For example:

In [71]:

```
N = 2
e = 200 # 201 actions
r = 500
g_APA200 = all_pay_auction(r, e, N)
```

In [72]:

```
gt.lemke_howson(g_APA200)
```

Out[72]:

`mclennan_tourky`

computes one approximate Nash equilibrium of an $N$-player normal form game
by the fixed-point algorithm of McLennan and Tourky (2006) applied to the best response correspondence

In [73]:

```
N = 3
r = 16
e = 5
g_APA3 = all_pay_auction(r, e, N)
```

Run `mclennan_tourky`

:

In [74]:

```
NE = gt.mclennan_tourky(g_APA3)
NE
```

Out[74]:

`epsilon`

(default to `1e-3`

).

In [75]:

```
g_APA3.is_nash(NE, tol=1e-3)
```

Out[75]:

In [76]:

```
epsilon = 1e-4
NE = gt.mclennan_tourky(g_APA3, epsilon=epsilon)
NE
```

Out[76]:

In [77]:

```
g_APA3.is_nash(NE, tol=epsilon)
```

Out[77]:

Additional information is returned by setting the `full_output`

option to `True`

:

In [78]:

```
NE, res = gt.mclennan_tourky(g_APA3, full_output=True)
res
```

Out[78]:

For this game, `mclennan_tourky`

returned a symmetric, totally mixed action profile
(cf. Rapoport and Amaldoss 2004)
with the default initial condition `(0, 0, 0)`

(profile of pure actions).

Let's try a different initial condition:

In [79]:

```
init = (
[1/2, 0, 0, 1/2, 0, 0], [0, 1/2, 0, 0, 1/2, 0], [0, 0, 0, 0, 0, 1]
) # profile of mixed actions
gt.mclennan_tourky(g_APA3, init=init)
```

Out[79]:

We obtained an asymetric "alternating" mixed action profile. While this is just an approximate Nash equilibrium, it suggests that there is an (exact) Nash equilibrium of the form $((p_0, 0, p_2, 0, p_4, 0), (p_0, 0, p_2, 0, p_4, 0), (0, q_1, 0, q_3, 0, q_5))$. In fact, a simple calculation shows that there is one such that $$ p_0 = \left(\frac{r-4}{r}\right)^{\frac{1}{2}}, p_0 + p_2 = \left(\frac{r-2}{r}\right)^{\frac{1}{2}}, p_4 = 1 - (p_0 + p_2), $$ and $$ q_1 = \frac{2}{r p_0}, q_1 + q_3 = \frac{4}{r (p_0+p_2)}, q_5 = 1 - (q_1 + q_3). $$

To verify:

In [80]:

```
p0 = ((r-4)/r)**(1/2)
p02 = ((r-2)/r)**(1/2)
p2 = p02 - p0
p4 = 1 - p02
q1 = (2/r)/p0
q13 = (4/r)/(p02)
q3 = q13 - q1
q5 = 1 - q13
a = ([p0, 0, p2, 0, p4, 0], [p0, 0, p2, 0, p4, 0], [0, q1, 0, q3, 0, q5])
a
```

Out[80]:

In [81]:

```
g_APA3.is_nash(a)
```

Out[81]:

E. Dechenaux, D. Kovenock, and V. Lugovskyy (2006), "Caps on bidding in all-pay auctions: Comments on the experiments of A. Rapoport and W. Amaldoss," Journal of Economic Behavior and Organization 61, 276-283.

C. E. Lemke and J. T. Howson (1964), "Equilibrium Points of Bimatrix Games," Journal of the Society for Industrial and Applied Mathematics 12, 413-423.

A. McLennan and R. Tourky (2006), "From Imitation Games to Kakutani."

A. Rapoport and W. Amaldoss (2004), "Mixed-strategy play in single-stage first-price all-pay auctions with symmetric players," Journal of Economic Behavior and Organization 54, 585-607.

B. von Stengel (1997), "New Lower Bounds for the Number of Equilibria in Bimatrix Games."

B. von Stengel (2007), "Equilibrium Computation for Two-Player Games in Strategic and Extensive Form," Chapter 3, N. Nisan, T. Roughgarden, E. Tardos, and V. Vazirani eds., Algorithmic Game Theory.

In [ ]:

```
```