研究紹介
東日本大震災、エネルギー/環境問題、少子高齢化等により、労働力も含めた希少な資源をどのように配分するかは、我が国の持続可能な発展のための喫緊の課題である。最適な資源配分を決定する問題は、伝統的に組合せ最適化問題として扱われている。しかしながら、情報学での資源配分問題に関する研究の問題点として、意思決定を行う主体は単数であることが前提であり、異なる目的を持つ複数の主体の間での資源配分は考慮されていないことがある。そこでは、異なる目的を持つ複数の主体（マルチエージェント）が存在する状況において、望ましい資源配分を実現するために、ゲーム理論を用いた資源配分問題、いわゆるメカニズムデザインに関する研究を進めている（図1）。
図1：応募者の研究の対象領域
従来、メカニズムデザインはミクロ経済学/ゲーム理論の一分野であり、アメリカ連邦通信委員会による周波数オークションやGoogleによるキーワード広告オークション、ニューイングランド腎臓交換プログラムによる腎移植ネットワークといった成果がとくに知られている。しかし、基本的には理論的性質を満たすメカニズムの存在可能性等の議論に重点がおかれ、メカニズムの入力にかかる記述量や実行にかかる計算量などのメカニズムの実現可能性に関する検討が不十分であるという問題点があった。例えば、参加者に嘘をつく誘因がないという理論的に優れた性質を持つ資源配分メカニズムであるVickrey-Clarke-Grovesメカニズムでは、メカニズムの実行時にNP困難な最適化問題を繰り返し解く必要があり、また、メカニズムの入力となるパラメータ、すなわち参加者の選好の記述量が配分の対象となる資源の種類に対して指数的に増加する。こうした課題を、情報学の技術を用いて解決する研究は重要な文理融合領域であり、世界的には情報学、とくに人工知能・マルチエージェントにおける一大研究分野となっている。
本研究室は日本では数少ない情報学におけるゲーム理論/メカニズムデザインを専門としており、その研究は、単なる情報学の技術のゲーム理論への応用にとどまらず、情報学の視点からでこそ気づくことができる先駆的な課題に取り組んでいる。
その代表的な課題として架空名義操作がある。架空名義操作（入札）とは、１人の参加者が複数のメールアドレス等を用いて複数の参加者のふりをして入札する不正行為である。インターネットオークションのようなネットワーク環境では各参加者の身元を正確に認証することは事実上不可能であるため、架空名義操作は深刻な問題となり得る。これに対して、架空名義操作の影響を受けないメカニズムの理論的特徴付けと解析、そしてアルゴリズムとしてのメカニズムの設計を進めている。さらに、これらの研究で得た知見を安定結婚問題や施設配置問題、協力ゲームなどに拡張している。
一方で、オークションのような資源配分メカニズムは従来は人手で設計されてきたが、近年メカニズム設計の問題自体を最適化問題に帰着し、メカニズムを自動設計する技術（自動メカニズムデザイン）がある。例えば、オークションのメカニズムを入力（参加者のもちうる選好の分布）と出力（割当と支払額）の関係を表で表すと考える。さらに、表の各項目を整数計画法の変数とし、制約条件（架空名義操作をしないことが最適）の元で、参加者の利益や収入の最大化を目的関数として最適解を求める。この解が、限定された入力に対してではあるが、架空名義操作不可能な割当と支払額となる。実際、これまでになかった架空名義操作の影響を受けないメカニズムの設計に成功している。これに関連する研究がFIT2011船井ベストペーパー賞を受賞している。
こうした研究成果をもとに、ゲーム理論の視点から、情報システムを通じて、様々な社会的課題を解決できるような研究を進めていきたい。ゲーム理論はいっけん抽象的過ぎて、具体的な課題の解決には向かないように見えるかもしれない。しかし実際には、人間が関わるシステムにおける課題を解決するには、ゲーム理論/ミクロ経済学分野で長年に渡って洗練されてきた抽象的なモデルは、流体のシミュレーションにおける理想気体や完全流体のようなものと考え、そこで何が起こるかを理解することが極めて重要となる。こうした意識の元で、理論と実践を相互にフィードバックさせることを常に意識しながら様々な社会的課題に取り組んで行きたい。
