展開形ゲーム : 定義

展開形ゲーム : 定義
展開形ゲームとは？
ゲームの木 (game tree) を用いて記述されるゲーム形式
Γ = (K, P, p, U, h)
岡田章「ゲーム理論」第 3 章から
反撃(R)
(F)
応戦
w(1):(-3,-3)
0(3)
協調(C)
0(2)
w(2):(-5,15)
(1/2)
A
0(1)
協調(C)
協調
(C)
w(3):(6,6)
0(4)
無視(I)
N
(1/2)
w(0):(0,10)
w(4):(5,5)
(1) ゲームの木 K：
初期点 0 から始まり，枝 (edge) と点 (node) からなる．
点 x までの枝と点の系列をパス(pass) という
(以後点とその点へのパスとを同一視する)．
x へのパス上の点 y を x > y と書く．
w : w が x > w なる x をもたない，w を頂点という．
W : 木の頂点の集合
X : 頂点以外の点 (手番，move) の集合
手番 x から直後の点を結ぶ枝を選択肢(alternative) と呼ぶ．
A(x) : x における選択し全体
プレイ : 初期点から頂点を結ぶパス
(2) プレイヤーの分割 P
プレイヤーの分割(player partition)
P = [P0 , P1 , P2 , . . . , Pn ]
ゲームの木 K の手番の集合 X 上の分割, 添え字 (i = 1, . . . , n) はプ
レイヤーを表す
i = 0 は偶然手番の集合となる
ex)P0 = {0(1)}, P1 = {0(2)}.P2 = {0(3), 0(4)}
1)X = P0 ∪ P1 ∪ . . . ∪ Pn
2) 任意の Pi , Pj (i ̸= j) に対して，Pi ∩ Pj = ϕ
3)Pi ̸= Φ, i = 1, 2, . . . , n
(3) 偶然手番の確率分布族 p
すべての偶然手番 x ∈ P0 に対し，x での選択肢の集合 A(x) 上のひと
つの確率分布 px が定められている.各選択肢 e ∈ A(x) に対して付与
する確率を px (e) とすれば，
∑
px (e) = 1 , 0 ≤ px (e) ≤ 1
e∈A(x)
が成り立つ．偶然手番 x ∈ P0 の確率分布 px の族を p とおく．
(4) 情報分割 U
情報分割(inf ormation partition)U
U = [U0 , U1 , . . . , Un ] は 1 つの P の細分割である
すべての i に対して, Ui は集合 Pi の部分集合 u の族であり,
∪
( )Pi =
u
u∈Ui
( )Ui の任意の異なる 2 つの集合 u, v に対して u ∩ v = ϕ
が成り立つ
Ui：プレイヤー i の情報分割, Ui に属する集合を
プレイヤー i の情報集合 (inf ormation set)
( ) 情報集合 u は同じプレイに 2 回以上交わってはならない
( ) 情報集合 u に含まれるすべての手番は同じ数の枝を持つ
情報集合 u における選択肢の全体を A(u) で表す
u(21)
0(4)
s(1)
s(3)
w(1)
s(4)
w(2)
s(5)
w(3)
s(6)
w(4)
s(5)
w(5)
u(1)
0(5)
0(2)
s(2)
u(0)
u(22)
0(1)
0(3)
s(2)
0(6)
s(1)
0(7)
s(6)
w(6)
s(3)
w(7)
s(4)
w(8)
プレイヤーの分割 :
P0 = {0(1)}, P1 = {0(2), 0(3)}
P2 = {0(4), 0(5), 0(6), 0(7)}
情報分割 :
U0 = [u(0)] = {0(1)}, U1 = [u(1)] = [{0(2), 0(3)}]
U2 = [u(21), u(22)] = [{0(4), 0(7)}{0(5), 0(6)}]
(5) 利得関数 h
利得関数(payof f f unction)h は，ゲーム K の各頂点 w ∈ W に対
して利得ベクトル
h(w) = (h1 (w)，h2 (w)，. . . , hn (w))
を対応させるもの
展開形ゲームΓ = (K, P, p, U, h)
この構成要素をルールと呼ぶ
ルールを全員が知っていてかつ全員がそのことを知っている：すべて
のプレイヤーの共通知識 (common knowledge) という
情報完備ゲーム (game with complete inf ormation) と呼ぶ
プレイヤーが情報を完全には把握していない
情報不完備ゲーム (game with incomplete inf ormation) と
呼ぶ
戦略(strategy)
• 純粋戦略
• 混合戦略
• 局所戦略
• 行動戦略
純粋戦略(pure strategy)
プレイヤー i の純戦略とは, プレイヤー i の各情報集合 u ∈ Ui に対し
て u における 1 つの選択肢πi (u) ∈ A(u) を対応させる関数πi である
プレイヤー i の純戦略の集合をΠi とおく
混合戦略(mixed strategy)
プレイヤー i の混合戦略とは純粋戦略の集合Πi 上の確率分布
プレイヤー i の混合戦略の集合を Qi とおく
局所戦略(local strategy)
情報集合 u ∈ Ui におけるプレイヤー i の局所戦略とは u における選択
肢の全体 A(u) 上の確率分布 biu のことである
行動戦略(behavior strategy)
各情報集合 u ∈ Ui に対して u における 1 つの局所戦略 biu を対応させ
る関数
プレイヤー i の行動戦略の全体を Bi
期待利得
b = (b1 , b2 , b3 , . . . , bn ) : プレイヤーの行動戦略の組
biu (e) : プレイヤー i が情報集合 u ∈ Ui において枝 e ∈ A(u) を選
択する確率
E(w) : 頂点 w ∈ W に対して, 初期点 0 から w までのパス上におけ
るすべての枝の全体.E0 (w), Ei (w) からなる
E0 (w) : 偶然手番の枝の集合
Ei (w) : プレイヤー i の枝の集合
c(w) : E0 (w) に含まれる偶然手番のすべての枝 e が選択される確率
の積
∑
c(w) =
p(e)
e∈E0 (w)
プレイ w が偶然手番を含まない場合 : c(w) = 1
行動戦略の組 b に対して
n
∏
∏
p(w|b) = c(w)
bi (e)
i=1 e∈Ei (w)
到達可能 : p(w|b) > 0
混合戦略の組 q に対して
∑
p(w|q) =
( n
∑ ∏
...
π1 ∈Π1
)
qi (πi )
πn ∈Πn
π = (π1 , π2 , . . . , πn )
i=1
p(w|π)
戦略の組 s = (s1 , . . . , sn ) として, プレイヤー i の期待利得 Hi は,
Hi (s1 , . . . , sn ) =
∑
w∈W
p(w|s)hi (w)
で定義される
簡単に言えば,「頂点 w の実現確率」×「その頂点における利得」を各
頂点について計算し和をとったもの
以上の定義により, プレイヤーの純戦略の集合Πi と期待利得関数 Hi
を用いることにより,
G = (N, {Πi }i∈N , {Hi }i∈N )
を構成できる：展開形ゲームΓの標準化 (normalization)
ナッシュ均衡の定義
定義 (ナッシュ均衡)
∗
∗
展開形ゲームΓにおいて, 行動戦略の組 b∗ = (b∗
,
b
,
.
.
.
,
b
1
2
n) が
ナッシュ均衡点であるとは, すべてのプレイヤー i = 1, 2, . . . , n のす
べての行動戦略 bi ∈ Bi に対して,
∗
Hi (b∗
)
≥
H
(b
,
b
i i
i
−i )
が成立することである．
ゲームの分解と合成
定義
Γ = (K, P, p, U, h) を展開形ゲームとする.ゲームの木 K の部分 K ′
に対して
Γのすべての情報集合は K ′ の手番と, K ′ 以外の手番を同時に含むこ
とはない
ならば, ゲームΓの各構成要素を部分木 K ′ に制限することにより部分
木 K ′ をもつ展開形ゲームを定義できる.このようなゲームを, ゲームΓ
の部分ゲーム (subgame)という.便宜上, ゲームΓ自身もΓのひとつの
部分ゲームとみなす
B
A
維持
引下
維持
維持
(4,4)
(1,6)
(6,1)
1/2
N
引下
1/2
維持
引下
B
(2,2)
維持
引下
引下
維持
引下
(4.4)
(6.1)
(1.6)
(2,2)
定義
ゲームΓの部分ゲームΓ′ と
Γ′ における行動戦略の組 b′ = (b′1 , . . . , b′n ) に対して,
部分ゲームΓ′ 全体をプレイヤーの期待利得ベクトル
s
H s (b′ ) = (H1s (b′ ), . . . Hn
(b′ )) で置き換えてできるゲームを, 部
分ゲームΓ′ と行動戦略の組 b′ によるゲームΓの
縮約ゲーム (truncated game)といい T (Γ/Γ′ , b′ ) とかく.
展開形ゲームΓの部分ゲームΓ′ が
プレイヤーの行動戦略の組 b = (b′1 , . . . , b′n ) によって到達可能であ
るとは, 行動戦略の組 b のもとでΓ′ の初期点 o′ が正の確率で到達され
るときをいう.
定理
展開形ゲームΓの行動戦略による均衡点 b∗ = (b∗′1 , . . . , b∗′n ) は次
の 2 条件を満たす
(1)b∗ によって到達可能なすべての部分ゲームΓ′ に均衡点 b∗′ を導く
(2) 任意の部分ゲームΓ′ に対して,
Γ′ と b∗′ によるΓの縮約ゲーム T (Γ/Γ′ , b∗′ ) に均衡点 b∗T を導く.
定理
展開形ゲームΓの行動戦略の組 b∗ = (b∗′1 , . . . , b∗′n ) が
(1)Γのある部分ゲームΓ′ に均衡点 b∗′ を導き, さらに
(2)Γ′ と b∗′ によるΓの縮約ゲーム T (Γ/Γ′ , b∗′ ) に均衡点 b∗T を導く
ならば, b∗ はゲームΓの均衡点である
完全情報ゲーム(game with perf ect inf ormation)
定義
展開形ゲームΓにおいてすべてのプレイヤー i(= 1, 2, . . . , n) のすべ
ての情報集合 u ∈ Ui がただ 1 つの手番からなるとき, ゲームは完全情
報ゲームであるという.
定理
ゲームの木が有限の長さをもつ完全情報ゲームでは, 純戦略による均
衡点が存在する.ただし, ゲームの木の長さとは一つのプレイに含まれ
る手番の最大数のことである.