「架空名義操作不可能な施設配置メカニズムの特徴付け」

2011年度論文賞受賞者の紹介

「架空名義操作不可能な施設配置メカニズムの特徴付け」

[情報処理学会論文誌 Vol.52, No.4, pp.1657-1666]
[論文概要]

 施設配置問題は,施設の配置場所を適切に決定する問題であり,経済学を始めとして様々な分野で広く研究が行われてきた.特に戦略的操作不可能(各参加者にとって正直が最良の策)な配置メカニズムの設計が重要な課題として認知されている.一方,インターネットを介してこのような施設配置を実現する場合には,一人の参加者が複数の参加者であるかのように振る舞う架空名義操作と呼ばれる不正行為が可能となる.本研究では,施設配置メカニズムの架空名義操作不可能性(参加者が架空名義を行っても得をしない性質)を定式化し,この性質を満たす配置メカニズムの特徴付けを与える.




[推薦理由]

 本論文は,施設配置問題について架空名義操作不可能性を実現する施設配置決定アルゴリズムの条件を示している.さらに,アルゴリズムの性能を最適解とのコスト比で評価し,2種類のコストに対して最左値アルゴリズムは最良のコスト比を達成することを示している.そして,施設配置問題では,架空名義操作不可能性が匿名操作不可能性,人口単調性と等価であることを示している.ゲーム理論的に不正ができない(不正をしても意味がない状況を作る)メカニズムを作るという着眼点は非常に興味深い.施設配置問題は最近のアルゴリズムゲーム理論の分野で盛んに研究されているが,本論文はその問題に対して架空名義操作不可能性に関する自明でない結果を出しており論文賞に値する.

東藤大樹 君

 2012年3月九州大学大学院システム情報科学府博士後期課程修了.2010年4月より日本学術振興会特別研究員DC1.アルゴリズム的ゲーム理論やメカニズムデザインに関する研究に従事.博士(情報科学).

岩崎敦 君

 2002年神戸大学大学院自然科学研究科博士課程修了.2004年より九州大学大学院システム情報科学研究院助教.ゲーム理論,学習,オークション,実験経済学に関する研究に従事.博士(学術).

横尾真 君

 1986年東京大学院修士課程修了.同年NTTに入社.2004年より九州大学大学院システム情報科学研究院教授.マルチエージェントシステムに関する研究に従事.博士(工学).2006年学士院学術奨励賞受賞.情報処理学会,AAAIフェロー.