2 × n 型双行列ゲームの Nash 均衡点を求める図解法松井知己

本稿では, 2 人非ゼロ和ゲーム（双行列ゲーム）の中で, 特に 2 × n 型双行列ゲームの Nash 均衡点を求める図解法についてまとめる. この図解法により, 2 × n 型双行列ゲームには Nash 均衡点が存在する事が把握でき, 奇数定理の直感的な理解も可能となる.

ゲーム理論の基礎を学ぶ（教える）際に, 最初に出てくるのが戦略型 2 人ゲームであるのは, 近年でも変わらない傾向だろう. また, Nash 均衡点についてそこで初めて触れるようになっている事が多い. 2 人 \underline{ゼロ和}ゲームにおける Nash 均衡点の存在は, 線形計画法の双対定理を通した理解も可能であり, また帰納法による（ある程度）簡単な証明もある. ところが, 囚人のジレンマ等の重要なゲームを含む 2 人\underline{非ゼロ和} ゲーム（双行列ゲーム）については, Nash 均衡点の存在証明には不動点定理が必要となる. 以下では, Nash 均衡点の存在性を直感的に把握できる図を提案しよう.

いくつかの本では, 2 × 2 型双行列ゲームの例で, 図示を試みている（ほら, 卍型のあの絵ですよ！） . しかし 2 × 2 型では, ゲームの種類が限られてしまっている. そこで, 2 × n 型くらいを, なんとか図示したい.

以下では n = 4 の 2 × 4 型双行列ゲームの例を使って話を進める. プレイヤーは s と t の 2 人とする. プレイヤー s は 5 つの純粋戦略 {S_{1}, S_{2}, S_{3}, S_{4}, S_{5}} を持ち, プレイヤー t は 2 つの純粋戦略 {T_{1}, T_{2}} を持つとする. 2 人のプレイヤーの利得行列は表 1, 2 の例を用いる.

以下では, プレイヤー t が戦略 (T_{1}, T_{2}) をそれぞれ確率 (p, 1 − p) で選択する混合戦略を採用しているとする. そのときのプレイヤー s の最適反応戦略は, 図 1 で表される. 詳しくは, 以下のようになっている. 図中の直線 S_{1}, S_{2}, S_{3}, S_{4}, S_{5} はプレイヤー s が対応する純粋戦略を選択したときに得られる期待利得を表している. 例えば 0 ≤ p < 1/3 ならば, プレイヤー s は S_{1} を採用するのが最も期待利得が大きくなる. また 1/3 < p < 5/9 ならば, プレイヤー s は S_{2} を採用する

まついともみ東京大学大学院工学系研究科計数工学専攻〒 113-8656 東京都文京区本郷 7-3-1 URL: http://www.misojiro.t.u-tokyo.ac.jp/˜ tomomi/ 受理 1999. 9. 1 表 1:プレイヤー s の利得行列

S_{1} S_{2} S_{3} S_{4} S_{5}
T_{1} 50 80 100 140 40
T_{2} 140 125 100 20 100

表 2:プレイヤー t の利得行列

S_{1} S_{2} S_{3} S_{4} S_{5}
T_{1}  3  2 12  6 11
T_{2}  1  7  9 15 14

のが最も期待利得が大きくなる. 特に p = 1/3 の時は, 0 以上 1 以下の任意の値 q について, プレイヤー s は (S_{1}, S_{2}) の 2 つの戦略を (q, 1 − q) の確率で選択する混合戦略を採用するのが最も期待利得が大きくなる. ゆえに, 図 1 において 4 本の直線の上側を持ってきた折れ線 ABCDE が, プレイヤー s にとって最も期待利得が大きい, すなわち最適反応戦略となっている. 戦略 S_{5} が最適反応戦略となる事は無い. まとめると, 以下の表になる.

表 3:プレイヤー s の最適反応戦略

p [0, \frac{1}{3}) 1/3 (\frac{1}{3}, \frac{5}{9}) 5/9 (\frac{5}{9}, \frac{2}{3}) 2/3 (\frac{2}{3}, 1]
S_{1} S_{1}, S_{2} S_{2} S_{2}, S_{3} S_{3} S_{3}, S_{4} S_{4}

Nash 均衡点は, 2 人のプレイヤーが相手の戦略の最適反応戦略を採用している（混合）戦略の対である. ゆえに, Nash 均衡点におけるプレイヤー s は, 上記の表に現れる（混合）戦略のどれかを採用している. 例えば S_{1} と S_{4} を用いた混合戦略は, 表 3 中に存在しない事から, Nash 均衡点にはなり得ない.

では次に, プレイヤー t の最適反応戦略を議論しよう. 図 2 は以下のように描かれる. まず S_{1}, S_{2}, S_{3}, S_{4}, S_{5} に対し t が T_{1} (T_{2}) を採用したときの利得（表 2 参照）を座標とする点を記入する.

プレイヤー t が T_{2} を採用する（p = 0）とき, s の最適反応戦略は S_{1} である. プレイヤー s が戦略 S_{1} を採用したときは, t の利得は T_{1} (T_{2}) を採用すると 3 (1) となる. 点 (3,1) が図 2 において, 斜め 45 度の線より下にあることから, t の最適反応戦略は T_{1} （すなわち p = 1）となる. これより p = 0 となる Nash 均衡点は [figure: p; s の期待利得; 140; 125; 100; 40; 20; 140; 100; 80; 50; A; B; C; D; E; S_{5}; S_{4}; S_{1}; S_{2}; S_{3}; 0; 1/3; 5/9; 2/3; 1; 図 1:プレイヤー s の最適反応戦略][figure: T_{1} による期待利得; T_{2} による期待利得; 最適反応; 戦略は T_{1}; 最適反応; 戦略は T_{2}; S_{1}; S_{2}; S_{3}; S_{4}; S_{5}; B′ = (\frac{19}{7}, \frac{19}{7}); C′ = (\frac{33}{4}, \frac{33}{4}); (\frac{21}{2}, \frac{21}{2}) = D′; O; 1; 7; 9; 15; 16; 2; 3; 6; 12; 16; 図 2:プレイヤー t の最適反応戦略]

無い. もし t が T_{1} を採用する（p = 1）ならば, プレイヤー s の最適反応戦略は S_{4} であり, 点 (6,15) が図 2 において, 斜め 45 度の線より上にあることから, プレイヤー t の S_{2} に対する最適反応戦略は T_{2}, すなわち p = 0 となる. ゆえに, p = 1 を満たす Nash 均衡点は存在しない.

次に表 3 に出現する s の戦略の順に従い, 図 2 中に折れ線 S_{1}S_{2}S_{3}S_{4} を引く. 上記の例では, S_{1} が右下に S_{4} が左上にある事から, S_{1} から S_{4} への折れ線は必ず斜め 45 度の線を通過する. 実は, 斜め 45 度の線上の点は, Nash 均衡点となる. 以下で, これを簡単に説明しよう.

図 2 中の 4 点 S_{1}, S_{2}, S_{3}, S_{4} の, 任意の点対の内分点の座標は, s が内分比に従う混合戦略を採用した際に, t が T_{1} (T_{2}) を採用した時の t の期待利得を表している. 図 2 において斜め 45 度の線より下（上）にあるときは, t の最適反応戦略は T_{1}(T_{2}) になる. 斜め 45 度線上では, T_{1} と T_{2} の任意の混合戦略が, 最適反応戦略となる.

例えば点 B′ の座標 (19/7,19/7) は, s が (S_{1}, S_{2}) を (5/7, 2/7) で選択する混合戦略である. t が T_{1}, T_{2} どちらを採用しても期待利得が 19/7 であることから, t の任意の混合戦略が, 最適反応戦略となる. これより, Nash 均衡点が 1 つ見つかる. プレイヤー t が p = 1/3 を採用するとき, s の最適反応戦略は (S_{1}, S_{2}) の混合戦略すべてであった. プレイヤー s が (S_{1}, S_{2}) を (5/7, 2/7) で選択する混合戦略（B′）は, 点 B′ が 45 度線上に存在することから, 任意の p ∈ [0, 1] が t の最適反応戦略になる. ゆえに「(T_{1}, T_{2}) を (1/3, 2/3) で選択する混合戦略 (p = 1/3) と, (S_{1}, S_{2}) を (5/7, 2/7) で選択する混合戦略の組」は Nash 均衡点となる.

点 C′ は (S_{2}, S_{3}) を (3/8, 5/8) で選択する混合戦略, 点 D′ は (S_{3}, S_{4}) を (3/4, 1/4) で選択する混合戦略である. 以上と同様の議論により, 「(T_{1}, T_{2}) を (5/9, 4/9) で選択する混合戦略 (p = 5/9) と, (S_{2}, S_{3}) を (3/8, 5/8) で選択する混合戦略の組」および「(T_{1}, T_{2}) を (2/3, 1/3) で選択する混合戦略 (p = 2/3) と, (S_{3}, S_{4}) を (3/4, 1/4) で選択する混合戦略の組」は Nash 均衡点となる.

上記では, 折れ線が 45 度の線と交わる点に Nash 均衡点が対応することから, Nash 均衡点の個数が奇数（3 個）になる. 図 2 において点 S_{4} が 45 度線より下にあったら, どうなるのか？そのときは点 D′ とそれに対応する Nash 均衡点が消失するかわり, 「t が T_{1} を (p = 1 を) 選択し, s が S_{4} を選択する組」という Nash 均衡点が出現し, Nash 均衡点の数は依然として 3 つである.

上記の図解法から, ゲームの変形に対して Nash 均衡点の集合を保持する事の難しさを, 直感的に把握することもできる. 例えば, 図 2 において S_{2} の点を \underline{連続的に}移動させても, S_{2} が 45 度の線を越えたところで B′ と C′ の点に対応する Nash 均衡点が 1 つに合わさり, そして消失するという, \underline{不連続な}状況が起こる. あるいは, 純粋戦略 S_{3} を消去したとき, Nash 均衡点 C′, D′ は消失し, Nash 均衡点は B′ のみとなる. さらに, 利得行列の連続的な変形や, 純粋戦略の追加や削除によって, Nash 均衡点が出現あるいは消失する例も容易に作る事が出来る. これらの事実を 2 × 2 型の双行列ゲームで把握することは容易ではない.