Algorithmic game theory! (アルゴリズム的ゲーム理論)

Algorithmic game theoryですね．日本語だとアルゴリズムゲーム理論，アルゴリズム的ゲーム理論，アルゴリズム論的ゲーム理論と訳語が固まっていませんが，最近は日本でもこれを専門とする研究者が増えてきたようです．個人的にはアルゴリズム的ゲーム理論と呼んでいます．

Wikipedia の記述を参考に少し概説すると， アルゴリズム的ゲーム理論とは，ゲーム理論とアルゴリズム理論の融合領域で，戦略的環境 (strategic environment) におけるアルゴリズムを設計・解析することを目的とした理論です．ここで戦略的環境とは，アルゴリズムの入力と出力に関係する主体（エージェントやプレイヤ）が複数存在し，それぞれの主体が異なる目的／選好を持っている環境を指します．このとき，それぞれの主体は利己的，つまり自分の利得を最大化することを目指して，戦略的に振る舞うと仮定します．

従来のアルゴリズム理論の世界では，アルゴリズムに関係する主体は単数，もしくは複数存在したとしても，その目的が同じであると仮定しています．この仮定の元でうまく動くアルゴリズムであっても，複数の利己的主体を前提とすると，うまく動かなくなることがよくある訳です．各ノードを利己的主体と見立てた時のパケットルーティングなどはよく引き合いに出される例ですね．

こうした利己的主体 (selfish agents) を前提とするアルゴリズム理論のことをアルゴリズム的ゲーム理論というわけです．ですので，アルゴリズム的ゲーム理論の研究とは，基本的にはアルゴリズム理論の拡張であり，利己的主体の元で，多項式時間で動くアルゴリズムを設計したり，既存のアルゴリズムの競合比（最適時の性能に対する最悪時の性能の比）を明らかにしたりします．

僕もそういう研究者の一人と言えば，一人ですが，なりきれてはいないタイプです．というのも，同じ計算機科学者といっても，アルゴリズム的ゲーム理論は，より硬派？な理論計算機科学者達 (theoretical computer scientists) が培ってきた分野です．実際，2012年のゲーデル賞 (Gödel prize) が6名の創始者達，Elias Koutsoupias and Christos H. Papadimitriou, Tim Roughgarden and Éva Tardos, and Noam Nisan and Amir Ronenに与えられています．

ゲーデル賞はACM SIGACT (The ACM Special Interest Group on Algorithms and Computation Theory) というアルゴリズムと計算量理論に関する部会を中心に創設された賞です．

僕が今まで書いた論文で一番アルゴリズム的ゲーム理論に近いのは以下です．この論文では，架空名義操作の影響を受けないアルゴリズムの競合比を明らかにして，それに合致する新しいアルゴリズムを提案しています．PPTは日本語ですが，昔ゲーム理論ワークショップで発表した初心者向けバージョンになっています．

“Worst-case efficiency ratio in false-name-proof combinatorial auction mechanisms,” Atsushi Iwasaki, Vincent Conitzer, Yoshifusa Omori, Yuko Sakurai, Taiki Todo, Mingyu Guo, and Makoto Yokoo, the proceedings of the 9th International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS-2010), 査読有, 633–640, 2010. [pdf], [ppt]

また，以前Algorithmic Game Theoryの輪読会をしたときの資料へのリンクは以下の東藤大樹君のページにあります．

Algorithmic game theory! (アルゴリズム的ゲーム理論輪読会)

アクセス制限がかかっていますが，興味のある方はご連絡くださればパスワードをお送りできます．