このコラムは，ORにかかわる概念，知識（手法，原理），それらの図解，よい教材や問題，∴・。応⊇メモランダム

実学ORの実施経験，そこから得られた智恵やアドバイス，失敗談と教訓，新しい視点，視座，フレームワーク，未だ解けていない問題，面白い研究テーマなどを， 新鮮に ，しかも コンパクトに表現し，提示していただくものです．ふるってご投稿ください．（原稿は，刷り上がI），半ページから3ページに納まるようにお書きくだきい．簡単に．／ 加筆訂正をお願いする場合があります）

2×乃型双行列ゲームのNash均衡点を求める図解法桧井 知己
本稿では，2人非ゼロ和ゲーム（双行列ゲーム）の中で，特に2×れ塑双行列ゲームのNash均衡点を求める図解法

表1：プレイヤーβの利得行列についてまとめる．この図解法により，2×町型双行列ゲー
ムにはNash均衡点が存在する事が把撞でき，奇数定理の直感的な理解も可能となる．

ゲーム理論の基礎を学ぶ（数える）際に，最初に出てくるのが戦略型2人ゲームであるのは，近年でも変わらない

表2：プレイヤー電の利得行列傾向だろう．また，Nash均衡点についてそこで初めて触れるようになっている事が多い．2人ゼロ和ゲームにおけるNash均衡点の存在は，線形計画法の双対定理を通した理解も可能であり，また帰納法による（ある程度）簡単な証明もある．ところが，囚人のジレンマ等の重要なゲー
ムを含む2人非ゼロ和ゲーム（双行列ゲーム）について

0≦p＜1／3ならば，プレイヤーぶはぎ1を採用するのは，Nash均衡点の存在証明には不動点定理が必要となる．

が最も期待利得が大きくなる．また1／3＜p＜ 5／9な以下では，NalSh均衡点の存在性を直感的に把握できる図

らば，プレイヤーβはg2を採用するのが最も期待利得がを提案しよう．

大きくなる．特にp＝1／3の時は，0以上1以下の任意

いくつかの本では，2×2塑双行列ゲームの例で，図示をの値曾について，プレイヤーβは（gl，g2）の2つの戦略試みている（ほら，卍型のあの絵ですよ！）．しかし2×を（ヴ，1一世）の確率で選択する混合戦略を採用するのが2型では，ゲームの種類が限られてしまっている，そこで，最も期待利得が大きくなる．ゆえに，図1において4本の2×㍑型くらいを，なんとか図示したい．

直線の上側を持ってきた折れ線ABCDEが，プレイヤーS以下ではれ ＝ 4の2 × 4型双行列ゲームの例をにとって最も期待利得が大きい，すなわち最適反応戦略と使って話を進める．プレイヤーはβとfの2人とする．プなっている．戦略g5が最適反応戦略となる事は無い．まとレイヤーβは5つあ純粋戦略‡51，52，量，範，g5）を持ち，めると，以下の表になる．

プレイヤーまは2つの純粋戦略‡n，苅）を持つとする．2人のプレイヤーの利得行列は表1，2の例を用いる．
以下では，プレイヤーfが戦略（n，苅）をそれぞれ確率（針1−p）で選択する混合戦略を採用しているとする．

表3：プレイヤーβの最適反応戦略

p ［0，喜） 1／3 （圭，告） 5／9 （喜，喜） 2／3 （喜，1］
51 gl，52 52 g2，5も 53 5も，5宣 5宣

そのときのプレイヤーβの最適反応戦略は，図1で表さ

Nash均衡点は，2人のプレイヤーが相手の戟略の最適反れる．詳しくは，以下のようになっている．国中の直線応戦略を採用している（混合）戦略の対である．ゆえに，

ぎ1，g2，量，54，g5はプレイヤーβが対応する純粋戦略を

Nash均衡点におけるプレイヤーβは，上記の表に現れる選択したときに得られる期待利得を表している．例えば（混合）戦略のどれかを採用している．例えば51とg4を用いた混合戦略は，表3中に存在しない事から，Nash均

まついともみ 東京大学大学院工学系研究科計数工学専攻〒113−8656東京都文京区本郷7−3−1

衡点にはなり得ない．
では次に，プレイヤーまの最適反応戦略を議論しよう．

URL：http：／／www・misojiro・t・u−tOkyo・aC・jprtomomi／

図 2は以下のように措かれる．まずgl，g2，量，範，g5に対しまがれ（苅）を採用したときの利得（表2参照）を

1999年12月号© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（25）665

ざの期待利得
座標は，βが内分比に従う混合戦略を採用した際に，まがn（為）を採用した時のまの期待利得を表しているt図2において斜め45度の線より下（上）にあるときは，fの最適反応戟略はn（苅）になる・斜め45度線上では，nと苅の任意の混合戦略が，最適反応戦略となる．
例えば点月′の座標（19／7，19／7）は，βが（gl，52）を（5／7，2／7）で選択する混合戦略である・まがれ，苅どちらを採用しても期待利得が19／7であることから，まの任意の混合戦略が，最適反応戦略となる．これより，Nash均
01／3 5／92／3

1

囲1：プレイヤ】−βの最適反応戟略

衡点が1つ見つかる．プレイヤーまがp＝1／3を採用するとき，βの最適反応戦略は（51，筑）の混合戟略すべてであった・プレイヤーβが（gl，g2）を（5／7，2／7）で選択す為による期待利得

る混合戦略（β′）は，点β′が45度線上に存在することから，任意のp∈［0，1］がtの最適反応戦略になる・ゆえに「（れ，乃）を（1／3，2／3）で選択する混合戦略（p＝1／3）と，（51，∫2）を（5／7，2／7）で選択する混合戟略の組」はNash均衡点となる．
点C′は（銭，烏）を（3／8，5／8）で選択する混合戦略，点β′は（＄，54）を（3／4，1／4）で選択する混合戦略であるt以上と同様の議論により，「（n，苅）を（5／9，4／9）で選択する混合戦略（p＝5／9）と，（52，烏）を（3／8，5／8）で選択する混合戦略の組」および「（n，為）を（2／3，1／3）で選択する混合戟略（p＝2／3）と，（g3，量）を（3／4，1／4）
で選択する混合戦略の粗」はNash均衡点となる．
れによる期待利得
図2：プレイヤーまの最適反応戦略

上記では，折れ線が45度の線と交わる点にNash均衡点が対応することから，Nash均衡点の個数が奇数（3個）になる．図2において点54が45度線より下にあっ座標とする点を記入する．

プレイヤー1が策を採用する（p＝0）とき，占の最たら，どうなるのか？そのときは点β′とそれに対応する適反応戦略は51である，プレイヤーβが戦略51を採用

Nash均衡点が消失するかわり，「壬がnを（p＝1を）選したときは，まの利得はTl（為）を採用すると3（1）とな択し，βがg4を選択する組」というNash均衡点が出現る‥与（3，1）が図2において，斜め45度の線より下にあるし，Nash均衡点の数は依然として3つである・

ことから，まの最適反応戦略はn（すなわちp＝1）とな

上記の図解法から，ゲームの変形に対してNash均衡点る．これよりp＝0となるNastl均衡点は無い・もしまがの集合を保持する事の難しさを，直感的に把握することもnを採用する（p＝1）ならば，プレイヤー5の最適反応できる．例えば，図2において52の点を連続的に移動さ戦略は54であり，点（6，15）が図2において，斜め45度のせても，52が45度の線を越えたところでβ′とC′の点線より上にあることから，プレイヤーまの52に対する最に対応するNasll均衡点が1つに合わさり，そして消失す

適反応戦略は苅，すなわちp＝0となる・ゆえに，p＝1るという，不連続な状況が起こる．あるいは，純粋戦略ざ3を満たすNash均衡点は存在しない．

を消去したとき，Nash均衡点C′，β′は消失し，Nash均次に表3に出現するβの戦略の順に従い，図2中に折れ衡点はβ′のみとなる、さらに，利得行列の連続的な変形

線5152S3S4を引く，上記の例では，51が右下に54が左や，純粋戦略の追加や削除によって，Nash均衡点が出現あ上にある事から，51から54への折れ線は必ず斜め45度るいは消失する例も容易に作る事が出来る．これらの事実の線を通過する．実は，斜め45度の線上の点は，Nash均を2×2型の汲行列ゲームで把捜することは容易ではない．

衡点となる．以下で，これを簡単に説明しよう・
図2中の4点Sl，52，53，54の，任意の点対の内分点の686（26）© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズ・リサーチ