出典は列挙するだけでなく、脚注などを用いてどの記述の情報源であるかを明記してください。記事の信頼性向上にご協力をお願いいたします。(2016年5月)
ナッシュ均衡(ナッシュきんこう、英: Nash equilibrium)は、ゲーム理論における非協力ゲームの解の一種であり、いくつかの解の概念の中で最も基本的な概念である。数学者のジョン・フォーブス・ナッシュにちなんで名付けられた。
ナッシュ均衡は、他のプレーヤーの戦略を所与とした場合、どのプレーヤーも自分の戦略を変更することによってより高い利得を得ることができない戦略の組み合わせである。ナッシュ均衡の下では、どのプレーヤーも戦略を変更する誘因を持たない。
ナッシュ均衡は必ずしもパレート効率的ではない。その代表例が囚人のジレンマである。 形式的な定義は次の通りである。標準型ゲーム G = (N, S, u) (N はプレーヤーの集合、 S = ∏ i ∈ N S i {\displaystyle S=\prod _{i\in N}S_{i}} は戦略の組の集合、 u = ( u i ) i ∈ N ( u i : S → R ) {\displaystyle u=(u_{i})_{i\in N}\;(u_{i}:S\rightarrow \mathbb {R} )} は効用の組)において、戦略の組 s ∗ ∈ S {\displaystyle s^{*}\in S} がナッシュ均衡であるとは、全てのプレーヤー i ∈ N {\displaystyle i\in N} と、全ての s i ∈ S i {\displaystyle s_{i}\in S_{i}} に対して、 u i ( s ∗ ) ≥ u i ( s i , s − i ∗ ) {\displaystyle u_{i}(s^{*})\geq u_{i}(s_{i},s_{-i}^{*})} を満たすことである。 ただし、s−i は、i 以外のプレーヤーの戦略の組をさす。 純粋戦略ゲーム
定義
純粋戦略ゲームにおけるナッシュ均衡
支配戦略均衡「囚人のジレンマ」も参照
Pa/PbB1B2
A15, 22, 4
A24, 61, 6
まず Pa の利得に注目すると、Pb がどちらの戦略を選ぼうが、Pa は A1 戦略を選んだ方がより大きな利得を得ることができる。このような関係が成り立つとき、A1 は強支配戦略
であると表現する。支配するとは、ある戦略を選ぶことが他方の戦略を選ぶより有利であるという意味である。次に Pb の利得に注目すると、Pa がどちらに戦略を選んでも、B2 戦略を選んだ方が B1 戦略のとき以上の利得を得られる。Pa が A2 戦略を選んだ場合には B1 と B2 は同等になるので、このような関係のとき B2 は弱支配戦略であるという。
結果として、Pa にとっての最適戦略は A1、Pb にとっての最適戦略は B2 となり、両者ともここから戦略を変更しても利得は減る。この組み合わせ (A1, B2) が支配戦略均衡となる。
Pa、Pb が (A1, B2) という戦略をとった場合、Paは戦略を変更して A2 をとれば利得が 2 から 1 へ減少してしまうため、戦略を変更する誘因を持たない。同様に Pb も、戦略を変更して B1 をとれば利得が 4 から 2 へ減少してしまうため、戦略を変更する誘因を持たない。従ってこの例では支配戦略均衡はナッシュ均衡である。
なお、Pa、Pb が (A2, B1) という戦略をとった場合の利得は (4, 6) となり、ナッシュ均衡における利得と比べて Pa、Pb ともにより大きな利得を得ることができる。この場合、Pa がより大きな 5 の利得を得るため A1 に戦略を変更する誘因を持つため、ナッシュ均衡ではない。すなわち、このゲームは囚人のジレンマゲームである。また、(A1, B2) から (A2, B1) への戦略変更は、パレート改善であり、ナッシュ均衡 (A1, B2) はパレート効率的ではない。 相手の戦略によってどの戦略が最も大きな利得を出すかが変化する場合、他の戦略すべてを支配できる戦略が存在しない場合がある。そのような場合、他から支配されている戦略(被支配戦略)を消去していくことで残った戦略の組み合わせを支配戦略均衡と定義できる。支配戦略によってナッシュ均衡が定義できる場合、それは消去によって定義されたものと一致する。 Pa/PbB1B2B3 B3 は B2 に支配されているため、B3 を消去。 Pa/PbB1B2 A3 は A2 に支配されているため A3 を消去。 Pa/PbB1B2 B1 は B2 に支配されているため B1 を消去。 Pa/PbB2 支配戦略均衡は (A2, B2)。 他のプレイヤーの戦略によらず最大利得をもたらす戦略の組合せも被支配戦略の逐次消去によって求まる戦略の組合せも支配戦略均衡であるが、ゲームの設定によっては上述した2つの方法では均衡を求めることができない。ナッシュ均衡の定義によれば他のプレイヤーの戦略を最適反応であると仮定したうえで自身の最適反応を求めればよいので、支配戦略均衡が存在しない純粋戦略ゲームにおいてもナッシュ均衡を見つけることができる。 たとえば上の3×3の標準形ゲームの (A1, B3) の利得を (4, 0) から (4, 5) に変えればどの戦略も逐次消去されず、支配戦略均衡が求まらないが、 Pa/PbB1B2B3 相手の戦略を所与としたときに最大利得をもたらす戦略(最適反応)を組み合わせていくと、唯一 (A2, B2) が最適反応の組合せになっていることがわかる。従ってこのゲームには純粋戦略ナッシュ均衡が一組存在する。 混合戦略ゲーム 以下では具体例を用いて混合戦略ナッシュ均衡を求めてみる。2人のプレイヤー Pa と Pb はそれぞれ2つの戦略から1つを選択するが、相手がどの戦略を選択するかはわからないため、各プレイヤーが確率的に相手の行動を予測する。すなわち Pa は相手 (Pb) が確率 q で B1 を選択し、Pb は相手 (Pa) が確率 p で A1 を選択すると予想しているとする。 Pa/PbB1 この表のゲームにおいて Pa の得る利得の期待値は: 一方、 Pb の得る利得の期待値は: ここで最適反応をとるとは相手の行動確率に関して期待利得がより大きな戦略を選ぶことであるから、以下のように各プレイヤーの行動をまとめることができる。 Pa/Pbp > 1/3p < 1/3 なお、p=1/3, q=2/3 のときはそれぞれ期待利得が相手の行動に関して無差別なので、平面上に各軸を行動確率(pとq)として各プレイヤーの最適反応をグラフで表わすことができる(これを均衡経路という)。混合戦略ナッシュ均衡とはこの図における均衡経路の交点であり、従って混合戦略ナッシュ均衡において Pa は (1/3, 2/3) を選択し、Pb は (2/3, 1/3) を選択する。 ここで分析したゲームは一般的に両性の争い
逐次消去による均衡
A15, 22, 44, 0
A24, 63, 62, 5
A33, 31, 27, 2
A15, 22, 4
A24, 63, 6
A33, 31, 2
A15, 22, 4
A24, 63, 6
A12, 4
A23, 6
純粋戦略ナッシュ均衡
A15, 22, 44, 5
A24, 63, 62, 5
A33, 31, 27, 2
混合戦略ゲームにおけるナッシュ均衡
確率 qB2
確率 (1 − q)
A1
確率 p1, 20, 0
A2
確率 (1 − p)0, 02, 1
A1を選択:1 × q + 0 × (1 − q)
A2を選択:0 × q + 2 × (1 − q)
B1を選択:2 × p + 0 × (1 − p)
B2を選択:0 × p + 1 × (1 − p)
q > 2/3p=1, q=1p=1, q=0
q < 2/3p=0, q=1p=0, q=0
参考文献
論文
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. .mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation.cs-ja1 q,.mw-parser-output .citation.cs-ja2 q{quotes:"「""」""『""』"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free a,.mw-parser-output .citation .cs1-lock-free a{background:url("//upload.wikimedia.org/wikipedia/commons/6/65/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited a,.mw-parser-output .id-lock-registration a,.mw-parser-output .citation .cs1-lock-limited a,.mw-parser-output .citation .cs1-lock-registration a{background:url("//upload.wikimedia.org/wikipedia/commons/d/d6/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription a,.mw-parser-output .citation .cs1-lock-subscription a{background:url("//upload.wikimedia.org/wikipedia/commons/a/aa/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("//upload.wikimedia.org/wikipedia/commons/4/4c/Wikisource-logo.svg")right 0.1em center/12px no-repeat}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:#d33}.mw-parser-output .cs1-visible-error{color:#d33}.mw-parser-output .cs1-maint{display:none;color:#3a3;margin-left:0.3em}.mw-parser-output .cs1-format{font-size:95%}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}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.