Author: Yuya Furusawa
Graduate School of Economics, University of Tokyo
This note demonstrates the best response dynamics model and its related models with brd.jl
Julia library.
using GameTheory
using Plots
plotly()
Plots.PlotlyBackend()
Best response dynamics is one of the strategy updating methods. At each round, the set of players is chosen, and they take best responses given other players' current strategy. Players who take best response only consider the next round payoff, that is they don't consider the future payoffs. From this feature, best response dynamics, is called myopic best response.
In the potential game, you can find a Nash equilibrium by best response dynamics.
Kandori-Mailath-Rob model(KMR model) is an evolutional model, similar to best response dynamics model. In KMR model, agents do not always take a strategy which delivers highest payoff, they sometimes take another strategy. Unlike best response dynamics, in KMR model, the system is not deterministic evolution. Startegy flips can occur in every period.
KMR model gives a risk-dominance equilibrium as stationary equilibrium. In contrast, best response dynamics does not always give a risk-dominance equilibrium. (We see these contrast later.)
KMR model is sometimes criticised by the absense of the foundation of strategy flips. To overcome this point, logit response dynamics model incorporates decision theoretic foundation of strategy chooice (See this note).
Sampling best response dynamics model is also evolutional model. In this model, agents who get a chance to revise an action observe the randomly sampled opponents' actions, and then take a best resoponse. If $k$ sample observed, we call $k$-sampling best response dynamics.
Under some conditions, this dynamics gives p-dominant equilibrium as stationary equilibirum (To refer the p-dominant equilibrium, see Morris, Rob and Shin(1995)).
brd.jl
usage¶# payoff matrix
payoff = [4 0;
3 2]
# the number of players
N = 4
4
To create BRD
instance, you need payoff matrix and the number of players.
# Best response dynamics
brd = BRD(payoff, N)
BRD{Int64}(4, 2×2 Player{2, Int64}: 4 0 3 2, 2)
You need additionally specify epsilon, the probability of strategy flips, and k, sample size, to create KMR
and SamplingBRD
instances respectively.
If not provided, these are set to epsilon=0.1
and k=2
by default.
# KMR model
epsilon = 0.1
kmr = KMR(payoff, N, epsilon)
# Sampling best response model
k = 2
sbrd = SamplingBRD(payoff, N, k)
SamplingBRD{Int64}(4, 2×2 Player{2, Int64}: 4 0 3 2, 2, 2)
play
method¶play
method proceeds the game by one step.
play
method requires init_action_dist
, which is the current action distribution(in other words "frquency", not probability distribution) where first element indicates the number of players who takes action 0.
init_action_dist = [2, 2]
play(brd, init_action_dist)
2-element Vector{Int64}: 3 1
You can use play
method similarly in KMR model and sampling best response dynamics model.
time_series
method¶time_series
method returns a time series of action distributions(frequencies).
You have to specify the length of time series.
In addition, you can choose initial action distribution from which the dynamics proceeds.
If not specified, it is randomly chosen.
ts_length = 5
init_action_dist = [2, 2]
time_series(brd, ts_length, init_action_dist)
2×5 Matrix{Int64}: 2 1 1 1 1 2 3 3 3 3
You can use time_series
method similarly in KMR model and sampling best response dynamics model.
We illustrate the dynamics of players' actions with coordination game and Young's game.
Coordination game is defined as follows:
1$\backslash$2 | $A$ | $B$ |
---|---|---|
$A$ | 2, 2 | 0, 0 |
$B$ | 0, 0 | 1, 1 |
coordination_game_matrix = [2 0; 0 1]
2×2 Matrix{Int64}: 2 0 0 1
Young's game is defined as follows:
1$\backslash$2 | $A$ | $B$ | $C$ |
---|---|---|---|
$A$ | 6, 6 | 0, 0 | 0, 0 |
$B$ | 5, 5 | 7, 7 | 5, 5 |
$C$ | 0, 0 | 5, 5 | 8, 8 |
young_game_matrix = [6 0 0; 5 7 5; 0 5 8]
3×3 Matrix{Int64}: 6 0 0 5 7 5 0 5 8
The number of agents is set to 10 and the length of time series is 200.
N = 10
ts_length = 200
200
label_2 = ["Action A" "Action B"]
label_3 = ["Action A" "Action B" "Action C"]
1×3 Matrix{String}: "Action A" "Action B" "Action C"
In the graphs below, vertical axis represents the number of players who take each actions, and holizontal axis represents the periods.
In evolutionary game theory, best response dynamics represents a class of strategy updating rules, where each player's strategy in the next round is determined by their best response to subset of population.
brd_coor = BRD(coordination_game_matrix, N);
m = 2
x = time_series(brd_coor, ts_length, [m, N-m])
plot([x[1, :], x[2, :]], label=label_2)
m = 8
x = time_series(brd_coor, ts_length, [m, N-m])
plot([x[1, :], x[2, :]], label=label_2)
You can see converged action profile depends on the initial action distribution.
epsilon = 0.1;
kmr_coor = KMR(coordination_game_matrix, N, epsilon)
KMR{Int64}(10, 2×2 Player{2, Int64}: 2 0 0 1, 2, 0.1)
m = 2
x = time_series(kmr_coor, ts_length, [m, N-m])
plot([x[1, :], x[2, :]], label=label_2)
This graph shows (A,A) is the long-run equilibrium which is a risk-dominance equilibrium (if not, pick larger ts_length
).
To compare the results from best response dynamics see the above, (A,A) becomes stationary equilibrium even if the number of player who initially takes action A is small.
kmr_young = KMR(young_game_matrix, N, epsilon)
KMR{Int64}(10, 3×3 Player{2, Int64}: 6 0 0 5 7 5 0 5 8, 3, 0.1)
m = 2
x = time_series(kmr_young, ts_length, [N-2*m, m, m])
plot([x[1, :], x[2, :], x[3, :]], label=label_3)
k = 2;
sbrd_coor = SamplingBRD(coordination_game_matrix, N, k)
SamplingBRD{Int64}(10, 2×2 Player{2, Int64}: 2 0 0 1, 2, 2)
m = 2
x = time_series(sbrd_coor, ts_length, [m, N-m])
plot([x[1, :], x[2, :]], label=label_2)
sbrd_young = SamplingBRD(young_game_matrix, N, k)
SamplingBRD{Int64}(10, 3×3 Player{2, Int64}: 6 0 0 5 7 5 0 5 8, 3, 2)
m = 2
x = time_series(sbrd_young, ts_length, [N-2*m, m, m])
plot([x[1, :], x[2, :], x[3, :]], label=label_3)