| 講演名 | 2015-12-19 ケーキ分割問題のためのメカニズムデザイン 鶴田 俊佑(九大), 東藤 大樹(九大), 櫻井 祐子(九大), 横尾 真(九大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | ケーキ分割問題は任意の点で分割可能な連続財（土地や計算機資源の利用時間など）をどのように分割し参加者に割り当てるかを考える問題である．計算機科学の分野では，参加者がケーキに対する好みを正直に申告することが弱支配戦略となることを保証する，戦略的操作不可能なメカニズムの研究が盛んである．更に強い性質として架空名義操作不可能性も考えられており，この性質は複数の名義を用いることができる場合でも，真の一名義で正直申告することが弱支配戦略となることを保証する．既存の研究では架空名義操作不可能性，非羨望性，及びパレート効率性といった望ましい性質を同時に満たすメカニズムが存在しないという不可能性定理が示されている．本論文では参加者が用いる名義数に応じた費用がかかるときに，架空名義操作不可能性，非羨望性，パレート効率性，及び個人合理性を同時に満たすメカニズムが存在することを示した．この費用は，メールアドレスを新たに作成するときの労力や，協力した友人に渡す金銭に対応する．この結果は費用という自然な仮定を導入することにより，既存の不可能性定理を克服できることを示す． |
| 抄録(英) | |
| キーワード(和) | ケーキ分割問題 / メカニズムデザイン / 架空名義操作 / 非羨望性 / パレート効率性 |
| キーワード(英) | |
| 資料番号 | AI2015-45 |
| 発行日 | 2015-12-11 (AI) |
| 研究会情報 | |
| 研究会 | AI |
|---|---|
| 開催期間 | 2015/12/18(から2日開催) |
| 開催地（和） | 那覇市ぶんかテンブス館 |
| 開催地（英） | |
| テーマ（和） | 「コンテキストを意識した知識の利用」および一般 |
| テーマ（英） | |
| 委員長氏名（和） | 菅原 俊治(早大) |
| 委員長氏名（英） | Toshiharu Sugawara(Waseda Univ.) |
| 副委員長氏名（和） | 峯 恒憲(九大) / 片上 大輔(東京工芸大) |
| 副委員長氏名（英） | Tsunenori Mine(Kyushu Univ.) / Daisuke Katagami(Tokyo Polytechnic Univ.) |
| 幹事氏名（和） | 服部 宏充(京大) / 福田 直樹(静岡大) |
| 幹事氏名（英） | Hiromitsu Hattori(Kyoto Univ.) / Naoki Fukuda(Shizuoka Univ.) |
| 幹事補佐氏名（和） | 清 雄一(電通大) |
| 幹事補佐氏名（英） | Yuichi Sei(Univ. of Electro-Comm.) |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Artificial Intelligence and Knowledge-Based Processing |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | ケーキ分割問題のためのメカニズムデザイン |
| サブタイトル（和） | |
| タイトル（英） | Mechanism Design for Cake Cutting |
| サブタイトル（和） | |
| キーワード(1)（和/英） | ケーキ分割問題 |
| キーワード(2)（和/英） | メカニズムデザイン |
| キーワード(3)（和/英） | 架空名義操作 |
| キーワード(4)（和/英） | 非羨望性 |
| キーワード(5)（和/英） | パレート効率性 |
| 第 1 著者 氏名（和/英） | 鶴田 俊佑 / Shunsuke Tsuruta |
| 第 1 著者 所属（和/英） | 九州大学(略称：九大) Kyushu University(略称：Kyushu Univ.) |
| 第 2 著者 氏名（和/英） | 東藤 大樹 / Taiki Todo |
| 第 2 著者 所属（和/英） | 九州大学(略称：九大) Kyushu University(略称：Kyushu Univ.) |
| 第 3 著者 氏名（和/英） | 櫻井 祐子 / Yuko Sakurai |
| 第 3 著者 所属（和/英） | 九州大学(略称：九大) Kyushu University(略称：Kyushu Univ.) |
| 第 4 著者 氏名（和/英） | 横尾 真 / Makoto Yokoo |
| 第 4 著者 所属（和/英） | 九州大学(略称：九大) Kyushu University(略称：Kyushu Univ.) |
| 発表年月日 | 2015-12-19 |
| 資料番号 | AI2015-45 |
| 巻番号（vol） | vol.115 |
| 号番号（no） | AI-381 |
| ページ範囲 | pp.113-118(AI), |
| ページ数 | 6 |
| 発行日 | 2015-12-11 (AI) |