ナッシュ均衡

ナッシュ均衡︵ナッシュきんこう、英: Nash equilibrium︶は、ゲーム理論における非協力ゲームの解の一種であり、いくつかの解の概念の中で最も基本的な概念である。数学者のジョン・フォーブス・ナッシュにちなんで名付けられた。

ナッシュ均衡は、他のプレーヤーの戦略を所与とした場合、どのプレーヤーも自分の戦略を変更することによってより高い利得を得ることができない戦略の組み合わせである。ナッシュ均衡の下では、どのプレーヤーも戦略を変更する誘因を持たない。

ナッシュ均衡は必ずしもパレート効率的ではない。その代表例が囚人のジレンマである。

定義

形式的な定義は次の通りである。標準型ゲーム G= (N, S, u) ︵N はプレーヤーの集合、$S=\prod _{i\in N}S_{i}$$S=\prod _{i\in N}S_{i}$ は戦略の組の集合、$u=(u_{i})_{i\in N}\;(u_{i}:S\rightarrow \mathbb {R} )$$u=(u_{i})_{i\in N}\;(u_{i}:S\rightarrow \mathbb {R} )$ は効用の組︶において、戦略の組 $s^{*}\in S$$s^{*}\in S$がナッシュ均衡であるとは、全てのプレーヤー $i\in N$$i\in N$と、全ての $s_{i}\in S_{i}$$s_{i}\in S_{i}$に対して、

$u_{i}(s^{*})\geq u_{i}(s_{i},s_{-i}^{*})$$u_{i}(s^{*})\geq u_{i}(s_{i},s_{-i}^{*})$
を満たすことである。

ただし、s_−i は、i 以外のプレーヤーの戦略の組をさす。

純粋戦略ゲームにおけるナッシュ均衡

支配戦略均衡

「囚人のジレンマ」も参照

純粋戦略ゲーム (Pure strategy game) とは、参加者 (プレーヤー) が必ずどれかの戦略を選ぶゲームである。例えば、以下の表は、二人のプレーヤー P_a と P_b がそれぞれ戦略（A₁ または A₂）と（B₁ または B₂）を選べるときの、それぞれの利得を示す。並んだ数字の左側は P_a の利得、右側は P_b の利得である。

Pa/Pb	B1	B2
A1	5, 2	2, 4
A2	4, 6	1, 6

まずP_a の利得に注目すると、P_b がどちらの戦略を選ぼうが、P_a はA₁ 戦略を選んだ方がより大きな利得を得ることができる。このような関係が成り立つとき、A₁ は強支配戦略であると表現する。支配するとは、ある戦略を選ぶことが他方の戦略を選ぶより有利であるという意味である。

次にP_b の利得に注目すると、P_a がどちらに戦略を選んでも、B₂ 戦略を選んだ方がB₁ 戦略のとき以上の利得を得られる。P_a がA₂ 戦略を選んだ場合にはB₁ とB₂ は同等になるので、このような関係のときB₂ は弱支配戦略であるという。

結果として、P_a にとっての最適戦略はA₁、P_b にとっての最適戦略はB₂ となり、両者ともここから戦略を変更しても利得は減る。この組み合わせ (A₁, B₂) が支配戦略均衡となる。

P_a、P_b が (A₁, B₂) という戦略をとった場合、P_aは戦略を変更してA₂ をとれば利得が2から1へ減少してしまうため、戦略を変更する誘因を持たない。同様にP_b も、戦略を変更してB₁ をとれば利得が4から2へ減少してしまうため、戦略を変更する誘因を持たない。従ってこの例では支配戦略均衡はナッシュ均衡である。

なお、P_a、P_b が (A₂, B₁) という戦略をとった場合の利得は (4, 6) となり、ナッシュ均衡における利得と比べてP_a、P_b ともにより大きな利得を得ることができる。この場合、P_a がより大きな5の利得を得るためA₁ に戦略を変更する誘因を持つため、ナッシュ均衡ではない。すなわち、このゲームは囚人のジレンマゲームである。また、(A₁, B₂) から (A₂, B₁) への戦略変更は、パレート改善であり、ナッシュ均衡 (A₁, B₂) はパレート効率的ではない。

逐次消去による均衡

相手の戦略によってどの戦略が最も大きな利得を出すかが変化する場合、他の戦略すべてを支配できる戦略が存在しない場合がある。そのような場合、他から支配されている戦略︵被支配戦略︶を消去していくことで残った戦略の組み合わせを支配戦略均衡と定義できる。支配戦略によってナッシュ均衡が定義できる場合、それは消去によって定義されたものと一致する。

Pa/Pb	B1	B2	B3
A1	5, 2	2, 4	4, 0
A2	4, 6	3, 6	2, 5
A3	3, 3	1, 2	7, 2

B₃ は B₂ に支配されているため、B₃ を消去。

Pa/Pb	B1	B2
A1	5, 2	2, 4
A2	4, 6	3, 6
A3	3, 3	1, 2

A₃ は A₂ に支配されているため A₃ を消去。

Pa/Pb	B1	B2
A1	5, 2	2, 4
A2	4, 6	3, 6

B₁ は B₂ に支配されているため B₁ を消去。

Pa/Pb	B2
A1	2, 4
A2	3, 6

支配戦略均衡は (A₂, B₂)。

純粋戦略ナッシュ均衡

他のプレイヤーの戦略によらず最大利得をもたらす戦略の組合せも被支配戦略の逐次消去によって求まる戦略の組合せも支配戦略均衡であるが、ゲームの設定によっては上述した２つの方法では均衡を求めることができない。ナッシュ均衡の定義によれば他のプレイヤーの戦略を最適反応であると仮定したうえで自身の最適反応を求めればよいので、支配戦略均衡が存在しない純粋戦略ゲームにおいてもナッシュ均衡を見つけることができる。

たとえば上の3×3の標準形ゲームの (A₁, B₃) の利得を (4, 0) から (4, 5) に変えればどの戦略も逐次消去されず、支配戦略均衡が求まらないが、

Pa/Pb	B1	B2	B3
A1	5, 2	2, 4	4, 5
A2	4, 6	3, 6	2, 5
A3	3, 3	1, 2	7, 2

相手の戦略を所与としたときに最大利得をもたらす戦略（最適反応）を組み合わせていくと、唯一 (A₂, B₂) が最適反応の組合せになっていることがわかる。従ってこのゲームには純粋戦略ナッシュ均衡が一組存在する。

混合戦略ゲームにおけるナッシュ均衡

混合戦略ゲームとは、参加者が行動を確率的に選ぶような戦略をとることでナッシュ均衡に到達する非協力ゲームのことである。このようなゲームでは純粋戦略ナッシュ均衡が必ずしも存在せず、ナッシュ均衡は各参加者の行動確率の組として表される。有限の（=プレーヤーの数と各プレーヤーの戦略の数が有限の）混合戦略ゲームでは少なくとも1つのナッシュ均衡が存在することはナッシュの定理で証明されている（ナッシュは、この証明を角谷の不動点定理を応用することによって得た）。

以下では具体例を用いて混合戦略ナッシュ均衡を求めてみる。2人のプレイヤー P_a と P_b はそれぞれ2つの戦略から1つを選択するが、相手がどの戦略を選択するかはわからないため、各プレイヤーが確率的に相手の行動を予測する。すなわち P_a は相手 (P_b) が確率 q で B₁ を選択し、P_b は相手 (P_a) が確率 p で A₁ を選択すると予想しているとする。

Pa/Pb	B1 確率 q	B2 確率 (1 − q)
A1 確率 p	1, 2	0, 0
A2 確率 (1 − p)	0, 0	2, 1

この表のゲームにおいて P_a の得る利得の期待値は：

• A₁を選択：1 × q + 0 × (1 − q)
• A₂を選択：0 × q + 2 × (1 − q)

一方、 P_b の得る利得の期待値は：

• B₁を選択：2 × p + 0 × (1 − p)
• B₂を選択：0 × p + 1 × (1 − p)

ここで最適反応をとるとは相手の行動確率に関して期待利得がより大きな戦略を選ぶことであるから、以下のように各プレイヤーの行動をまとめることができる。

Pa/Pb	p > 1/3	p < 1/3
q > 2/3	p=1, q=1	p=1, q=0
q < 2/3	p=0, q=1	p=0, q=0

なお、p=1/3, q=2/3 のときはそれぞれ期待利得が相手の行動に関して無差別なので、平面上に各軸を行動確率︵pとq︶として各プレイヤーの最適反応をグラフで表わすことができる︵これを均衡経路という︶。混合戦略ナッシュ均衡とはこの図における均衡経路の交点であり、従って混合戦略ナッシュ均衡においてP_a は (1/3, 2/3) を選択し、P_b は (2/3, 1/3) を選択する。

ここで分析したゲームは一般的に両性の争いと呼ばれるものである。

参考文献

論文

●Nash, J. (January 15, 1950). “Equilibrium Points in n-Person Games”. Proc. Natl. Acad. Sci. U.S.A. (NAS) 36 (1): 48–49. Bibcode: 1950PNAS...36...48N. doi:10.1073/pnas.36.1.48. ISSN 0027-8424. JSTOR 88031. LCCN 16-10069. OCLC 43473694. PMC 1063129. PMID 16588946. http://www.sscnet.ucla.edu/polisci/faculty/chwe/austen/nash1950.pdf. 

●Glicksberg, I. L. (February 1952). “A Further Generalization of the Kakutani Fixed-Point Theorem, with Applications to Nash Equilibrium Points”. Proc. Am. Math. Soc. (AMS) 3 (1): 170-174. doi:10.2307/2032478. ISSN 0002-9939. JSTOR 2032478. LCCN 51-3937. OCLC 1480367. http://www.ams.org/journals/proc/1952-003-01/S0002-9939-1952-0046638-5/S0002-9939-1952-0046638-5.pdf. 

書籍

●ロバート・ギボンズ 著、福岡 正夫・須田 伸一 訳﹃経済学のためのゲーム理論入門﹄創文社、1995年7月。ASIN 442385080X。ISBN 978-4423850800。 NCID BN12843079。OCLC 673606398。全国書誌番号:95072397。 

●ジョン・フォン・ノイマン、オスカー・モルゲンシュテルン 著、阿部修一・銀林浩・下島英忠・橋本和美・宮本敏雄 訳﹃ゲームの理論と経済行動﹄筑摩書房︿ちくま学芸文庫﹀、2009年5月11日。ASIN 4480092110。ISBN 978-4-480-09211-3。 NCID BA89979297。OCLC 326519825。全国書誌番号:21624029。 

●Aviad Rubinstein: "Hardness of Approximation Between P and NP", ACM, ISBN 978-1-947487-23-9 (May 2019), doi:10.1145/3241304.　※ナッシュ均衡を求める計算量的な困難さを扱った書籍である。

関連項目

●ゲーム理論

●パレート最適

●囚人のジレンマ

外部リンク

●日本大百科全書(ニッポニカ)﹃ナッシュ均衡﹄ - コトバンク