QuantEcon/Games.jl のケース
$N$ 人標準形ゲーム ($N$-player normal form game) は
で構成される.
(利得関数 $u_i$ の第1引数はつねに $a_i$ とする.)
プレイヤー $i$ の利得関数は $n_i \times \cdots \times n_{i+N-1}$ の $N$ 次元配列で表現できる.
例:
$ \begin{bmatrix} 3, 2 & 1, 1 \\ 0, 0 & 2, 3 \end{bmatrix} $
In [1]:
type Player{N,T<:Real}
payoff_array::Array{T,N}
end
インデックスが (自分の行動, 相手の行動) となるように値を並べることに注意.
In [2]:
payoff_array1 = [3 1;
0 2]
Out[2]:
In [3]:
player1 = Player(payoff_array1)
Out[3]:
In [4]:
payoff_array2 = [2 0;
1 3]
Out[4]:
In [5]:
player2 = Player(payoff_array2)
Out[5]:
自身の行動の数を返すメソッドを定義しておく.
In [6]:
num_actions(p::Player) = size(p.payoff_array)[1]
# num_actions(p::Player) = size(p.payoff_array, 1) ???
Out[6]:
In [7]:
type NormalFormGame{N,T<:Real}
players::NTuple{N,Player{N,T}}
nums_actions::NTuple{N,Int}
end
In [8]:
function NormalFormGame{N,T}(players::NTuple{N,Player{N,T}})
# Check that the shapes of the payoff arrays are consistent
# ...
nums_actions::NTuple{N,Int} =
tuple([num_actions(player) for player in players]...)
return NormalFormGame{N,T}(players, nums_actions)
end;
In [9]:
g = NormalFormGame((player1, player2))
Out[9]:
Games.jl
では他にもいくつかコンストラクタを用意している.
課題:
利得表をプリントするメソッドがほしい.
(Issue #7)
In [10]:
typealias PureAction Integer
typealias MixedAction{T<:Real} Vector{T}
typealias Action{T<:Real} Union{PureAction,MixedAction{T}};
In [11]:
function payoff_vector(player::Player{2}, opponent_action::PureAction)
return player.payoff_array[:, opponent_action]
end;
In [12]:
function payoff_vector(player::Player{2}, opponent_action::MixedAction)
return player.payoff_array * opponent_action
end;
In [13]:
player1.payoff_array
Out[13]:
In [14]:
payoff_vector(player1, 1)
Out[14]:
In [15]:
payoff_vector(player1, [0.5, 0.5])
Out[15]:
In [16]:
function is_best_response(player::Player{2},
own_action::PureAction,
opponent_action::Action;
tol::Float64=1e-8)
payoffs = payoff_vector(player, opponent_action)
payoff_max = maximum(payoffs)
return payoffs[own_action] >= payoff_max - tol
end;
In [17]:
function is_best_response(player::Player{2},
own_action::MixedAction,
opponent_action::Action;
tol::Float64=1e-8)
payoffs = payoff_vector(player, opponent_action)
payoff_max = maximum(payoffs)
return dot(own_action, payoffs) >= payoff_max - tol
end;
In [18]:
is_best_response(player1, 1, 1)
Out[18]:
In [19]:
is_best_response(player1, 1, [0.5, 0.5])
Out[19]:
In [20]:
is_best_response(player1, [0.5, 0.5], [0.5, 0.5])
Out[20]:
In [21]:
is_best_response(player1, [0.5, 0.5], 1)
Out[21]:
In [22]:
is_best_response(player1, 1, [0.25, 0.75])
Out[22]:
In [23]:
is_best_response(player1, 2, [0.25, 0.75])
Out[23]:
(1, 1)
は Nash 均衡である:
In [24]:
is_best_response(g.players[1], 1, 1) && is_best_response(g.players[2], 1, 1)
Out[24]:
(1, 2)
は Nash 均衡ではない:
In [25]:
is_best_response(g.players[1], 1, 2) && is_best_response(g.players[2], 2, 1)
Out[25]:
([0.75, 0.25], [0.25, 0.75])
は Nash 均衡である:
In [26]:
is_best_response(g.players[1], [0.75, 0.25], [0.25, 0.75]) &&
is_best_response(g.players[2], [0.25, 0.75], [0.75, 0.25])
Out[26]:
ActionProfile
を定義しておく:
In [27]:
typealias ActionProfile{T<:Real,N} NTuple{N,Action{T}};
In [28]:
function is_nash(g::NormalFormGame{2}, action_profile::ActionProfile)
for (i, player) in enumerate(g.players)
own_action, opponent_action =
action_profile[i], action_profile[3-i]
if !(is_best_response(player, own_action, opponent_action))
return false
end
end
return true
end;
In [29]:
is_nash(g, (1, 1))
Out[29]:
In [30]:
is_nash(g, (1, 2))
Out[30]:
In [31]:
is_nash(g, ([0.75, 0.25], [0.25, 0.75]))
Out[31]:
例 ($N = 3$):
プレイヤーの集合 $\{1, 2, 3\}$
行動空間 (共通) $\{1, 2\}$
利得関数 (共通)
$ u_i(a) = \begin{cases} 1 & \text{if $a = (1, 1, 1)$} \\ 2 & \text{if $a = (2, 2, 2)$} \\ 0 & \text{otherwise} \end{cases} $
In [32]:
payoff_array = zeros(2, 2, 2)
for i in 1:2
payoff_array[i, i, i] = i
end
payoff_array
Out[32]:
In [33]:
g3 = NormalFormGame(tuple([Player(payoff_array) for i in 1:3]...))
Out[33]:
$(a_2, a_3)$ に対するプレイヤー1の利得ベクトルは?
$\rightarrow$ $a_3$ を固定するとプレイヤー1とプレイヤー2の2人ゲームと見なすことができる.
In [34]:
function _reduce_last_player(payoff_array::Array, action::PureAction)
shape = size(payoff_array)
A = reshape(payoff_array, (prod(shape[1:end-1]), shape[end]))
out = A[:, action]
return reshape(out, shape[1:end-1])
end;
In [35]:
function _reduce_last_player(payoff_array::Array, action::MixedAction)
shape = size(payoff_array)
A = reshape(payoff_array, (prod(shape[1:end-1]), shape[end]))
out = A * action
return reshape(out, shape[1:end-1])
end;
In [36]:
_reduce_last_player(payoff_array, 1)
Out[36]:
In [37]:
_reduce_last_player(payoff_array, [0.5, 0.5])
Out[37]:
_reduce_last_player
を再帰的に使う:
In [38]:
num_opponents{N}(::Player{N}) = N - 1
function payoff_vector(player::Player, opponents_actions::ActionProfile)
payoffs = player.payoff_array
for i in num_opponents(player):-1:1
payoffs = _reduce_last_player(payoffs, opponents_actions[i])
end
return payoffs
end
Out[38]:
In [39]:
payoff_vector(g3.players[1], (1, 1))
Out[39]:
In [40]:
payoff_vector(g3.players[1], ([0.5, 0.5], [0.5, 0.5]))
Out[40]:
In [41]:
function is_best_response(player::Player,
own_action::PureAction,
opponents_actions::ActionProfile;
tol::Float64=1e-8)
payoffs = payoff_vector(player, opponents_actions)
payoff_max = maximum(payoffs)
return payoffs[own_action] >= payoff_max - tol
end
function is_best_response(player::Player,
own_action::MixedAction,
opponents_actions::ActionProfile;
tol::Float64=1e-8)
payoffs = payoff_vector(player, opponents_actions)
payoff_max = maximum(payoffs)
return dot(own_action, payoffs) >= payoff_max - tol
end;
In [42]:
is_best_response(g3.players[1], 1, (1, 1))
Out[42]:
In [43]:
is_best_response(g3.players[1], [0.5, 0.5], (1, [0.3, 0.7]))
Out[43]:
In [44]:
function is_nash(g::NormalFormGame, action_profile::ActionProfile)
for (i, player) in enumerate(g.players)
own_action = action_profile[i]
opponents_actions =
tuple(action_profile[i+1:end]..., action_profile[1:i-1]...)
if !(is_best_response(player, own_action, opponents_actions))
return false
end
end
return true
end;
In [45]:
is_nash(g3, (1, 1, 1))
Out[45]:
In [46]:
is_nash(g3, (2, 2, 2))
Out[46]:
In [47]:
p = 2 - sqrt(2)
is_nash(g3, ([p, 1-p], [p, 1-p], [p, 1-p]))
Out[47]:
_reduce_last_player
で type inference がうまくいってない.
(Issue #2)
In [48]:
@code_warntype _reduce_last_player(payoff_array, 1)
再掲:
In [49]:
function func{T<:Real,N}(a::Array{T,N}, x::Vector{Float64})
shape = size(a)
shape_reduced = shape[1:end-1]
b = reshape(a, (prod(shape_reduced), shape[end]))
out = b * x
return reshape(out, shape_reduced)
end;
In [50]:
a = ones(1, 2, 3, 4)
size(a)
Out[50]:
In [51]:
x = ones(size(a)[end])
Out[51]:
In [52]:
func(a, x)
Out[52]:
In [53]:
@code_warntype func(a, x)
@generated
というのを使うと (だいたい) うまくいく:
In [54]:
@generated function func_g{T<:Real,N}(a::Array{T,N}, x::Vector{Float64})
return quote
$(M = N - 1)
shape = size(a)
shape_reduced = shape[1:end-1]::NTuple{$M,Int}
b = reshape(a, (prod(shape_reduced), shape[end]))
out = b * x
return reshape(out, shape_reduced)
end
end
Out[54]:
In [55]:
func_g(a, x)
Out[55]:
In [56]:
@code_warntype func_g(a, x)
こういう難しいのを使わない "普通の" 書き方でうまい方法はないものでしょうか. (julia-wakalang Issue #18)
In [ ]: