Loading article…
アルゴリズムゲーム理論（AGT ）は、ゲーム理論とコンピュータサイエンスの交差点に位置する学際的な分野であり、複数の戦略的エージェントが相互作用する環境におけるアルゴリズムの理解と設計に焦点を当てています。この研究分野は、計算論的思考と経済学の原理を組み合わせ、アルゴリズムへの入力が自己利益を追求する参加者からもたらされる場合に生じる課題に取り組んでいます。
従来のアルゴリズム設計では、入力は固定され信頼できるものと想定されていました。しかし、オンラインオークション、インターネットルーティング、デジタル広告、リソース割り当てシステムなど、多くの現実世界のアプリケーションでは、入力は複数の独立したエージェントによって提供され、これらのエージェントは結果を自分に有利に操作するために戦略的に情報を偽って報告する可能性があります。AGTは、このような戦略的な行動にもかかわらず効果的なシステムを分析および設計するためのフレームワークを提供します。
この分野は、互いに補完し合う2つの視点からアプローチすることができる。
この分野のアルゴリズム設計者は、従来のアルゴリズム要件（多項式時間実行時間や良好な近似比など）を満たすと同時に、参加者がシステムの意図した設計に従って行動することを保証するインセンティブ制約にも対処しなければならない。
1999年、ノーム・ニサンとアミール・ロネンによる画期的な論文[ 1 ]は、理論計算機科学コミュニティの注目を、利己的な（戦略的な）ユーザーのためのアルゴリズム設計へと向けさせた。彼らは要約の中で次のように述べている。
本稿では、参加者がアルゴリズムに従うとは限らず、むしろ自身の利益を優先すると考えられる分散環境におけるアルゴリズム問題を考察する。このような参加者（エージェントと呼ばれる）はアルゴリズムを操作できるため、アルゴリズム設計者は、エージェントが正しく行動することで、エージェントの利益が最大限に満たされるように事前に配慮する必要がある。メカニズム設計の分野の概念に基づき、このようなアルゴリズムを研究するためのフレームワークを提案する。このモデルでは、アルゴリズムによる解法は参加者への報酬によって特徴づけられ、メカニズムと呼ばれる。報酬は、すべての参加者がアルゴリズム設計者の意図どおりに行動するように、慎重に選択する必要がある。本稿では、メカニズム設計の標準的なツールをアルゴリズム問題、特に最短経路問題に適用する。
この論文はアルゴリズム的メカニズム設計という用語を作り出し、2012年のゲーデル賞選考委員会によって「アルゴリズム的ゲーム理論の発展の基礎を築いた3つの論文」の1つとして認められた。[ 2 ]
2012年のゲーデル賞でアルゴリズムゲーム理論への基礎的貢献として引用された他の2つの論文は、「無秩序の代償」の概念を導入し発展させた。1999年の論文「最悪の均衡」[ 3 ]で、クツピアスとパパディミトリウは、エージェントの利己的な行動によるシステム効率の低下を測る新しい尺度を提案した。それは、最適な構成におけるシステム効率と最悪のナッシュ均衡におけるシステム効率の比率である。（「無秩序の代償」という用語は、その数年後に登場した。[ 4 ]）
インターネットは、交換や商業の基盤として、またそれ自体として、新たな経済を生み出した。インターネットの計算的な性質は、この新たな経済において計算ツールの利用を可能にした。一方で、インターネット自体は多くの人々の行動の結果である。これは、それまで主流であった古典的な「トップダウン」型の計算アプローチとは異なる点である。したがって、ゲーム理論は、インターネットとその中での人間と機械の相互作用を考察する上で、自然な方法と言える。
ゲーム理論は均衡（ナッシュ均衡など）を研究する分野です。均衡とは一般的に、どのプレイヤーも戦略を変更するインセンティブを持たない状態と定義されます。均衡は、インターネットに関連するいくつかの分野、例えば金融取引や通信負荷分散などで見られます。ゲーム理論は均衡を分析するためのツールを提供しており、一般的なアプローチは「ゲームを見つける」こと、つまり特定のインターネット上のやり取りをゲームとして定式化し、それに関連する均衡を導き出すことです。
問題をゲームの観点から再定式化することで、インターネット上の相互作用の分析や、特定の要求を満たすメカニズムの構築が可能になります。均衡が存在することが示された場合、さらに次の疑問に答える必要があります。すなわち、均衡は妥当な時間内に見つけることができるのか、ということです。これは、均衡を見つけるためのアルゴリズムの分析につながります。特に重要なのは、アルゴリズム的ゲーム理論における多くの問題を含む複雑性クラスPPADです。
メカニズム設計は、インセンティブ制約下での最適化を扱う経済学の一分野である。アルゴリズム的メカニズム設計は、計算効率の要件の下での経済システムの最適化を検討する。研究対象となる典型的な目標には、収益最大化と社会福祉最大化が含まれる。
無秩序の価格と安定性の価格という概念は、参加者の利己的な行動によってシステムのパフォーマンスが低下することを捉えるために導入されました。無秩序の価格は、可能な最適なパフォーマンスに対する、均衡状態におけるシステムの最悪のパフォーマンスを捉えます。[ 5 ]一方、安定性の価格は、システムの最良の均衡状態における相対的なパフォーマンスを捉えます。 [ 6 ]これらの概念は、アルゴリズム設計における近似比の概念に対応します。
ゲームにおける均衡の存在は、通常、非構成的不動点定理を用いて確立される。ナッシュ均衡を計算するための効率的なアルゴリズムは知られていない。この問題は、2人対戦ゲームであっても、複雑性クラスPPADに対して完全である。 [ 7 ]対照的に、相関均衡は線形計画法を用いて効率的に計算でき、[ 8 ]また、後悔のない戦略によって学習することもできる。[ 9 ]
計算論的社会選択は、個々のエージェントの選好の集約である社会選択の計算論的側面を研究する。例としては、投票規則や連合形成のアルゴリズムと計算複雑性などが挙げられる。 [ 10 ]
その他のトピックは以下のとおりです。
アルゴリズムゲーム理論の論文は、 GEB [ 15 ]などのゲーム理論ジャーナル、 Econometricaなどの経済学ジャーナル、 SICOMP [ 16 ]などのコンピュータサイエンスジャーナルにも掲載されることが多い。