ナッシュ均衡のソースを表示

{{参照方法|date=2016-5-30}}
'''ナッシュ均衡'''（ナッシュきんこう、{{lang-en-short|''Nash equilibrium''}}）は、[[ゲーム理論]]における[[非協力ゲーム]]の解の一種であり、いくつかの解の概念の中で最も基本的な概念である。数学者の[[ジョン・ナッシュ|ジョン・フォーブス・ナッシュ]]にちなんで名付けられた。

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

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

==定義==
形式的な定義は次の通りである。[[標準型ゲーム]] {{Math|''G'' {{=}} (''N'', ''S'', ''u'')}} （{{Mvar|N}} はプレーヤーの集合、<math>S=\prod_{i\in N}S_i</math> は戦略の組の集合、<math>u=(u_i)_{i \in N}\;(u_i:S\rightarrow\mathbb{R})</math> は効用の組）において、戦略の組 <math>s^*\in S</math> がナッシュ均衡であるとは、全てのプレーヤー <math>i\in N</math> と、全ての <math>s_i\in S_i</math> に対して、
:<math>u_i(s^*)\geq u_i(s_i, s^*_{-i})</math>
を満たすことである。

ただし、{{Math|''s''<sub>&minus;''i''</sub>}} は、{{Mvar|i}} 以外のプレーヤーの戦略の組をさす。

==純粋戦略ゲームにおけるナッシュ均衡==
===支配戦略均衡===
{{see also|囚人のジレンマ}}
[[純粋戦略ゲーム]] ({{en|Pure strategy game}}) とは、参加者 (プレーヤー) が必ずどれかの戦略を選ぶゲームである。例えば、以下の表は、二人のプレーヤー P<sub>a</sub> と P<sub>b</sub> がそれぞれ戦略（A<sub>1</sub> または A<sub>2</sub>）と（B<sub>1</sub> または B<sub>2</sub>）を選べるときの、それぞれの利得を示す。並んだ数字の左側は P<sub>a</sub> の利得、右側は P<sub>b</sub> の利得である。
{|class="wikitable" style="margin: auto;"
|-
|P<sub>a</sub>/P<sub>b</sub>||B<sub>1</sub>||B<sub>2</sub>
|-
|A<sub>1</sub>||5, 2||2, 4
|-
|A<sub>2</sub>||4, 6||1, 6
|}
まず P<sub>a</sub> の利得に注目すると、P<sub>b</sub> がどちらの戦略を選ぼうが、P<sub>a</sub> は A<sub>1</sub> 戦略を選んだ方がより大きな利得を得ることができる。このような関係が成り立つとき、A<sub>1</sub> は[[強支配戦略]]であると表現する。'''支配'''するとは、ある戦略を選ぶことが他方の戦略を選ぶより有利であるという意味である。

次に P<sub>b</sub> の利得に注目すると、P<sub>a</sub> がどちらに戦略を選んでも、B<sub>2</sub> 戦略を選んだ方が B<sub>1</sub> 戦略のとき以上の利得を得られる。P<sub>a</sub> が A<sub>2</sub> 戦略を選んだ場合には B<sub>1</sub> と B<sub>2</sub> は同等になるので、このような関係のとき B<sub>2</sub> は[[弱支配戦略]]であるという。

結果として、P<sub>a</sub> にとっての最適戦略は A<sub>1</sub>、P<sub>b</sub> にとっての最適戦略は B<sub>2</sub> となり、両者ともここから戦略を変更しても利得は減る。この組み合わせ (A<sub>1</sub>, B<sub>2</sub>) が'''支配戦略均衡'''となる。

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

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

===逐次消去による均衡===
相手の戦略によってどの戦略が最も大きな利得を出すかが変化する場合、他の戦略すべてを支配できる戦略が存在しない場合がある。そのような場合、他から支配されている戦略（被支配戦略）を消去していくことで残った戦略の組み合わせを支配戦略均衡と定義できる。支配戦略によってナッシュ均衡が定義できる場合、それは消去によって定義されたものと一致する。
{|class="wikitable" style="margin: auto;"
|-
|P<sub>a</sub>/P<sub>b</sub>||B<sub>1</sub>||B<sub>2</sub>||B<sub>3</sub>
|-
|A<sub>1</sub>||5, 2||2, 4||4, 0
|-
|A<sub>2</sub>||4, 6||3, 6||2, 5
|-
|A<sub>3</sub>||3, 3||1, 2||7, 2
|}
B<sub>3</sub> は B<sub>2</sub> に<!--B<sub>1</sub> にも?-->支配されているため、B<sub>3</sub> を消去。
{|class="wikitable" style="margin: auto;"
|-
|P<sub>a</sub>/P<sub>b</sub>||B<sub>1</sub>||B<sub>2</sub>
|-
|A<sub>1</sub>||5, 2||2, 4
|-
|A<sub>2</sub>||4, 6||3, 6
|-
|A<sub>3</sub>||3, 3||1, 2
|}
A<sub>3</sub> は A<sub>2</sub> に<!--A<sub>1</sub> にも?-->支配されているため A<sub>3</sub> を消去。
{|class="wikitable" style="margin: auto;"
|-
|P<sub>a</sub>/P<sub>b</sub>||B<sub>1</sub>||B<sub>2</sub>
|-
|A<sub>1</sub>||5, 2||2, 4
|-
|A<sub>2</sub>||4, 6||3, 6
|}
B<sub>1</sub> は B<sub>2</sub> に支配されているため B<sub>1</sub> を消去。
{|class="wikitable" style="margin: auto;"
|-
|P<sub>a</sub>/P<sub>b</sub>||B<sub>2</sub>
|-
|A<sub>1</sub>||2, 4
|-
|A<sub>2</sub>||3, 6
|}
支配戦略均衡は (A<sub>2</sub>, B<sub>2</sub>)。

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

たとえば上の3&times;3の標準形ゲームの (A<sub>1</sub>, B<sub>3</sub>) の利得を (4, 0) から (4, 5) に変えればどの戦略も逐次消去されず、支配戦略均衡が求まらないが、
{|class="wikitable" style="margin: auto;"
|-
|P<sub>a</sub>/P<sub>b</sub>||B<sub>1</sub>||B<sub>2</sub>||B<sub>3</sub>
|-
|A<sub>1</sub>||5, 2||2, 4||4, 5
|-
|A<sub>2</sub>||4, 6||3, 6||2, 5
|-
|A<sub>3</sub>||3, 3||1, 2||7, 2
|}

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

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

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

{|class="wikitable" style="margin: auto;"
|-
|P<sub>a</sub>/P<sub>b</sub>||B<sub>1</sub><br />確率 ''q''||B<sub>2</sub><br />確率 (1 &minus; ''q'')
|-
|A<sub>1</sub><br />確率 ''p''||1, 2||0, 0
|-
|A<sub>2</sub><br />確率 (1 &minus; ''p'')||0, 0||2, 1
|}
この表のゲームにおいて P<sub>a</sub> の得る利得の[[期待値]]は：

* A<sub>1</sub>を選択：{{Math|1 &times; ''q'' + 0 &times; (1 &minus; ''q'')}}
* A<sub>2</sub>を選択：{{Math|0 &times; ''q'' + 2 &times; (1 &minus; ''q'')}}

一方、 P<sub>b</sub> の得る利得の[[期待値]]は：

* B<sub>1</sub>を選択：{{Math|2 &times; ''p'' + 0 &times; (1 &minus; ''p'')}}
* B<sub>2</sub>を選択：{{Math|0 &times; ''p'' + 1 &times; (1 &minus; ''p'')}}

ここで最適反応をとるとは相手の行動確率に関して期待利得がより大きな戦略を選ぶことであるから、以下のように各プレイヤーの行動をまとめることができる。
{|class="wikitable" style="margin: auto;"
|-
|P<sub>a</sub>/P<sub>b</sub>||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<sub>a</sub> は (1/3, 2/3) を選択し、P<sub>b</sub> は (2/3, 1/3) を選択する。

ここで分析したゲームは一般的に{{仮リンク|両性の争い|en|Battle of the sexes (game theory)}}と呼ばれるものである。

== 参考文献 ==
=== 論文 ===
* {{Cite journal|first=J.|last=Nash|authorlink=ジョン・ナッシュ|title=Equilibrium Points in n-Person Games|date=January 15, 1950|publisher=[[米国科学アカデミー|NAS]]|journal=[[米国科学アカデミー紀要|Proc. Natl. Acad. Sci. U.S.A.]]|url=http://www.sscnet.ucla.edu/polisci/faculty/chwe/austen/nash1950.pdf|volume=36|issue=1|pages=48–49|issn=0027-8424|lccn=16010069|oclc=43473694|jstor=88031|pmid=16588946|pmc=1063129|bibcode=1950PNAS...36...48N|doi=10.1073/pnas.36.1.48|ref=harv}}
* {{Cite journal|first=I. L.|last=Glicksberg|title=A Further Generalization of the Kakutani Fixed-Point Theorem, with Applications to Nash Equilibrium Points|url=http://www.ams.org/journals/proc/1952-003-01/S0002-9939-1952-0046638-5/S0002-9939-1952-0046638-5.pdf|publisher=[[アメリカ数学会|AMS]]|journal={{enlink|Proceedings of the American Mathematical Society|Proc. Am. Math. Soc.|p=off|s=off}}|volume=3|issue=1|month=February|year=1952|pages=170-174|issn=0002-9939|lccn=51003937|oclc=1480367|jstor=2032478|doi=10.2307/2032478|ref=harv}}

=== 書籍 ===
* {{cite book|和書|title=経済学のためのゲーム理論入門|author=ロバート・ギボンズ|translator=[[福岡正夫|福岡 正夫]]・須田 伸一|publisher=[[創文社]]|date=1995-07|id={{全国書誌番号|95072397}}|isbn=978-4423850800|ncid=BN12843079|oclc=673606398|asin=442385080X|ref=ギボンズ(1995)}}
* {{Cite book|和書|author=ジョン・フォン・ノイマン|authorlink=ジョン・フォン・ノイマン|author2=オスカー・モルゲンシュテルン|authorlink2=オスカー・モルゲンシュテルン|translator=阿部修一・[[銀林浩]]・下島英忠・橋本和美・宮本敏雄|date=2009-05-11|title=ゲームの理論と経済行動|publisher=[[筑摩書房]]|series=[[ちくま学芸文庫]]|id={{全国書誌番号|21624029}}|isbn=978-4-480-09211-3|ncid=BA89979297|oclc=326519825|asin=4480092110|ref=NM(2009)}}
* Aviad Rubinstein: "Hardness of Approximation Between P and NP", ACM, ISBN 978-1-947487-23-9 (May 2019), {{doi|10.1145/3241304}}.　※ナッシュ均衡を求める計算量的な困難さを扱った書籍である。

==関連項目==
* [[ゲーム理論]]
* [[パレート最適]]
* [[囚人のジレンマ]]

== 外部リンク ==
* {{Kotobank|2=[[日本大百科全書]](ニッポニカ)}}

{{ゲーム理論}}
{{Normdaten}}
{{DEFAULTSORT:なつしゆきんこう}}
[[Category:ゲーム理論]]
[[Category:不動点]]
[[Category:決定理論]]
[[Category:数学に関する記事]]
[[Category:経済学のエポニム]]
[[Category:ノーベル経済学賞]]