ナッシュ均衡

ナッシュ均衡の最新ニュースをまとめて検索！

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

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

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

[編集] 定義

形式的な定義は次の通りである。標準型ゲーム G = (N, S, u) （N はプレーヤーの集合、 $S = \prod_{i \in N} S_i$ は戦略の組の集合、 $u = (u_i)_{i \in N} \; (u_i : S \rightarrow \mathbb{R})$ は効用の組）において、戦略の組 $s^* \in S$ がナッシュ均衡であるとは、全てのプレーヤー $i \in N$ と、全ての $s_i \in 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 の利得である。

P_a/P_b	B₁	B₂
A₁	5, 2	2, 4
A₂	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₂) はパレート効率的ではない。

[編集] 逐次消去によるナッシュ均衡

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

P_a/P_b	B₁	B₂	B₃
A₁	5, 2	2, 4	4, 0
A₂	4, 6	3, 6	2, 5
A₃	3, 3	1, 2	7, 2

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

P_a/P_b	B₁	B₂
A₁	5, 2	2, 4
A₂	4, 6	3, 6
A₃	3, 3	1, 2

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

P_a/P_b	B₁	B₂
A₁	5, 2	2, 4
A₂	4, 6	3, 6

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

P_a/P_b	B₂
A₁	2, 4
A₂	3, 6

ナッシュ均衡は (A₂, B₂)。

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

混合戦略ゲームとは、参加者が各行動を選ぶ確率を戦略とするような非協力ゲームのことである。この場合、ナッシュ均衡は各参加者の行動確率の組として表される。有限ゲーム (プレーヤーの数と各プレーヤーの戦略の数が有限のゲーム) は少なくとも 1 つのナッシュ均衡を (混合戦略ゲームで考えれば) 持つことが証明されている (ナッシュの定理。ナッシュは、この証明を角谷の不動点定理を応用することによって得た）。

P_a/P_b	B₁ 確率 q	B₂ 確率 (1 - q)
A₁ 確率 p	1, 2	0, 0
A₂ 確率 (1 - p)	0, 0	2, 1

この表のゲームの場合は P_a の得る利得の期待値は：

1・pq + 2・(1 - p)(1 - q) = 3pq - 2p - 2q + 2 = (3q - 2)p + 2(1 - q)

である。これを p の関数だと考えると：

q > 2/3 なら：単調増加の直線グラフなので、期待値の最大値は p = 1 のとき q
q < 2/3 なら：単調減少の直線グラフなので、期待値の最大値は p = 0 のとき 2 - 2q
q = 2/3 なら：期待値は一定で 2/3

となる。

P_b の得る利得の期待値の最大値も、p によって同様に決定される。この二つのグラフの交点がナッシュ均衡となる。このゲームの場合は (2/3, 1/3) がそうである。

最終更新 2009年11月6日 (金) 19:36 （日時は個人設定で未設定ならばUTC）。
【ナッシュ均衡】変更履歴