何をする手法か?
ナッシュ均衡(Nash Equilibrium)とは、どのプレイヤーも一方的に戦略を変更することで利得を改善できないような、ゲーム理論における解概念である。1950年にジョン・ナッシュによって形式化された。Lemke-Howsonアルゴリズムは、戦略多面体の完全にラベル付けされた頂点ペアを特定することにより、二行列ゲームにおける均衡を計算で見つける。
手法の背後にある直感
ナッシュ均衡では、各プレイヤーの戦略は他の全てのプレイヤーの戦略に対する最善応答となっている。両プレイヤーが互いの戦略を知っている状況を想像すると、どちらも変更したくないだろう。なぜなら、変更すると損をするだけだからである。Lemke-Howsonアルゴリズムは、ゲーム多面体の幾何学的性質を利用し、ラベル(満たされていない制約)を追跡し、頂点をピボット移動させていくことで、完全にラベル付けされたペアが見つかるまで探索を続ける。これは、両プレイヤーが有利な逸脱をしない構成である。
歴史学
ジョン・ナッシュは1950年の博士論文で、全ての有限ゲームは少なくとも1つの混合戦略ナッシュ均衡を持つことを証明した。1964年にLemkeとHowsonは、これらの均衡を見つけるための最初の構成的アルゴリズムを発表し、ナッシュの存在証明を実用的な計算方法に変換した。彼らの研究は、計算ゲーム理論とアルゴリズム経済学の基礎となった。
使うべき場面
プレイヤーが2人で離散的な戦略空間を持つゲームを研究する場合、あるいは完全混合均衡を探す場合に、ナッシュ均衡分析を使用する。戦略的相互作用が最も重要となる競争、交渉、調整問題のモデル化に適している。Lemke-Howson法は、非退化な二行列ゲームに最も適している。退化ケースでは、記号計算や摂動が必要になる場合がある。
限界と注意点
- 二プレイヤーゲーム(二行列ゲーム)に限定される。nプレイヤーゲームへの拡張はNP困難である
- 複数の進入ピボットが可能な退化ゲームでは失敗するか、非効率になる
- 1つの均衡しか見つからない場合がある。非ゼロサムゲームでは複数の均衡が存在することが多い
- 動的ゲームや展開形ゲームを、再定式化なしに直接扱えない
出典に示された条件は、独立した科学的レビューや分析エンジンによる検証の代わりにはなりません。
強み
- 有限な二行列ゲームにおけるナッシュ均衡を見つけるための計算効率が高い
- 非退化ゲームにおける完全にラベル付けされた頂点ペアへの収束を保証する
- 組み合わせ幾何学とゲーム理論を結びつける理論的基盤を提供する
- 混合戦略均衡に適用可能であり、これは純粋戦略の結果よりもしばしば現実的である
応用
- 経済学:寡占競争や市場における価格設定行動のモデル化
- オークションとメカニズム設計:第一価格入札や封印入札オークションにおける入札戦略の分析
- サイバーセキュリティ:ネットワークセキュリティゲームにおける攻撃者・防御者の均衡予測
- 野生生物学:捕食者・被食者相互作用における進化的に安定な戦略の分析
使い方
使い方
二行列ゲームを、各プレイヤーの最善応答条件を表す2つの線形相補問題(LCP)に変換する。
プレイヤーのいずれかのインセンティブ制約が満たされていないかに基づいて、戦略多面体の辺と頂点にラベルを割り当てる。
全要素が1の頂点(完全にラベル付けされた状態)から開始し、シンプレックス法に似たピボット操作を実行して多面体を移動させ、ラベルを除去・追加していくことで、完全にラベル付けされたペアを発見する。
他のプレイヤーの戦略が与えられた場合に、どちらのプレイヤーも利得を改善できないことを確認することで、両プレイヤーの戦略が相互の最善応答を形成していることを検証する。
よくある落とし穴
- 一意の均衡が存在するという仮定。多くのゲームでは、異なる利得への影響を持つ複数のナッシュ均衡が存在する
- 混合戦略均衡(確率的プレイ)と純粋戦略均衡を混同し、エージェントの行動の誤解につながる
- 均衡の必要条件と十分条件の区別を見落とす。完全にラベル付けされたペアは最適性を満たすが、プレイヤーが協調できない場合には実現されない可能性がある
よくある質問
ゲームにナッシュ均衡は存在しないことがありますか?
純粋戦略ナッシュ均衡は存在しない場合がある(例:じゃんけん)が、全ての有限ゲームは、プレイヤーが特定の確率で行動をランダム化する少なくとも1つの混合戦略均衡を持つ。
混合戦略均衡は純粋戦略均衡とどのように異なりますか?
純粋戦略均衡では、各プレイヤーは確実にある特定のアクションを選択する。混合戦略均衡では、各プレイヤーは行動の確率分布を使用する。混合均衡はしばしばより一般的であり、純粋均衡が存在しない場合に存在する。
Lemke-Howsonアルゴリズムは、総当たり探索よりもなぜ好まれるのですか?
このアルゴリズムは、戦略空間の多面体構造を利用し、探索空間を指数関数的に削減し、非退化ゲームでは多項式時間で収束を達成する。一方、総当たり列挙は、戦略空間が大きくなるにつれて実行不可能になる。
関連する手法
参考文献
Nash, J. F. (1950). Equilibrium points in N-person games. Proceedings of the National Academy of Sciences, 36(1), 48-49.
DOI 文献を開くコピーしました。Lemke, C. E., & Howson Jr, J. T. (1964). Equilibrium points of bimatrix games. Journal of the Society for Industrial and Applied Mathematics, 12(2), 413-423.
DOI 文献を開くコピーしました。