ゲーム理論 (game theory)

ゲーム理論 (game theory)
互いに競争状態にある場面での意思決定問題
最適な戦略(strategy)およびそのときの結果を考える。
相手：個人、企業、国家など意思を持っている
【用語】
競争者(player) ：互いに独自の戦略を選択し、勝負する
ｎ人ゲーム ：ｎ人のプレヤー(player)がいるゲーム
利得表(pay-off matrix) :各プレヤーの結果（利益)
ゼロ和ゲーム (zero-sum game)：各プレヤーの利得
の合計がゼロとなっているゲーム
©ＡＴＳＵＴＯ ＮＩＳＨＩＯ
戦略(strategy)
• 純粋戦略(pure strategy) − 閉じた戦略
各プレヤーは、自分の戦略からただ１つの戦略
を選び、勝負する。
ゲームの結果(最適解) ｰ 鞍点(saddle point)
mini-max法 ：自分はマキシミン原理で行動し、
相手はミニマックス原理で行動する。一致した点がゲーム解。
• 混合戦略(mixed strategy) − 開いた戦略
最適解が存在しない
→ 確率、行列、グラフなどを利用する
©ＡＴＳＵＴＯ ＮＩＳＨＩＯ
cf. p.15
純粋戦略
２人ゼロ和ゲーム
プレハブ・ハウスの生産・販売をしている i社、j社
ｉ
ｊ
別 荘
店 舗
新婚住宅
勉強部屋
０．５
１
２
事 務 所 −４．５
４
−６
©ＡＴＳＵＴＯ ＮＩＳＨＩＯ
純粋戦略の考え方
両社は悪い状態の中でより高い利益が期待できる戦略を選ぶ。
即ち
• i社は各戦略の最悪の場合(最小値)のうち、
最高値の戦略を選ぶ。 → Maxmin原理
• J社は各戦略の最悪の場合(最大値)のうち、
最小値の戦略を選ぶ。 → Minimax原理
両社の戦略が交差した値がゲームの解
→ サドル点
©ＡＴＳＵＴＯ ＮＩＳＨＩＯ
サドル点のグラフ表示
サドル点
i社
j社
©ＡＴＳＵＴＯ ＮＩＳＨＩＯ
純粋戦略 (cont)
別荘 店舗 新婚住宅 (最小値)
勉強部屋
1
2
0.5
0.5 max min
事 務 所 ｰ4.5
4
ｰ6
ｰ6
(最大値)
4
2
0.5
min max
ｉ社は勉強部屋、ｊ社は別荘を生産・販売したと
き、ゲームの解は0.5
サドル点＝ゲームの解
©ＡＴＳＵＴＯ ＮＩＳＨＩＯ
cf. p.18
混合戦略
サドル点が
Ａ、Ｂでじゃんけん − ２人ゲーム
Ａ
Ｂ
ぐう
ちょき
ぱあ
(最大値)
存在しない
ちょき
ぱあ
０
１
−１
−１
−１
０
１
−１
ぐう
１
−１
０
１
１
１
©ＡＴＳＵＴＯ ＮＩＳＨＩＯ
(最小値)
−１
cf. p.19
混合戦略 (行列を利用)
行列を利用する場合 ： ２×２の行列で有効
a b
G= c d
p=(p1,p2)=(A,B) q=(q1,q2)=(C,D)
このとき、期待値ｖ=｜G｜/s
ただし、
A=(d - c)/s
B=(a - b)/s
C=(d - b)/s
D=(a - c)/s
｜G｜=a・d − b・c
s=a＋d−ｂ−ｃ
©ＡＴＳＵＴＯ ＮＩＳＨＩＯ
cf. p.20
混合戦略 (例題)
行列を利用する場合 ： ２×２の行列で有効
2 -1
G = -1 2
s=2+2-(-1)-(-1)=6
p=(｛2-(-1)}/6,{2-(-1)}/6)=(1/2,1/2)
q=({2-(-1)}/6,{2-(-1)}/6)=(1/2,1/2)
このとき、
期待値ｖ=｜G｜/s = {2×2-(-1)(-1)}/6 = 1/2
©ＡＴＳＵＴＯ ＮＩＳＨＩＯ
混合戦略 (確率を利用)
じゃんけんの場合：３×３なので行列による解法は利用できない。確率を利用
利得行列に負の値があるので、一定数を加え正の値にする。
-1 0 1
1 2 3
1 -1 0
→（２を加える）→ 3 1 2
(Ⅰ)
0 1 -1
2 3 1
Aの最適戦略を Ｘ ＝ (ｘ1，ｘ2，ｘ3)
ｘ1 ＋ ３ｘ2 ＋ ２ｘ3 ≧ ｖ0
２ｘ1 ＋ ｘ2 ＋ ３ｘ3 ≧ ｖ0
３ｘ1 ＋ ２ｘ2 ＋ ｘ3 ≧ ｖ0
，ゲームの解を v0 とすると、(Ⅰ)より、
©ＡＴＳＵＴＯ ＮＩＳＨＩＯ
混合戦略 (確率を利用)
Aの最適戦略を X ＝ (ｘ1，ｘ2，ｘ3) ，ゲームの解を v0 とすると、(Ⅰ)より、
ｘ1 ＋ ３ｘ2 ＋ ２ｘ3 ≧ ｖ0
２ｘ1 ＋ ｘ2 ＋ ３ｘ3 ≧ ｖ0
３ｘ1 ＋ ２ｘ2 ＋ ｘ3 ≧ ｖ0
v0 は正の値だから、上の各式を ｖ0 で割り、ｘi / ｖ0 ＝ θi と置く。
また、Aは ｖ0 を最大にするように X を選ぶから、1 / ｖ0 を最小にすればよい。
従って、
θ1 ＋ ３θ2 ＋ ２θ3 ≧ 1
２θ1 ＋ θ2 ＋ ３θ3 ≧ 1
３θ1 ＋ ２θ2 ＋ θ3 ≧ 1
θ1 ＋ θ2 ＋ θ3 ＝ 1 / ｖ0 ＝最小
θ1 ， θ2 ，θ3 ≧ 0
【Ⅱ】
©ＡＴＳＵＴＯ ＮＩＳＨＩＯ
混合戦略 (確率を利用)
θ1 ＋ ３θ2 ＋ ２θ3 ≧ 1
２θ1 ＋ θ2 ＋ ３θ3 ≧ 1
３θ1 ＋ ２θ2 ＋ θ3 ≧ 1
θ1 ＋ θ2 ＋ θ3 ＝ 1 / ｖ0 ＝最小
θ1 ， θ2 ，θ3 ≧ 0
【Ⅱ】
【Ⅱ】は明らかに線形計画の問題。
変数の数がθ1 とθ2 の２つならば、図式解法で、
変数の数が３個以上のときは、シンプレックス法で解ける。
シンプレックス法より、 θ1＝1/6 ， θ2＝1/6 ， θ3＝1/6
これより、1 / ｖ0 ＝θ1 ＋ θ2 ＋ θ3 ＝ 1/2 ∴ ｖ0 ＝2
ｘi / ｖ0 ＝ θi だから ｘ1 ＝ 1/3 ． ｘ2 ＝ 1/3 , ｘｘ3＝ 1/3
利得行列には 2 を加えたので、ｖ0 から 2 を引いてゲームの解は 0 となる。
©ＡＴＳＵＴＯ ＮＩＳＨＩＯ
ジレンマ・ゲーム（dilemma game）
非ゼロ和ゲームの一種
表のようにマクシミン戦略を選択するとａ2，b2となり、
ゲームの解は２となる。しかし表からも分かるように 戦略
ａ1，b1を選択した方は得策である。
ａ1
そのためには、Ａ，Ｂ両者の協力が必要となる。
しかし、Ａが裏切って戦略をａ2に変えると、Ｂの
利益は１に減少し、Ａの利益は４に増大する。
Ｂが裏切った場合も同様である。Ａ，Ｂが共に
ａ2
裏切ると戦略ａ2，b2が選択され、両者の利益は
共に２となり、報復を受けることになる。
ｂ2
ｂ1
３
１
３
４
４
２
１
２
左上はＡ，右下はＢの利益
©ＡＴＳＵＴＯ ＮＩＳＨＩＯ
弱虫ゲーム
このゲームは、危険をおかして勇者となるか、
安全を取って。弱虫となるかのジレンマ・ゲーム。
マクシミン戦略はａ1,ｂ1でゲームの解は共に３となる。
しかし、Ａが勇気をだして積極策を選び、
利益が１減少する危険を冒して、戦略ａ2を選択 戦略
すると、利益は４に増大する。
ａ1
これに対して、Ｂが相変わらず安全第一主義を
取るとすれば、Ｂの利益は２に減少する。
ａ2
４
２
４
１
２
©ＡＴＳＵＴＯ ＮＩＳＨＩＯ
ｂ2
ｂ1
３
３
１
指導者ゲーム
このゲームは、先手をとって指導者となり、大きな利益を獲得するか、追従者
となっても指導者の指示に従順に従って、次善の策をあてがわれるかというよう
な場合のジレンマ・ゲーム。
マクシミン戦略はａ1,ｂ1でゲームの解は共に２である。
ここで、Ａは戦略をａ2に変更すると、利益は４で最高
となり、Ｂの利益も３に増大する。しかし、同じことはＢ
にもいえる。ところが、Ａ,Ｂ共にマクシミン戦略を選択
すると、利益は最悪の１となってしまう。そこで、Ａは
リーダーシップを発揮し、共に有利であることを理由に、
Ｂにｂ1を選択させ、自分はａ2を選択する。
弱虫ゲームとの相違は、ＢはＡの言うことを聞いても、
利益が２から３に増大し次善の策となることである。
©ＡＴＳＵＴＯ ＮＩＳＨＩＯ
戦略
ａ1
ｂ1
２
２
ａ2
４
ｂ2
３
４
１
３
１
英雄ゲーム
このゲームは、自己の利益より相手の利益が多くても、自ら次善の策を選ぶこ
とによって自己の利益も増大するような場合のジレンマ・ゲームであり、指導者
ゲームの反対の心理状態を表すモデルである。
マクシミン戦略はａ1,ｂ1でゲームの解は共に２である。
ここで、Ｂが戦略をｂ2に変更すると、Ａは最高の利益４
となる。また、Ａがａ1を選べば、Ｂの利益が最高となる。
そこで互いに相手が譲歩し、自分に花を持たせてくれる
ように期待している。
このときＡは英雄心を発揮してＢに花を持たせるため
自分はａ1を選び３の利益に甘んじ、Ｂに４の利益を実
現させることを提案する。これでもＡの利益は２から３
に増大するから、その英雄的行為はある程度報われ
ることになる。同じことはＢについてもいえる。
しかし、Ａ,Ｂ両者が犠牲的精神を発揮しａ2,ｂ2を選
ぶと最悪の利益１となる。
©ＡＴＳＵＴＯ ＮＩＳＨＩＯ
戦略
ａ1
ｂ1
２
２
ａ2
３
ｂ2
４
３
１
４
１
囚人ゲーム
このゲームは、お互いに相手に対して疑心暗鬼を生じている場合のジレンマ・ゲームである。
Ａ,Ｂは共犯である。検事がＡ,Ｂを別々に呼んで、
両者の犯した罪は共に４年の刑に相当する。
もしも、いずれか一方が自白すれば十分後悔した
ものと認め、自白した者の刑を１年に減刑するが、
もう一方の否認し続けた者は一層重い６年の刑を
科すると宣言した。
一方、弁護士は両者とも否認し続けた場合には、
証拠不十分で、共に２年の刑で済むと薦めた。
この場合、一番良いのは、弁護士の薦めに従って
両者とも否認することである。しかしＡ,Ｂは別々に
隔離されているため、相手がもしかすると減刑のために
自白するのではないかと疑心暗鬼に陥り、両者共に
共犯の事実を認めてしまい、結局最悪のケースに陥ってしまう。
©ＡＴＳＵＴＯ ＮＩＳＨＩＯ
Ｂ
否認
否認
Ａ
自白
自白
-2 -6
-2 -1
-1 -4
-6 -4