メカニズムデザイン

メカニズムデザインは、逆ゲーム理論とも呼ばれ、自己利益を追求するエージェントが合理的に行動することで、設計者が望む結果を生み出すように、相互作用のルールを設計することである。

Definition

メカニズムデザインとは、合理的な自己利益追求型エージェントの均衡行動が、効率性や真実性といった望ましい目的を達成するように、多エージェント相互作用のルール（誰が何ができ、結果と支払いがどのように決定されるか）をどのように定義するかを研究する学問である。

Scope

このトピックでは、戦略的エージェントのための相互作用プロトコルの設計、すなわち、社会的選択と選好の集約、効率性とインセンティブ整合性（真実性）の目標、啓示原理、オークション（ヴィックリーのセカンドプライスオークションやヴィックリー・クラーク・グローブス機構を含む）、およびメカニズム実装のアルゴリズム的・計算的側面について扱う。これは、個人のインセンティブを集団的目標とどのように整合させるかについて述べる。固定されたゲームにおいてエージェントがどのように振る舞うかの記述的分析は、ゲーム理論の項目で扱われる。

Core questions

• エージェントが真の選好を報告するインセンティブを持つように、相互作用のルールはどのように設計できるか？
• 啓示原理は、真実なメカニズムに限定することについて何を述べているか？
• オークションは、私的評価を持つエージェント間で商品を効率的に割り当てるにはどうすればよいか？
• 望ましいメカニズムを実装するための計算コストはどのくらいか？

Key concepts

• 社会的選択と選好集約
• インセンティブ整合性（真実性）
• 支配戦略実装
• 啓示原理
• オークション
• ヴィックリーのセカンドプライスオークション
• ヴィックリー・クラーク・グローブス（VCG）機構
• 効率性と個人合理性

Key theories

インセンティブ整合性とセカンドプライスオークション

ヴィックリーのセカンドプライス（封印入札）オークションでは、落札者が2番目に高い入札額を支払うため、真実な入札が支配戦略となり、慎重なルール設計が自己利益を追求するエージェントから正直な行動を引き出す方法を示している。

ヴィックリー・クラーク・グローブス機構

VCGファミリーは、セカンドプライスの考え方を複雑な配分問題に一般化し、各エージェントにその外部性を課すことで、真実な報告が支配戦略となり、効率的な結果が選択されるようにする。

啓示原理

啓示原理は、あるメカニズムによって達成可能な任意の結果は、真実な直接メカニズムによっても達成可能であることを示しており、設計者は一般性を失うことなくインセンティブ整合的なメカニズムに焦点を当てることができる。

Clinical relevance

メカニズムデザインは、オンライン広告やスポンサー検索オークション、周波数帯域や資源のオークション、電子市場やマッチングシステム、計算資源の割り当てにおいて、戦略的エージェントが効率的かつ真実な結果に導かれるようなルールを設計することで、その基盤となっている。

History

メカニズムデザインは、ヴィックリーのオークション分析（1961年）と、その後のクラークおよびグローブスの貢献によってVCGファミリーが形成された経済理論から発展した。1990年代後半からは、計算機科学が計算上の扱いやすさや近似の研究を加え、Algorithmic Game Theory（2007年）などのテキストで示されたアルゴリズム的メカニズムデザインが誕生した。

Key figures

• William Vickrey
• Edward H. Clarke
• Theodore Groves
• Noam Nisan
• Tim Roughgarden

Seminal works

• vickrey1961
• shoham2009
• nisan2007

Frequently asked questions

なぜメカニズムデザインは逆ゲーム理論と呼ばれるのか？

ゲーム理論は、相互作用のルールを所与のものとして、合理的なエージェントがどのように振る舞うかを分析する。メカニズムデザインは逆の働きをする。すなわち、望ましい結果から出発し、エージェントの合理的な行動がその結果を生み出すようにルールを設計するため、逆ゲーム理論という名称が付けられている。

なぜセカンドプライスオークションは真実な入札を促すのか？

ヴィックリーのセカンドプライスオークションでは、落札者は自分の入札額ではなく、2番目に高い入札額を支払う。これにより、入札額を低くするインセンティブがなくなる。真の価値を入札することは、価値がある場合にのみ落札に役立ち、決して過払いすることはないため、正直な入札が支配戦略となる。