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

• Item type: Journal(1)
• 公開日: 2011-04-15
• タイトル: 架空名義操作不可能な施設配置メカニズムの特徴付け
• タイトル / 言語: en
• タイトル: Characterization of False-name-proof Facility Location Mechanisms
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 一般論文（論文賞受賞）
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 九州大学大学院システム情報科学府情報学専攻
• 著者所属: 九州大学大学院システム情報科学府情報学専攻
• 著者所属: 九州大学大学院システム情報科学府情報学専攻
• 著者所属(英): en
• 著者所属(英): Graduate School of ISEE, Kyushu University
• 著者所属(英): en
• 著者所属(英): Graduate School of ISEE, Kyushu University
• 著者所属(英): en
• 著者所属(英): Graduate School of ISEE, Kyushu University
• 著者名: 東藤, 大樹; 岩崎, 敦; 横尾, 真
• 著者名(英): Taiki, Todo; Atsushi, Iwasaki; Makoto, Yokoo
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 施設配置問題は，施設の配置場所を適切に決定する問題であり，オペレーションズリサーチや経済学において広く研究が行われてきた．特に戦略的操作不可能（各参加者にとって正直が最良の策）な配置メカニズムの設計が重要な課題として認知されている．一方，インターネットを介してこのような施設配置を実現する場合には，1人のエージェントが複数のエージェントであるかのように振る舞う架空名義操作と呼ばれる不正行為が可能となる．本研究では，施設配置メカニズムの架空名義操作不可能性を定式化し，この性質を満たす配置メカニズムの特徴付けを与える．また，この特徴付けを応用し，架空名義操作不可能な配置メカニズムが達成可能な近似率を解明する．具体的には社会的コストおよび最大コストの2つの評価基準に関して，架空名義操作不可能な配置メカニズムが達成可能な近似率の下界値を解明し，その下界値を達成するメカニズムの存在を示す．さらに，従来施設配置問題や経済学において議論されてきた類似の概念と架空名義操作不可能性との関係を明確にする．具体的には，人口単調性，匿名操作不可能性，架空名義操作不可能性の3つの性質が等価となることを明らかにする．また，架空名義操作不可能な配置メカニズムはつねに結託的戦略的操作不可能性を満たすことを示す．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Recently, mechanism design without monetary transfers is attracting much attention, since in many application domains on Internet, introducing monetary transfers is impossible or undesirable. Mechanism design studies how to design mechanisms that result in good outcomes even when agents strategically report their preferences. However, in highly anonymous settings such as the Internet, declaring preferences dishonestly is not the only way to manipulate the mechanism. Often, it is possible for an agent to pretend to be multiple agents, and submit multiple reports using different identifiers, e.g., different e-mail addresses. Such false-name manipulations are more likely to occur in a mechanism without monetary transfers, since submitting multiple reports would be less risky in such a mechanism. In this paper, we formalized false-name manipulations in facility location problems on the real line and obtained a full characterization of false-name-proof facility location mechanisms. By utilizing this characterization, we obtained tight bounds of approximation ratios for two objective functions; the social cost and the maximum cost. We also clarified the connections between false-name-proofness and other related properties. In particular, we showed that both population monotonicity and anonymity-proofness are equivalent to false-name-proofness.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN00116647
• 書誌情報: 情報処理学会論文誌; 巻 52, 号 4, p. 1657-1666, 発行日 2011-04-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7764