# Tools for Game Theory¶

Daisuke Oyama
Faculty of Economics, University of Tokyo

This notebook demonstrates the functionalities of the Player and NormalFormGame types in QuantEcon/Games.jl.

The first time you run this notebook, you need to install the Games.jl package by removing the "#" below:

In [1]:
# Pkg.clone("https://github.com/QuantEcon/Games.jl")

In [2]:
using Games
using Compat  # For compatibility for Julia v0.4


## Normal Form Games¶

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

• $I = \{1, \ldots, N\}$ is the set of players,
• $A_i = \{1, \ldots, n_i\}$ 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 $1$-st argument of the payoff function $u_i$ is player $i$'s own action and the $j$-th argument, $j = 2, \ldots, N$, is player ($i+j-1$)'s action (modulo $N$).

In our package, a normal form game and a player are represented by the types 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.

### Creating a NormalFormGame¶

There are several ways to create a NormalFormGame instance.

The first is to pass an array of payoffs for all the players, i.e., an $(N+1)$-dimenstional array of shape $(n_1, \ldots, n_N, N)$ whose $(a_1, \ldots, a_N)$-entry contains an array of the $N$ payoff values for the action profile $(a_1, \ldots, a_N)$.

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

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

In [3]:
matching_pennies_bimatrix = Array(Float64, 2, 2, 2)
matching_pennies_bimatrix[1, 1, :] = [1, -1]  # payoff profile for action profile (1, 1)
matching_pennies_bimatrix[1, 2, :] = [-1, 1]
matching_pennies_bimatrix[2, 1, :] = [-1, 1]
matching_pennies_bimatrix[2, 2, :] = [1, -1]
g_MP = NormalFormGame(matching_pennies_bimatrix)

Out[3]:
2×2 NormalFormGame{2,Float64}
In [4]:
g_MP.players[1]  # Player instance for player 1

Out[4]:
2×2 Player{2,Float64}:
[1.0 -1.0; -1.0 1.0]
In [5]:
g_MP.players[2]  # Player instance for player 2

Out[5]:
2×2 Player{2,Float64}:
[-1.0 1.0; 1.0 -1.0]
In [6]:
g_MP.players[1].payoff_array  # Player 1's payoff array

Out[6]:
2×2 Array{Float64,2}:
1.0  -1.0
-1.0   1.0
In [7]:
g_MP.players[2].payoff_array  # Player 2's payoff array

Out[7]:
2×2 Array{Float64,2}:
-1.0   1.0
1.0  -1.0
In [8]:
g_MP[1, 1]  # payoff profile for action profile (1, 1)

Out[8]:
2-element Array{Float64,1}:
1.0
-1.0

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 = NormalFormGame(coordination_game_matrix)

Out[9]:
2×2 NormalFormGame{2,Int64}
In [10]:
g_Coo.players[1].payoff_array  # Player 1's payoff array

Out[10]:
2×2 Array{Int64,2}:
4  0
3  2
In [11]:
g_Coo.players[2].payoff_array  # Player 2's payoff array

Out[11]:
2×2 Array{Int64,2}:
4  0
3  2

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 [12]:
RPS_matrix = [0 -1 1;
1 0 -1;
-1 1 0]
g_RPS = NormalFormGame(RPS_matrix)

Out[12]:
3×3 NormalFormGame{2,Int64}

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 [13]:
g_PD = NormalFormGame((2, 2))  # There are 2 players, each of whom has 2 actions
g_PD[1, 1] = [1, 1]
g_PD[1, 2] = [-2, 3]
g_PD[2, 1] = [3, -2]
g_PD[2, 2] = [0, 0];

In [14]:
g_PD

Out[14]:
2×2 NormalFormGame{2,Float64}
In [15]:
g_PD.players[1].payoff_array

Out[15]:
2×2 Array{Float64,2}:
1.0  -2.0
3.0   0.0

Finally, a NormalFormGame instance can be constructed by giving an array of Player instances, as explained in the next section.

### Creating a 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 [16]:
player1 = Player([3 1; 0 2])
player2 = Player([2 0; 1 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.

In [17]:
player1.payoff_array

Out[17]:
2×2 Array{Int64,2}:
3  1
0  2
In [18]:
player2.payoff_array

Out[18]:
2×2 Array{Int64,2}:
2  0
1  3

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

In [19]:
g_BoS = NormalFormGame((player1, player2))

Out[19]:
2×2 NormalFormGame{2,Int64}

### More than two players¶

Games with more than two players are also supported.

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_1 + \cdots + q_N$ 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 [20]:
immutable Cournot{N} end

@compat function (::Type{Cournot{N}}){N,T<:Real}(a::Real, c::Real, q_grid::Vector{T})
nums_actions = tuple([length(q_grid) for i in 1:N]...)::NTuple{N,Int}
S = promote_type(typeof(a), typeof(c), T)
payoff_array= Array{T}(nums_actions)
for I in CartesianRange(nums_actions)
Q = zero(S)
for i in 1:N
Q += q_grid[I[i]]::T
end
payoff_array[I] = (a - c - Q) * q_grid[I[1]]
end
players = tuple([Player(payoff_array) for i in 1:N]...)::NTuple{N,Player{N,T}}
return NormalFormGame(players)
end

cournot{T<:Real}(a::Real, c::Real, N::Integer, q_grid::Vector{T}) =
Cournot{N}(a, c, q_grid)

Out[20]:
cournot (generic function with 1 method)

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

In [21]:
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)

Out[21]:
2×2×2 NormalFormGame{3,Int64}
In [22]:
print(g_Cou.players[1])

2×2×2 Player{3,Int64}:
[300 250; 375 300]

[250 200; 300 225]
In [23]:
g_Cou.nums_actions

Out[23]:
(2,2,2)

## Nash Equilibrium¶

A 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 methods best_response and best_responses.

Consider the Matching Pennies game g_MP defined above. For example, player 1's best response to the opponent's action 2 is:

In [24]:
best_response(g_MP.players[1], 2)

Out[24]:
2

Player 1's best responses to the opponent's mixed action [0.5, 0.5] (we know they are 1 and 2):

In [25]:
# By default, returns the best response action with the smallest index
best_response(g_MP.players[1], [0.5, 0.5])

Out[25]:
1
In [26]:
# With tie_breaking='random', returns randomly one of the best responses
best_response(g_MP.players[1], [0.5, 0.5], tie_breaking="random")  # Try several times

Out[26]:
1

best_responses returns an array of all the best responses:

In [27]:
best_responses(g_MP.players[1], [0.5, 0.5])

Out[27]:
2-element Array{Int64,1}:
1
2

For this game, we know that ([0.5, 0.5], [0.5, 0.5]) is a (unique) Nash equilibrium.

In [28]:
is_nash(g_MP, ([0.5, 0.5], [0.5, 0.5]))

Out[28]:
true
In [29]:
is_nash(g_MP, (1, 1))

Out[29]:
false
In [30]:
is_nash(g_MP, ([1., 0.], [0.5, 0.5]))

Out[30]:
false

### Finding Nash equilibria¶

Our package does not have sophisticated algorithms to compute Nash equilibria (yet)... One might look at Gambit, which implements several such algorithms.

#### Brute force¶

For small games, we can find pure action Nash equilibria by brute force, by calling the method pure_nash.

In [31]:
function print_pure_nash_brute(g::NormalFormGame)
NEs = pure_nash(g)
num_NEs = length(NEs)
if num_NEs == 0
msg = "no pure Nash equilibrium"
elseif num_NEs == 1
msg = "1 pure Nash equilibrium:\n$(NEs[1])" else msg = "$num_NEs pure Nash equilibria:\n"
for (i, NE) in enumerate(NEs)
i < num_NEs ? msg *= "$NE," : msg *= "$NE"
end
end
println(join(["The game has ", msg]))
end

Out[31]:
print_pure_nash_brute (generic function with 1 method)

Matching Pennies:

In [32]:
print_pure_nash_brute(g_MP)

The game has no pure Nash equilibrium


Coordination game:

In [33]:
print_pure_nash_brute(g_Coo)

The game has 2 pure Nash equilibria:
(1,1),(2,2)


Rock-Paper-Scissors:

In [34]:
print_pure_nash_brute(g_RPS)

The game has no pure Nash equilibrium


Battle of the Sexes:

In [35]:
print_pure_nash_brute(g_BoS)

The game has 2 pure Nash equilibria:
(1,1),(2,2)


Prisoners' Dillema:

In [36]:
print_pure_nash_brute(g_PD)

The game has 1 pure Nash equilibrium:
(2,2)


Cournot game:

In [37]:
print_pure_nash_brute(g_Cou)

The game has 1 pure Nash equilibrium:
(2,2,2)


#### Sequential best response¶

In some games, such as "supermodular games" and "potential games", the process of sequential best responses converges to a Nash equilibrium.

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

In [38]:
function sequential_best_response(g::NormalFormGame;
init_actions::Union{Vector{Int},Void}=nothing,
tie_breaking="smallest",
verbose=true)
N = num_players(g)
a = Array{Int}(N)
if init_actions == nothing
init_actions = ones(Int, N)
end
copy!(a, init_actions)
if verbose
println("init_actions: $a") end new_a = Array{Int}(N) max_iter = prod(g.nums_actions) for t in 1:max_iter copy!(new_a, a) for (i, player) in enumerate(g.players) if N == 2 a_except_i = new_a[3-i] else a_except_i = (new_a[i+1:N]..., new_a[1:i-1]...) end new_a[i] = best_response(player, a_except_i, tie_breaking=tie_breaking) if verbose println("player$i: $new_a") end end if new_a == a return a else copy!(a, new_a) end end println("No pure Nash equilibrium found") return a end  Out[38]: sequential_best_response (generic function with 1 method) 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 [39]: a, c = 80, 20 N = 3 q_grid = collect(linspace(0, a-c, 13)) # [0, 5, 10, ..., 60] g_Cou = cournot(a, c, N, q_grid)  Out[39]: 13×13×13 NormalFormGame{3,Float64} In [40]: a_star = sequential_best_response(g_Cou) # By default, start with (1, 1, 1) println("Nash equilibrium indices:$a_star")
println("Nash equilibrium quantities: \$(q_grid[a_star])")

init_actions: [1,1,1]
player 1: [7,1,1]
player 2: [7,4,1]
player 3: [7,4,2]
player 1: [5,4,2]
player 2: [5,4,2]
player 3: [5,4,3]
player 1: [4,4,3]
player 2: [4,4,3]
player 3: [4,4,4]
player 1: [4,4,4]
player 2: [4,4,4]
player 3: [4,4,4]
Nash equilibrium indices: [4,4,4]
Nash equilibrium quantities: [15.0,15.0,15.0]

In [41]:
# Start with the largest actions (13, 13, 13)
sequential_best_response(g_Cou, init_actions=[13, 13, 13])

init_actions: [13,13,13]
player 1: [1,13,13]
player 2: [1,1,13]
player 3: [1,1,7]
player 1: [4,1,7]
player 2: [4,2,7]
player 3: [4,2,5]
player 1: [4,2,5]
player 2: [4,3,5]
player 3: [4,3,4]
player 1: [4,3,4]
player 2: [4,4,4]
player 3: [4,4,4]
player 1: [4,4,4]
player 2: [4,4,4]
player 3: [4,4,4]

Out[41]:
3-element Array{Int64,1}:
4
4
4

The limit action profile is indeed a Nash equilibrium:

In [42]:
is_nash(g_Cou, tuple(a_star...))

Out[42]:
true

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

In [43]:
print_pure_nash_brute(g_Cou)

The game has 7 pure Nash equilibria:
(5,4,3),(4,5,3),(5,3,4),(4,4,4),(3,5,4),(4,3,5),(3,4,5)


Make it bigger:

In [44]:
N = 4
q_grid = collect(linspace(0, a-c, 61))  # [0, 1, 2, ..., 60]
g_Cou = cournot(a, c, N, q_grid)

Out[44]:
61×61×61×61 NormalFormGame{4,Float64}
In [45]:
sequential_best_response(g_Cou)

init_actions: [1,1,1,1]
player 1: [31,1,1,1]
player 2: [31,16,1,1]
player 3: [31,16,8,1]
player 4: [31,16,8,5]
player 1: [18,16,8,5]
player 2: [18,17,8,5]
player 3: [18,17,12,5]
player 4: [18,17,12,9]
player 1: [13,17,12,9]
player 2: [13,15,12,9]
player 3: [13,15,14,9]
player 4: [13,15,14,11]
player 1: [12,15,14,11]
player 2: [12,14,14,11]
player 3: [12,14,14,11]
player 4: [12,14,14,12]
player 1: [12,14,14,12]
player 2: [12,13,14,12]
player 3: [12,13,14,12]
player 4: [12,13,14,13]
player 1: [12,13,14,13]
player 2: [12,13,14,13]
player 3: [12,13,13,13]
player 4: [12,13,13,13]
player 1: [13,13,13,13]
player 2: [13,13,13,13]
player 3: [13,13,13,13]
player 4: [13,13,13,13]
player 1: [13,13,13,13]
player 2: [13,13,13,13]
player 3: [13,13,13,13]
player 4: [13,13,13,13]

Out[45]:
4-element Array{Int64,1}:
13
13
13
13
In [46]:
sequential_best_response(g_Cou, init_actions=[1, 1, 1, 31])

init_actions: [1,1,1,31]
player 1: [16,1,1,31]
player 2: [16,8,1,31]
player 3: [16,8,5,31]
player 4: [16,8,5,18]
player 1: [17,8,5,18]
player 2: [17,12,5,18]
player 3: [17,12,9,18]
player 4: [17,12,9,13]
player 1: [15,12,9,13]
player 2: [15,14,9,13]
player 3: [15,14,11,13]
player 4: [15,14,11,12]
player 1: [14,14,11,12]
player 2: [14,14,11,12]
player 3: [14,14,12,12]
player 4: [14,14,12,12]
player 1: [13,14,12,12]
player 2: [13,14,12,12]
player 3: [13,14,13,12]
player 4: [13,14,13,12]
player 1: [13,14,13,12]
player 2: [13,13,13,12]
player 3: [13,13,13,12]
player 4: [13,13,13,13]
player 1: [13,13,13,13]
player 2: [13,13,13,13]
player 3: [13,13,13,13]
player 4: [13,13,13,13]

Out[46]:
4-element Array{Int64,1}:
13
13
13
13

Sequential best response does not converge in all games:

In [47]:
print(g_MP)  # Matching Pennies

2×2 NormalFormGame{2,Float64}
In [48]:
sequential_best_response(g_MP)

init_actions: [1,1]
player 1: [1,1]
player 2: [1,2]
player 1: [2,2]
player 2: [2,1]
player 1: [1,1]
player 2: [1,2]
player 1: [2,2]
player 2: [2,1]
No pure Nash equilibrium found

Out[48]:
2-element Array{Int64,1}:
2
1
In [ ]: