「非協力ゲーム理論」の版間の差分

提供: ORWiki
ナビゲーションに移動 検索に移動
 
(3人の利用者による、間の3版が非表示)
1行目: 1行目:
 
'''【ひきょうりょくげーむりろん (noncooperative game theory)】'''
 
'''【ひきょうりょくげーむりろん (noncooperative game theory)】'''
 +
 +
=== 概要 ===
  
 
プレイヤー間で拘束的な協定を結ぶことができないゲームを非協力ゲームといい, 非協力ゲームを扱う理論を非協力ゲーム理論という. 非協力ゲームでは, 提携は形成されない. 非協力ゲーム理論はナッシュ (J.F. Nash) が創始した.
 
プレイヤー間で拘束的な協定を結ぶことができないゲームを非協力ゲームといい, 非協力ゲームを扱う理論を非協力ゲーム理論という. 非協力ゲームでは, 提携は形成されない. 非協力ゲーム理論はナッシュ (J.F. Nash) が創始した.
 +
 +
=== 詳説 ===
 +
 +
 [[プレイヤー]]間で拘束的な協定をむすぶことが可能なゲームを[[協力ゲーム]], そうでないゲームを非協力ゲームといい, 非協力ゲームを扱う理論を[[非協力ゲーム理論]] (noncooperative game theory) という. 拘束的協定とは, ゲームの外部から付与された拘束力をともなう協定であって, たとえば違反した場合にしかるべきペナルティが課せられるために従わざるをえないような協定である. それゆえ, 協力ゲームでは拘束的協定のもとでプレイヤーたちは [[提携]] を組んで行動することができるが, 非協力ゲームではプレイヤーたちは個々独立に意思決定し, 束縛されずに自由なコミュニケーションや取り決めをすることが許されている. これらのことは普通モデルに明記されないので注意が必要である.
 +
 +
 フォンノイマン (J. von Neumann) が1928年に[[ミニマックス定理 (ゲーム理論における)|ミニマックス定理]]を証明することによって解決した, ゲーム理論の出発点に位置する[[2人ゼロ和ゲーム]]は最もよく知られた非協力ゲームであり, 勝つか負けるかという完全な利害対立状況を記述するものである([8]). これに対して, ナッシュ (J. F. Nash) が1950年に創始した一般の非協力ゲームでは, 有名な[[囚人のジレンマ]]などにみられるように, 利害は完全に対立するとはかぎらない. そのためゼロ和という条件に縛られないので, 今日, 経済学を中心とする社会科学や生物学などに広く応用されている. 非協力ゲーム理論とは, 普通, このナッシュの理論をいう([5]).
 +
 +
 ナッシュはさらに, 合理的主体間の交渉や契約などの協力行動, つまり, 協力ゲームは, 一般に適切な非協力ゲームに還元して分析するべきであるという方法論上の提案をしたが, これは現在[[ナッシュプログラム]] (Nash program) として知られている([5]). 1994年のノーベル経済学賞は, あとで述べるようにこの方法論が経済分析に果たした貢献が評価されて, ナッシュ, ハルサーニ (J. C. Harsanyi) およびゼルテン (R.Selten) に対して与えられたものである.
 +
 +
 非協力ゲームは,  <math>G=(N; S_1,\ldots ,S_n; u_1,\ldots ,u_n)\, </math>  のように形式的に表現することができる. このように表現されたゲームを[[戦略形ゲーム]]という. ここに<math>N\, </math>はプレイヤーの集合, <math>S_i\, </math>はプレイヤー<math>i\, </math>の[[戦略 (ゲーム理論における)|戦略]]の集合, <math>u_i\, </math>は<math>S=S_1 \times \cdots \times S_n\, </math>上で定義されたプレイヤー<math>i\, </math>の[[フォンノイマン・モルゲンシュテルン効用関数]]である.  <math>N\, </math>とすべての<math>S_i\, </math>が有限集合であるとき, ゲーム<math>G\, </math>を有限ゲーム, そうでないとき無限ゲームという. また, <math>N=\{1,2\}, \ u_1 (s)+u_2 (s) = 0\ \mbox{ for all } s=(s_1, s_2) \in S_1 \times S_2\, \, </math> , が成り立つゲーム<math>G\, </math>が[[2人ゼロ和ゲーム]]である.
 +
 +
 非協力ゲームの[[ナッシュ均衡]] (Nash equilibrium) とは, 次のような[[混合戦略]]の組である. <math>\Delta S_i\, </math>でプレイヤー<math>i\, </math>の混合戦略の集合をあらわし, 混合戦略の組<math>x=(x_1, \ldots , x_n) \in \Delta S= \Delta S_1 \times\cdots \times \Delta S_n\, </math> のもとでのプレイヤー<math>i\, </math>の効用の期待値(期待効用)を<math>U_i(x)\, </math>であらわそう. このとき, 混合戦略の組<math>x^*=(x^{*}_{1}, \ldots , x^*_n ) \in \Delta S\, </math>がナッシュ均衡であるとは, すべてのプレイヤーiに対して
 +
 +
 +
<center>
 +
<math>U_i (x^*) \ge U_i (x^*_1 ,\ldots , x^*_{i-1}, x_i, x^*_{i+1},\ldots , x^*_n )\ \mbox{ for all } x_i \in \Delta S_i\, </math>
 +
</center>
 +
 +
 +
となることである. このように, ナッシュ均衡においては, 各プレイヤーの戦略は他のすべてのプレイヤーの戦略に対する最適な反応であり, 独立に行動する各プレイヤーは, 外的な拘束力がなくても, 他の戦略に切り替えることなくそこに留まることになる.
 +
 +
 混合戦略まで考えた有限ゲームや, 各<math>S_i\, </math> がコンパクト凸集合で, 各効用関数<math>u_i\, </math> が連続かつ<math>x_i\, </math>に関して準凹であるような無限ゲームがナッシュ均衡をもつことは, ブラウワーや角谷の不動点定理によって証明することができる. また, 2人ゼロ和ゲームのナッシュ均衡は, [[マックスミニ戦略]]と[[ミニマックス戦略]]の組であることも容易に確かめることができる. こうして, ナッシュによる均衡の存在定理は, [[ミニマックス定理 (ゲーム理論における)|ミニマックス定理]]の拡張になっていることがわかる.
 +
 +
 非協力ゲームの研究はその後, シャープレイ (L. S. Shapley) の[[確率ゲーム]] (stochastic game) ([7])やキューン (H. W. Kuhn)の[[展開形ゲーム]] ([4]), 無限回[[繰り返しゲーム]] (repeated game) の[[フォーク定理]] (folk theorem) ([1]), 連続時間上の動学を考える[[微分ゲーム]] (differential game) などの理論展開に続いて, ハルサーニによる[[不完備情報ゲーム]] (game with incomplete information) への拡張([2])やゼルテンの[[完全均衡]] (perfect equilibrium) ([6])などを産出した. さらに80年代に入ってからの[[逐次均衡]] (sequential equilibrium) ([3])という技術的展開も加わって, 産業組織論や情報経済学などの経済学の分野に新しい分析方法を確立し, 重要な研究領域を切り開くことになった.
 +
 +
 また, [[進化的安定戦略]]の名で知られる戦略は, 進化生物学においてナッシュ均衡のひとつの精緻化として生まれたものであり, 逆にこれに影響されて80年代に発展したのが[[進化ゲーム理論]]と呼ばれる非協力ゲーム理論である. 進化ゲーム理論におけるプレイヤーは, 通常のゲームにおけるように, 完全な合理性を備えた意思決定主体ではなく, むしろ思考せずにあらかじめ決められた行動のみを一定の手順でとるオートマトン, ないしアルゴリズムである. 自然界において, 特定の遺伝子が淘汰されずに優勢になっていくように, 進化ゲームでは進化的に安定なアルゴリズム(戦略)が動学的な均衡点になることが知られている. このように, 進化ゲームは合理的推論によらない均衡選択の可能性を示しており, これがきっかけとなって, 90年代以降, プレイヤーの[[限定合理性]] (bounded rationality) と, プレイヤーの[[学習 (ゲーム理論における)|学習]]による均衡選択の研究が精力的になされるようになった. この限定合理的な行動による均衡選択というアイディアの原型は, 実はナッシュ自身が彼の最初の論文の削除された章で述べていたことが知られている.
 +
 +
 +
 +
----
 +
'''参考文献'''
 +
 +
[1] R. Axcelrod, ''The Evolution of Cooperation'', Basic Books, 1984.
 +
 +
[2] J. C. Harsanyi, "Games with Incomplete Information Played by `Bayesian' Players, parts I,II and III," ''Management Science'', '''14''' (1967-8), 159-182, 320-334, 486-502.
 +
 +
[3] D. M. Kreps and R. Wilson, "Sequential Equilibria," ''Econometrica'', '''50''' (1982), 863-894.
 +
 +
[4] H. W. Kuhn, "Extensive Games and the Problem of Information," in ''Contributions to the Theory of Games II,  Annals of Mathematics Studies'', '''28''', H. W. Kuhn and A. W. Tucker,  eds., Princeton University Press, 1953.
 +
 +
[5] J. F. Nash, Jr, ''Essays on Game Theory'', Edward Elgar, 1996
 +
 +
[6] R. C. Selten, "Reexamination of the Perfectness Concept for Equilibrium Points in Extensive Games," ''International Journal of Game Theory'', '''4''' (1975), 25-55.
 +
 +
[7] L. S. Shapley, "Stochastic Games," ''Proceedings of the National Academy of Sciences of the United States''}, '''39''' (1953), 1095-1100.
 +
 +
[8] J. von Neumann and O. Morgenstern, ''Theory of Games and Economic Behavior. 3rd ed.,'' Princeton University Press, 1953.
 +
 +
[[category:ゲーム理論|ひきょうりょくげーむりろん]]

2008年4月4日 (金) 10:30時点における最新版

【ひきょうりょくげーむりろん (noncooperative game theory)】

概要

プレイヤー間で拘束的な協定を結ぶことができないゲームを非協力ゲームといい, 非協力ゲームを扱う理論を非協力ゲーム理論という. 非協力ゲームでは, 提携は形成されない. 非協力ゲーム理論はナッシュ (J.F. Nash) が創始した.

詳説

 プレイヤー間で拘束的な協定をむすぶことが可能なゲームを協力ゲーム, そうでないゲームを非協力ゲームといい, 非協力ゲームを扱う理論を非協力ゲーム理論 (noncooperative game theory) という. 拘束的協定とは, ゲームの外部から付与された拘束力をともなう協定であって, たとえば違反した場合にしかるべきペナルティが課せられるために従わざるをえないような協定である. それゆえ, 協力ゲームでは拘束的協定のもとでプレイヤーたちは 提携 を組んで行動することができるが, 非協力ゲームではプレイヤーたちは個々独立に意思決定し, 束縛されずに自由なコミュニケーションや取り決めをすることが許されている. これらのことは普通モデルに明記されないので注意が必要である.

 フォンノイマン (J. von Neumann) が1928年にミニマックス定理を証明することによって解決した, ゲーム理論の出発点に位置する2人ゼロ和ゲームは最もよく知られた非協力ゲームであり, 勝つか負けるかという完全な利害対立状況を記述するものである([8]). これに対して, ナッシュ (J. F. Nash) が1950年に創始した一般の非協力ゲームでは, 有名な囚人のジレンマなどにみられるように, 利害は完全に対立するとはかぎらない. そのためゼロ和という条件に縛られないので, 今日, 経済学を中心とする社会科学や生物学などに広く応用されている. 非協力ゲーム理論とは, 普通, このナッシュの理論をいう([5]).

 ナッシュはさらに, 合理的主体間の交渉や契約などの協力行動, つまり, 協力ゲームは, 一般に適切な非協力ゲームに還元して分析するべきであるという方法論上の提案をしたが, これは現在ナッシュプログラム (Nash program) として知られている([5]). 1994年のノーベル経済学賞は, あとで述べるようにこの方法論が経済分析に果たした貢献が評価されて, ナッシュ, ハルサーニ (J. C. Harsanyi) およびゼルテン (R.Selten) に対して与えられたものである.

 非協力ゲームは, のように形式的に表現することができる. このように表現されたゲームを戦略形ゲームという. ここにはプレイヤーの集合, はプレイヤー戦略の集合, 上で定義されたプレイヤーフォンノイマン・モルゲンシュテルン効用関数である. とすべてのが有限集合であるとき, ゲームを有限ゲーム, そうでないとき無限ゲームという. また, , が成り立つゲーム2人ゼロ和ゲームである.

 非協力ゲームのナッシュ均衡 (Nash equilibrium) とは, 次のような混合戦略の組である. でプレイヤーの混合戦略の集合をあらわし, 混合戦略の組 のもとでのプレイヤーの効用の期待値(期待効用)をであらわそう. このとき, 混合戦略の組がナッシュ均衡であるとは, すべてのプレイヤーiに対して



となることである. このように, ナッシュ均衡においては, 各プレイヤーの戦略は他のすべてのプレイヤーの戦略に対する最適な反応であり, 独立に行動する各プレイヤーは, 外的な拘束力がなくても, 他の戦略に切り替えることなくそこに留まることになる.

 混合戦略まで考えた有限ゲームや, 各 がコンパクト凸集合で, 各効用関数 が連続かつに関して準凹であるような無限ゲームがナッシュ均衡をもつことは, ブラウワーや角谷の不動点定理によって証明することができる. また, 2人ゼロ和ゲームのナッシュ均衡は, マックスミニ戦略ミニマックス戦略の組であることも容易に確かめることができる. こうして, ナッシュによる均衡の存在定理は, ミニマックス定理の拡張になっていることがわかる.

 非協力ゲームの研究はその後, シャープレイ (L. S. Shapley) の確率ゲーム (stochastic game) ([7])やキューン (H. W. Kuhn)の展開形ゲーム ([4]), 無限回繰り返しゲーム (repeated game) のフォーク定理 (folk theorem) ([1]), 連続時間上の動学を考える微分ゲーム (differential game) などの理論展開に続いて, ハルサーニによる不完備情報ゲーム (game with incomplete information) への拡張([2])やゼルテンの完全均衡 (perfect equilibrium) ([6])などを産出した. さらに80年代に入ってからの逐次均衡 (sequential equilibrium) ([3])という技術的展開も加わって, 産業組織論や情報経済学などの経済学の分野に新しい分析方法を確立し, 重要な研究領域を切り開くことになった.

 また, 進化的安定戦略の名で知られる戦略は, 進化生物学においてナッシュ均衡のひとつの精緻化として生まれたものであり, 逆にこれに影響されて80年代に発展したのが進化ゲーム理論と呼ばれる非協力ゲーム理論である. 進化ゲーム理論におけるプレイヤーは, 通常のゲームにおけるように, 完全な合理性を備えた意思決定主体ではなく, むしろ思考せずにあらかじめ決められた行動のみを一定の手順でとるオートマトン, ないしアルゴリズムである. 自然界において, 特定の遺伝子が淘汰されずに優勢になっていくように, 進化ゲームでは進化的に安定なアルゴリズム(戦略)が動学的な均衡点になることが知られている. このように, 進化ゲームは合理的推論によらない均衡選択の可能性を示しており, これがきっかけとなって, 90年代以降, プレイヤーの限定合理性 (bounded rationality) と, プレイヤーの学習による均衡選択の研究が精力的になされるようになった. この限定合理的な行動による均衡選択というアイディアの原型は, 実はナッシュ自身が彼の最初の論文の削除された章で述べていたことが知られている.



参考文献

[1] R. Axcelrod, The Evolution of Cooperation, Basic Books, 1984.

[2] J. C. Harsanyi, "Games with Incomplete Information Played by `Bayesian' Players, parts I,II and III," Management Science, 14 (1967-8), 159-182, 320-334, 486-502.

[3] D. M. Kreps and R. Wilson, "Sequential Equilibria," Econometrica, 50 (1982), 863-894.

[4] H. W. Kuhn, "Extensive Games and the Problem of Information," in Contributions to the Theory of Games II, Annals of Mathematics Studies, 28, H. W. Kuhn and A. W. Tucker, eds., Princeton University Press, 1953.

[5] J. F. Nash, Jr, Essays on Game Theory, Edward Elgar, 1996

[6] R. C. Selten, "Reexamination of the Perfectness Concept for Equilibrium Points in Extensive Games," International Journal of Game Theory, 4 (1975), 25-55.

[7] L. S. Shapley, "Stochastic Games," Proceedings of the National Academy of Sciences of the United States}, 39 (1953), 1095-1100.

[8] J. von Neumann and O. Morgenstern, Theory of Games and Economic Behavior. 3rd ed., Princeton University Press, 1953.