アルゴリズム機構設計

アルゴリズム的メカニズム設計（AMD ）は、経済ゲーム理論、最適化、およびコンピュータサイエンスの交点に位置する。メカニズム設計における典型的な問題は、複数の利己的な参加者のためのシステムを設計し、均衡状態における参加者の利己的な行動がシステムの良好なパフォーマンスにつながるようにすることである。研究される典型的な目的には、収益最大化と社会厚生最大化が含まれる。アルゴリズム的メカニズム設計は、いくつかの点で古典的な経済メカニズム設計とは異なる。古典的な経済学のメカニズム設計ではエージェントに関する分布仮定を行うことが多いのに対し、アルゴリズム的メカニズム設計では、最悪ケース分析や近似比などの理論計算機科学の分析ツールが一般的に用いられる。また、計算上の制約が極めて重要であるとみなされる。多項式時間で効率的に実装できないメカニズムは、メカニズム設計問題に対する実行可能な解決策とはみなされない。これは、例えば、古典的な経済メカニズムであるヴィックリー・クラーク・グローブスオークションを排除することが多い。

ノアム・ニサンとアミール・ロネンは、1999年に発表された研究論文で初めて「アルゴリズム的メカニズム設計」という言葉を提唱した。^{[ 1 ] [ 2 ]}

• アルゴリズムゲーム理論
• 計算論的社会選択
• メタゲーム
• インセンティブ対象
• ヴィックリー・クラーク・グローブス機構

• ヴァジラニ、ヴィジェイ V. ;ニサン, ノーム;ティム・ラフガーデン;タルドス、エヴァ(2007)。アルゴリズムゲーム理論(PDF)。ケンブリッジ、英国: Cambridge University Press。ISBN 0-521-87282-0。
• ダッティング、ポール。 Geiger、Andreas (2007 年 5 月 9 日)、Algorithmic Mechanism Design (PDF)、セミナー レポート、カールスルーエ大学、Fakultät für Informatik、2015 年 6 月 13 日のオリジナル(PDF)からアーカイブ、2015 年6 月 11 日に取得。