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:
# Pkg.clone("https://github.com/QuantEcon/Games.jl")
using Games
using Compat # For compatibility for Julia v0.4
An $N$-player normal form game is a triplet $g = (I, (A_i)_{i \in I}, (u_i)_{i \in I})$ where
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.
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} $
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)
2×2 NormalFormGame{2,Float64}
g_MP.players[1] # Player instance for player 1
2×2 Player{2,Float64}: [1.0 -1.0; -1.0 1.0]
g_MP.players[2] # Player instance for player 2
2×2 Player{2,Float64}: [-1.0 1.0; 1.0 -1.0]
g_MP.players[1].payoff_array # Player 1's payoff array
2×2 Array{Float64,2}: 1.0 -1.0 -1.0 1.0
g_MP.players[2].payoff_array # Player 2's payoff array
2×2 Array{Float64,2}: -1.0 1.0 1.0 -1.0
g_MP[1, 1] # payoff profile for action profile (1, 1)
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} $
coordination_game_matrix = [4 0;
3 2] # square matrix
g_Coo = NormalFormGame(coordination_game_matrix)
2×2 NormalFormGame{2,Int64}
g_Coo.players[1].payoff_array # Player 1's payoff array
2×2 Array{Int64,2}: 4 0 3 2
g_Coo.players[2].payoff_array # Player 2's payoff array
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} $
RPS_matrix = [0 -1 1;
1 0 -1;
-1 1 0]
g_RPS = NormalFormGame(RPS_matrix)
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} $
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];
g_PD
2×2 NormalFormGame{2,Float64}
g_PD.players[1].payoff_array
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.
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} $
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.
player1.payoff_array
2×2 Array{Int64,2}: 3 1 0 2
player2.payoff_array
2×2 Array{Int64,2}: 2 0 1 3
Passing an array of Player instances is the third way to create a NormalFormGame
instance:
g_BoS = NormalFormGame((player1, player2))
2×2 NormalFormGame{2,Int64}
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
.
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)
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$.
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)
2×2×2 NormalFormGame{3,Int64}
print(g_Cou.players[1])
2×2×2 Player{3,Int64}: [300 250; 375 300] [250 200; 300 225]
g_Cou.nums_actions
(2,2,2)
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:
best_response(g_MP.players[1], 2)
2
Player 1's best responses to the opponent's mixed action [0.5, 0.5]
(we know they are 1 and 2):
# By default, returns the best response action with the smallest index
best_response(g_MP.players[1], [0.5, 0.5])
1
# 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
1
best_responses
returns an array of all the best responses:
best_responses(g_MP.players[1], [0.5, 0.5])
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.
is_nash(g_MP, ([0.5, 0.5], [0.5, 0.5]))
true
is_nash(g_MP, (1, 1))
false
is_nash(g_MP, ([1., 0.], [0.5, 0.5]))
false
Our package does not have sophisticated algorithms to compute Nash equilibria (yet)... One might look at Gambit, which implements several such algorithms.
For small games, we can find pure action Nash equilibria by brute force,
by calling the method pure_nash
.
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
print_pure_nash_brute (generic function with 1 method)
Matching Pennies:
print_pure_nash_brute(g_MP)
The game has no pure Nash equilibrium
Coordination game:
print_pure_nash_brute(g_Coo)
The game has 2 pure Nash equilibria: (1,1),(2,2)
Rock-Paper-Scissors:
print_pure_nash_brute(g_RPS)
The game has no pure Nash equilibrium
Battle of the Sexes:
print_pure_nash_brute(g_BoS)
The game has 2 pure Nash equilibria: (1,1),(2,2)
Prisoners' Dillema:
print_pure_nash_brute(g_PD)
The game has 1 pure Nash equilibrium: (2,2)
Cournot game:
print_pure_nash_brute(g_Cou)
The game has 1 pure Nash equilibrium: (2,2,2)
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.
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
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:
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)
13×13×13 NormalFormGame{3,Float64}
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]
# 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]
3-element Array{Int64,1}: 4 4 4
The limit action profile is indeed a Nash equilibrium:
is_nash(g_Cou, tuple(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: (5,4,3),(4,5,3),(5,3,4),(4,4,4),(3,5,4),(4,3,5),(3,4,5)
Make it bigger:
N = 4
q_grid = collect(linspace(0, a-c, 61)) # [0, 1, 2, ..., 60]
g_Cou = cournot(a, c, N, q_grid)
61×61×61×61 NormalFormGame{4,Float64}
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]
4-element Array{Int64,1}: 13 13 13 13
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]
4-element Array{Int64,1}: 13 13 13 13
Sequential best response does not converge in all games:
print(g_MP) # Matching Pennies
2×2 NormalFormGame{2,Float64}
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
2-element Array{Int64,1}: 2 1