ゲーム理論概念の Julia での表現

QuantEcon/Games.jl のケース

$N$ 人標準形ゲーム ($N$-player normal form game) は

  • プレイヤーの集合 $\{1, \ldots, N\}$
  • 各プレイヤー $i$ の行動集合 $\{1, \ldots, n_i\}$
  • 各プレイヤー $i$ の利得関数 $u_i(a_i, \ldots, a_{i+N-1})$

で構成される.

(利得関数 $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} $

Julia での表現

プレイヤーとゲームのどちらをより基本にすべきか
$\rightarrow$ プレイヤーを基本とすることにする.

Player type

人は社会から独立には存在し得ない.

プレイヤーは payoff_array::Array{T,N} で表現する.

  • N: 社会 (ゲーム) の構成人数

In [1]:
type Player{N,T<:Real}
    payoff_array::Array{T,N}
end

インデックスが (自分の行動, 相手の行動) となるように値を並べることに注意.


In [2]:
payoff_array1 = [3 1;
                 0 2]


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

In [3]:
player1 = Player(payoff_array1)


Out[3]:
Player{2,Int64}(2x2 Array{Int64,2}:
 3  1
 0  2)

In [4]:
payoff_array2 = [2 0;
                 1 3]


Out[4]:
2x2 Array{Int64,2}:
 2  0
 1  3

In [5]:
player2 = Player(payoff_array2)


Out[5]:
Player{2,Int64}(2x2 Array{Int64,2}:
 2  0
 1  3)

自身の行動の数を返すメソッドを定義しておく.


In [6]:
num_actions(p::Player) = size(p.payoff_array)[1]
# num_actions(p::Player) = size(p.payoff_array, 1) ???


Out[6]:
num_actions (generic function with 1 method)

NormalFormGame type

NormalFormGame タイプは Player インスタンスを $N$ 個集めたもの.

  • Player たちの payoff_arrayeltype は共通でないといけないことにする.

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]:
NormalFormGame{2,Int64}((Player{2,Int64}(2x2 Array{Int64,2}:
 3  1
 0  2),Player{2,Int64}(2x2 Array{Int64,2}:
 2  0
 1  3)),(2,2))

Games.jl では他にもいくつかコンストラクタを用意している.

課題:
利得表をプリントするメソッドがほしい. (Issue #7)

純粋行動 (pure action) と混合行動 (mixed action)

以下,

  • 行動空間 $\{1, \ldots, n_i\}$ の要素を純粋行動
  • 行動空間上の確率分布 ($n_i$ 次元ベクトル) を混合行動

と呼び,純粋行動と混合行動を併せて行動と呼ぶ.


In [10]:
typealias PureAction Integer
typealias MixedAction{T<:Real} Vector{T}
typealias Action{T<:Real} Union{PureAction,MixedAction{T}};

is_nash を作る

NormalFormGame インスタンスにおいて,与えられた行動の組 $(a_1, a_2)$ が Nash 均衡かどうかを判定するメソッドを実装したい.

  • 各プレイヤー $i$ について,$a_i$ が $a_j$ ($j \neq i$) に対する最適反応 (best response) であるかどうかを判定する $\cdots$ is_best_response
  • 各プレイヤー $i$ について,相手の $a_j$ に対する,自分の行動ごとの利得のベクトルを計算する $\cdots$ payoff_vector

とりあえず,2-player のケースを考える.

payoff_vector


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]:
2x2 Array{Int64,2}:
 3  1
 0  2

In [14]:
payoff_vector(player1, 1)


Out[14]:
2-element Array{Int64,1}:
 3
 0

In [15]:
payoff_vector(player1, [0.5, 0.5])


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

is_best_response


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]:
true

In [19]:
is_best_response(player1, 1, [0.5, 0.5])


Out[19]:
true

In [20]:
is_best_response(player1, [0.5, 0.5], [0.5, 0.5])


Out[20]:
false

In [21]:
is_best_response(player1, [0.5, 0.5], 1)


Out[21]:
false

In [22]:
is_best_response(player1, 1, [0.25, 0.75])


Out[22]:
true

In [23]:
is_best_response(player1, 2, [0.25, 0.75])


Out[23]:
true

is_nash

(1, 1) は Nash 均衡である:


In [24]:
is_best_response(g.players[1], 1, 1) && is_best_response(g.players[2], 1, 1)


Out[24]:
true

(1, 2) は Nash 均衡ではない:


In [25]:
is_best_response(g.players[1], 1, 2) && is_best_response(g.players[2], 2, 1)


Out[25]:
false

([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]:
true

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]:
true

In [30]:
is_nash(g, (1, 2))


Out[30]:
false

In [31]:
is_nash(g, ([0.75, 0.25], [0.25, 0.75]))


Out[31]:
true

3人以上のケース

例 ($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]:
2x2x2 Array{Float64,3}:
[:, :, 1] =
 1.0  0.0
 0.0  0.0

[:, :, 2] =
 0.0  0.0
 0.0  2.0

In [33]:
g3 = NormalFormGame(tuple([Player(payoff_array) for i in 1:3]...))


Out[33]:
NormalFormGame{3,Float64}((Player{3,Float64}(2x2x2 Array{Float64,3}:
[:, :, 1] =
 1.0  0.0
 0.0  0.0

[:, :, 2] =
 0.0  0.0
 0.0  2.0),Player{3,Float64}(2x2x2 Array{Float64,3}:
[:, :, 1] =
 1.0  0.0
 0.0  0.0

[:, :, 2] =
 0.0  0.0
 0.0  2.0),Player{3,Float64}(2x2x2 Array{Float64,3}:
[:, :, 1] =
 1.0  0.0
 0.0  0.0

[:, :, 2] =
 0.0  0.0
 0.0  2.0)),(2,2,2))

payoff_vector

$(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]:
2x2 Array{Float64,2}:
 1.0  0.0
 0.0  0.0

In [37]:
_reduce_last_player(payoff_array, [0.5, 0.5])


Out[37]:
2x2 Array{Float64,2}:
 0.5  0.0
 0.0  1.0

_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]:
payoff_vector (generic function with 3 methods)

In [39]:
payoff_vector(g3.players[1], (1, 1))


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

In [40]:
payoff_vector(g3.players[1], ([0.5, 0.5], [0.5, 0.5]))


Out[40]:
2-element Array{Float64,1}:
 0.25
 0.5 

is_best_response

2人のケースと同じ.


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]:
true

In [43]:
is_best_response(g3.players[1], [0.5, 0.5], (1, [0.3, 0.7]))


Out[43]:
false

is_nash

同様.


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]:
true

In [46]:
is_nash(g3, (2, 2, 2))


Out[46]:
true

In [47]:
p = 2 - sqrt(2)
is_nash(g3, ([p, 1-p], [p, 1-p], [p, 1-p]))


Out[47]:
true

問題点

_reduce_last_player で type inference がうまくいってない. (Issue #2)


In [48]:
@code_warntype _reduce_last_player(payoff_array, 1)


Variables:
  payoff_array::Array{Float64,3}
  action::Int64
  shape::Tuple{Int64,Int64,Int64}
  A::Array{Float64,2}
  out::Array{Float64,1}
  ##I#8167::Tuple{Colon,Int64}
  ####I#8157#8168::Tuple{Colon,Int64}
  ######I#8153#8158#8169::Tuple{Colon,Int64}
  #########s29#8119#8154#8159#8170::Bool
  ########_var0#8120#8155#8160#8171::Bool
  ######_var1#8156#8161#8172::Bool

Body:
  begin  # In[34], line 2:
      shape = (top(tuple))((Base.arraysize)(payoff_array::Array{Float64,3},1)::Int64,(Base.arraysize)(payoff_array::Array{Float64,3},2)::Int64,(Base.arraysize)(payoff_array::Array{Float64,3},3)::Int64)::Tuple{Int64,Int64,Int64} # In[34], line 3:
      GenSym(1) = (Base.nfields)(shape::Tuple{Int64,Int64,Int64})::Int64
      GenSym(2) = (Base.box)(Int64,(Base.sub_int)(GenSym(1),1))
      GenSym(3) = (Main.prod)((Main.getindex)(shape::Tuple{Int64,Int64,Int64},$(Expr(:new, UnitRange{Int64}, 1, :(((top(getfield))(Base.Intrinsics,:select_value)::I)((Base.sle_int)(1,GenSym(2))::Bool,GenSym(2),(Base.box)(Int64,(Base.sub_int)(1,1)))::Int64))))::TUPLE{VARARG{INT64}})::ANY
      GenSym(0) = (Base.nfields)(shape::Tuple{Int64,Int64,Int64})::Int64
      A = (Main.reshape)(payoff_array::Array{Float64,3},(top(tuple))(GenSym(3),(Base.getfield)(shape::Tuple{Int64,Int64,Int64},GenSym(0))::Int64)::TUPLE{ANY,INT64})::Array{Float64,2} # In[34], line 4:
      GenSym(5) = Main.:
      GenSym(6) = action::Int64
      NewvarNode(symbol("#########s29#8119#8154#8159#8170"))
      (Base.arraysize)(A::Array{Float64,2},1)::Int64
      unless true goto 9
      GenSym(7) = (Base.arraysize)(A::Array{Float64,2},2)::Int64
      unless (Base.sle_int)(1,GenSym(6))::Bool goto 7
      ########_var0#8120#8155#8160#8171 = (Base.sle_int)(GenSym(6),GenSym(7))::Bool
      goto 8
      7: 
      ########_var0#8120#8155#8160#8171 = false
      8: 
      #########s29#8119#8154#8159#8170 = ########_var0#8120#8155#8160#8171::Bool
      goto 10
      9: 
      #########s29#8119#8154#8159#8170 = false
      10: 
      unless #########s29#8119#8154#8159#8170::Bool goto 11
      ######_var1#8156#8161#8172 = #########s29#8119#8154#8159#8170::Bool
      goto 12
      11: 
      ######_var1#8156#8161#8172 = (Base.throw_boundserror)(A::Array{Float64,2},(top(tuple))(GenSym(5),GenSym(6))::Tuple{Colon,Int64})::UNION{}
      12: 
      ######_var1#8156#8161#8172::Bool
      out = (Base._unsafe_getindex)($(Expr(:new, :((top(getfield))(Base,:LinearFast)::Type{Base.LinearFast}))),A::Array{Float64,2},GenSym(5),action::Int64)::Array{Float64,1} # In[34], line 5:
      GenSym(8) = (Base.nfields)(shape::Tuple{Int64,Int64,Int64})::Int64
      GenSym(9) = (Base.box)(Int64,(Base.sub_int)(GenSym(8),1))
      return (Main.reshape)(out::Array{Float64,1},(Main.getindex)(shape::Tuple{Int64,Int64,Int64},$(Expr(:new, UnitRange{Int64}, 1, :(((top(getfield))(Base.Intrinsics,:select_value)::I)((Base.sle_int)(1,GenSym(9))::Bool,GenSym(9),(Base.box)(Int64,(Base.sub_int)(1,1)))::Int64))))::TUPLE{VARARG{INT64}})::ARRAY{FLOAT64,N}
  end::ARRAY{FLOAT64,N}

再掲:


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]:
(1,2,3,4)

In [51]:
x = ones(size(a)[end])


Out[51]:
4-element Array{Float64,1}:
 1.0
 1.0
 1.0
 1.0

In [52]:
func(a, x)


Out[52]:
1x2x3 Array{Float64,3}:
[:, :, 1] =
 4.0  4.0

[:, :, 2] =
 4.0  4.0

[:, :, 3] =
 4.0  4.0

In [53]:
@code_warntype func(a, x)


Variables:
  a::Array{Float64,4}
  x::Array{Float64,1}
  shape::Tuple{Int64,Int64,Int64,Int64}
  shape_reduced::TUPLE{VARARG{INT64}}
  b::Array{Float64,2}
  out::Array{Float64,1}
  ##TS#8483::Type{Float64}
  ####dims#8288#8484::Tuple{Int64}

Body:
  begin  # In[49], line 2:
      shape = (top(tuple))((Base.arraysize)(a::Array{Float64,4},1)::Int64,(Base.arraysize)(a::Array{Float64,4},2)::Int64,(Base.arraysize)(a::Array{Float64,4},3)::Int64,(Base.arraysize)(a::Array{Float64,4},4)::Int64)::Tuple{Int64,Int64,Int64,Int64} # In[49], line 3:
      GenSym(0) = (Base.nfields)(shape::Tuple{Int64,Int64,Int64,Int64})::Int64
      GenSym(1) = (Base.box)(Int64,(Base.sub_int)(GenSym(0),1))
      shape_reduced = (Main.getindex)(shape::Tuple{Int64,Int64,Int64,Int64},$(Expr(:new, UnitRange{Int64}, 1, :(((top(getfield))(Base.Intrinsics,:select_value)::I)((Base.sle_int)(1,GenSym(1))::Bool,GenSym(1),(Base.box)(Int64,(Base.sub_int)(1,1)))::Int64))))::TUPLE{VARARG{INT64}} # In[49], line 4:
      GenSym(3) = (Main.prod)(shape_reduced::TUPLE{VARARG{INT64}})::ANY
      GenSym(2) = (Base.nfields)(shape::Tuple{Int64,Int64,Int64,Int64})::Int64
      b = (Main.reshape)(a::Array{Float64,4},(top(tuple))(GenSym(3),(Base.getfield)(shape::Tuple{Int64,Int64,Int64,Int64},GenSym(2))::Int64)::TUPLE{ANY,INT64})::Array{Float64,2} # In[49], line 5:
      ##TS#8483 = Float64
      GenSym(4) = (top(tuple))((Base.arraysize)(b::Array{Float64,2},1)::Int64)::Tuple{Int64}
      GenSym(5) = (top(ccall))(:jl_new_array,(top(apply_type))(Base.Array,Float64,1)::Type{Array{Float64,1}},(top(svec))(Base.Any,Base.Any)::SimpleVector,Array{Float64,1},0,GenSym(4),0)::Array{Float64,1}
      out = (Base.LinAlg.gemv!)(GenSym(5),'N',b::Array{Float64,2},x::Array{Float64,1})::Array{Float64,1} # In[49], line 6:
      return (Main.reshape)(out::Array{Float64,1},shape_reduced::TUPLE{VARARG{INT64}})::ARRAY{FLOAT64,N}
  end::ARRAY{FLOAT64,N}

@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]:
func_g (generic function with 1 method)

In [55]:
func_g(a, x)


Out[55]:
1x2x3 Array{Float64,3}:
[:, :, 1] =
 4.0  4.0

[:, :, 2] =
 4.0  4.0

[:, :, 3] =
 4.0  4.0

In [56]:
@code_warntype func_g(a, x)


Variables:
  a::Array{Float64,4}
  x::Array{Float64,1}
  shape::Tuple{Int64,Int64,Int64,Int64}
  shape_reduced::Tuple{Int64,Int64,Int64}
  b::Array{Float64,2}
  out::Array{Float64,1}
  ####xs#8485#8492::Tuple{}
  ##TS#8493::Type{Float64}
  ####dims#8288#8494::Tuple{Int64}

Body:
  begin  # In[54], line 2: # In[54], line 3: # In[54], line 4:
      shape = (top(tuple))((Base.arraysize)(a::Array{Float64,4},1)::Int64,(Base.arraysize)(a::Array{Float64,4},2)::Int64,(Base.arraysize)(a::Array{Float64,4},3)::Int64,(Base.arraysize)(a::Array{Float64,4},4)::Int64)::Tuple{Int64,Int64,Int64,Int64} # In[54], line 5:
      GenSym(0) = (Base.nfields)(shape::Tuple{Int64,Int64,Int64,Int64})::Int64
      GenSym(1) = (Base.box)(Int64,(Base.sub_int)(GenSym(0),1))
      shape_reduced = (top(typeassert))((Main.getindex)(shape::Tuple{Int64,Int64,Int64,Int64},$(Expr(:new, UnitRange{Int64}, 1, :(((top(getfield))(Base.Intrinsics,:select_value)::I)((Base.sle_int)(1,GenSym(1))::Bool,GenSym(1),(Base.box)(Int64,(Base.sub_int)(1,1)))::Int64))))::TUPLE{VARARG{INT64}},Tuple{Int64,Int64,Int64})::Tuple{Int64,Int64,Int64} # In[54], line 6:
      GenSym(2) = (Base.nfields)(shape::Tuple{Int64,Int64,Int64,Int64})::Int64
      b = (Main.reshape)(a::Array{Float64,4},(top(tuple))((Base.box)(Int64,(Base.mul_int)((Base.box)(Int64,(Base.mul_int)((top(getfield))(shape_reduced::Tuple{Int64,Int64,Int64},1)::Int64,(top(getfield))(shape_reduced::Tuple{Int64,Int64,Int64},2)::Int64)),(top(getfield))(shape_reduced::Tuple{Int64,Int64,Int64},3)::Int64)),(Base.getfield)(shape::Tuple{Int64,Int64,Int64,Int64},GenSym(2))::Int64)::Tuple{Int64,Int64})::Array{Float64,2} # In[54], line 7:
      ##TS#8493 = Float64
      GenSym(3) = (top(tuple))((Base.arraysize)(b::Array{Float64,2},1)::Int64)::Tuple{Int64}
      GenSym(4) = (top(ccall))(:jl_new_array,(top(apply_type))(Base.Array,Float64,1)::Type{Array{Float64,1}},(top(svec))(Base.Any,Base.Any)::SimpleVector,Array{Float64,1},0,GenSym(3),0)::Array{Float64,1}
      out = (Base.LinAlg.gemv!)(GenSym(4),'N',b::Array{Float64,2},x::Array{Float64,1})::Array{Float64,1} # In[54], line 8:
      return (Main.reshape)(out::Array{Float64,1},shape_reduced::Tuple{Int64,Int64,Int64})::Array{Float64,3}
  end::Array{Float64,3}

こういう難しいのを使わない "普通の" 書き方でうまい方法はないものでしょうか. (julia-wakalang Issue #18)


In [ ]: