講演名 | 2017-05-13 λ Group Strategy Proof Mechanisms for the Obnoxious Facility Game in Star Networks 福井 悠平(京大), アレクサンダル シュルベフスキ(京大), 永持 仁(京大), |
---|---|
PDFダウンロードページ | PDFダウンロードページへ |
抄録(和) | In the obnoxious facility game, we design mechanisms that output a location of an undesirable facility based on the locations of players reported by themselves. The benefit of a player is defined to be the distance between her location and the facility. A player may try to manipulate the output of the mechanism by strategically misreporting her location. We wish to design a $lambda$-group strategy-proof mechanism i.e., for every group of players, at least one player in the group cannot gain strictly more than $lambda$ times her primary benefit by having the entire group change their reports simultaneously. In this paper, we design an $k$-candidate $lambda$-group strategy-proof mechanism for the obnoxious facility game in the metric defined by $k$ half lines with a common endpoint such that each candidate is a point in each of the half-lines at the same distance to the common endpoint as other candidates. Then, we show that the benefit ratio of the mechanism is at most $1+1/(k-1)lambda$. Finally, we prove that the bound is nearly tight. |
抄録(英) | In the obnoxious facility game, we design mechanisms that output a location of an undesirable facility based on the locations of players reported by themselves. The benefit of a player is defined to be the distance between her location and the facility. A player may try to manipulate the output of the mechanism by strategically misreporting her location. We wish to design a $lambda$-group strategy-proof mechanism i.e., for every group of players, at least one player in the group cannot gain strictly more than $lambda$ times her primary benefit by having the entire group change their reports simultaneously. In this paper, we design an $k$-candidate $lambda$-group strategy-proof mechanism for the obnoxious facility game in the metric defined by $k$ half lines with a common endpoint such that each candidate is a point in each of the half-lines at the same distance to the common endpoint as other candidates. Then, we show that the benefit ratio of the mechanism is at most $1+1/(k-1)lambda$. Finally, we prove that the bound is nearly tight. |
キーワード(和) | |
キーワード(英) | mechanism designobnoxious facility gamestrategy proofstar network |
資料番号 | COMP2017-9 |
発行日 | 2017-05-05 (COMP) |
研究会情報 | |
研究会 | COMP / IPSJ-AL |
---|---|
開催期間 | 2017/5/12(から2日開催) |
開催地(和) | 長崎県建設工業協同組合 |
開催地(英) | |
テーマ(和) | |
テーマ(英) | |
委員長氏名(和) | 伊藤 大雄(電通大) / 堀山 貴史(埼玉大) |
委員長氏名(英) | Hiro Ito(Univ. of Electro-Comm.) / 堀山 貴史(埼玉大) |
副委員長氏名(和) | 宇野 裕之(阪府大) |
副委員長氏名(英) | Yushi Uno(Osaka Pref. Univ.) |
幹事氏名(和) | 脊戸 和寿(成蹊大) / 斎藤 寿樹(九工大) / 岡本 吉央(電通大) / 川原 純(NAIST) / 河村 彰星(東大) |
幹事氏名(英) | Kazuhisa Seto(Seikei Univ.) / Toshiki Saito(Kyushu Inst. of Tech.) / 岡本 吉央(電通大) / 川原 純(NAIST) / 河村 彰星(東大) |
幹事補佐氏名(和) | |
幹事補佐氏名(英) |
講演論文情報詳細 | |
申込み研究会 | Technical Committee on Theoretical Foundations of Computing / Special Interest Group on Algorithms |
---|---|
本文の言語 | ENG |
タイトル(和) | |
サブタイトル(和) | |
タイトル(英) | λ Group Strategy Proof Mechanisms for the Obnoxious Facility Game in Star Networks |
サブタイトル(和) | |
キーワード(1)(和/英) | / mechanism designobnoxious facility gamestrategy proofstar network |
第 1 著者 氏名(和/英) | 福井 悠平 / Yuhei Fukui |
第 1 著者 所属(和/英) | 京都大学(略称:京大) Kyoto University(略称:Kyoto Univ.) |
第 2 著者 氏名(和/英) | アレクサンダル シュルベフスキ / Aleksandar Shurbevski |
第 2 著者 所属(和/英) | 京都大学(略称:京大) Kyoto University(略称:Kyoto Univ.) |
第 3 著者 氏名(和/英) | 永持 仁 / Hiroshi Nagamochi |
第 3 著者 所属(和/英) | 京都大学(略称:京大) Kyoto University(略称:Kyoto Univ.) |
発表年月日 | 2017-05-13 |
資料番号 | COMP2017-9 |
巻番号(vol) | vol.117 |
号番号(no) | COMP-28 |
ページ範囲 | pp.61-68(COMP), |
ページ数 | 8 |
発行日 | 2017-05-05 (COMP) |