大会名称 |
---|
2010年 情報科学技術フォーラム(FIT) |
大会コ-ド |
F |
開催年 |
2010 |
発行日 |
2010/8/20 |
セッション番号 |
7A |
セッション名 |
アルゴリズム・コンピュテーション(3) |
講演日 |
2010/09/09 |
講演場所(会議室等) |
A会場(総合学習プラザ1F 第5講義室) |
講演番号 |
RA-007 |
タイトル |
架空名義操作不可能な施設配置メカニズムの特徴付け |
著者名 |
東藤 大樹, 岩崎 敦, 横尾 真, |
キーワード |
施設配置問題, Algorithmic Game Theory, 近似率解析 |
抄録 |
施設の配置場所を適切に決定する問題は施設配置問題と呼ばれる. インターネット上で施設配置問題を扱う場合, 一人のエージェントが複数のアカウントを用いる架空名義操作と呼ばれる不正行為が可能となるが, 架空名義操作に対して頑健(架空名義操作不可能)な配置メカニズムは従来議論されていなかった. 本研究では,施設配置問題における架空名義操作を定式化し, 架空名義操作不可能な配置メカニズムの特徴付けを与える. また,与えた特徴付けを応用し, 架空名義操作不可能な配置メカニズムが達成可能な近似率を解明する. 更に,従来議論されてきたいくつかの性質と架空名義操作不可能性との関係を明確にする. |
本文pdf |
PDF download (392.4KB) |