エージェントのためのゲーム理論

ゲーム理論は、合理的なエージェント間の戦略的相互作用を分析するための数学的枠組みを提供し、各意思決定者の結果が他の意思決定者の選択に依存する場合に、自己利益を追求する意思決定者がどのように行動するかを予測します。

Definition

ゲーム理論は、複数の合理的なエージェントがそれぞれ行動を選択し、その利得がすべてのエージェントの選択に依存する状況を研究し、均衡などの解概念を通じて安定した、または合理的な共同行動を特徴付けます。

Scope

このトピックでは、マルチエージェントAIで使用されるゲーム理論の基礎について扱います。具体的には、標準形ゲームと展開形ゲーム、支配戦略、ナッシュ均衡とその存在、混合戦略、囚人のジレンマやゼロサムゲームなどの主要な例、および均衡を計算するためのアルゴリズム的な問題が含まれます。エージェントが互いをどのように推論し、どのような共同行動が安定しているかについて考察します。相互作用ルールの設計はメカニズムデザインの項目で扱われ、ゲームをプレイすることを学習することは機械学習のサブフィールドに属します。

Core questions

• 戦略的相互作用は、標準形または展開形ゲームとしてどのように表現されますか？
• どのような解概念（支配戦略、ナッシュ均衡）が合理的なエージェントの行動を予測しますか？
• 均衡は、混合戦略において存在する保証がありますか？
• 均衡を計算することはどの程度困難であり、これはエージェントによるその利用にどのように影響しますか？

Key concepts

• 標準形ゲームと展開形ゲーム
• 利得と戦略
• 支配戦略
• ナッシュ均衡
• 混合戦略
• ゼロサムゲームとミニマックス
• 囚人のジレンマ
• 均衡計算

Key theories

ナッシュ均衡

ナッシュ均衡とは、どのエージェントも、他のエージェントが戦略を変えない限り、自分自身の戦略を一方的に変更することによって利得を改善できないような戦略の組み合わせです。ナッシュは、すべての有限ゲームには、混合戦略において少なくとも1つのそのような均衡が存在することを証明しました。

ゼロサムゲームにおけるミニマックス

2人ゼロサムゲームにおいて、フォン・ノイマンのミニマックス定理は、両プレイヤーにとっての価値と最適な（場合によってはランダム化された）戦略を保証し、ゲーム理論を敵対的意思決定に結びつけます。

支配戦略とジレンマ

支配戦略によるゲームの分析は、囚人のジレンマのような結果を説明します。そこでは、個々の合理的な選択が集合的に悪い結果につながり、個人とグループの合理性の間の緊張を示しています。

Clinical relevance

ゲーム理論的分析は、戦略的なエージェントがどのように行動するかを予測し、競争環境における安定した結果を特定することにより、オークションや市場、セキュリティおよびパトロール戦略、ネットワークルーティングと輻輳、自動交渉の設計に情報を提供します。

History

ゲーム理論はフォン・ノイマンとモルゲンシュテルンによって1944年に創始され、ナッシュの均衡概念（1950年）によって拡張されました。それは経済学の中心となり、1990年代からは、均衡の計算複雑性とマルチエージェントシステムにおけるその利用を研究するアルゴリズム的ゲーム理論を通じて、AIとコンピュータサイエンスの中心的な分野となりました。

Key figures

• John von Neumann
• Oskar Morgenstern
• John F. Nash
• Yoav Shoham
• Kevin Leyton-Brown

Seminal works

• nash1950
• vonneumann1944
• shoham2009

Frequently asked questions

ナッシュ均衡とは何ですか？

ナッシュ均衡とは、各エージェントにつき1つずつの戦略の組み合わせであり、他のエージェントが戦略を固定している限り、どの単一のエージェントも自分自身の戦略のみを変更することによってより良い結果を得ることができない状態を指します。これは、安定した相互に整合性のある合理的な行動の概念を捉えています。

囚人のジレンマはAIエージェントにとってなぜ重要ですか？

囚人のジレンマは、自己の合理的な利益に基づいて行動するエージェントが、協力した場合よりも全員にとって悪い結果に到達する可能性があることを示しています。これは、自己利益を追求するエージェントのシステムを構築する際に、インセンティブと協調メカニズムを設計することが重要である理由を浮き彫りにします。