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

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

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




［推薦理由］

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