講演抄録/キーワード |
講演名 |
2015-12-19 09:00
ケーキ分割問題のためのメカニズムデザイン ○鶴田俊佑・東藤大樹・櫻井祐子・横尾 真(九大) AI2015-45 |
抄録 |
(和) |
ケーキ分割問題は任意の点で分割可能な連続財(土地や計算機資源の利用時間など)をどのように分割し参加者に割り当てるかを考える問題である.
計算機科学の分野では,参加者がケーキに対する好みを正直に申告することが弱支配戦略となることを保証する,戦略的操作不可能なメカニズムの研究が盛んである.
更に強い性質として架空名義操作不可能性も考えられており,この性質は複数の名義を用いることができる場合でも,真の一名義で正直申告することが弱支配戦略となることを保証する.
既存の研究では架空名義操作不可能性,非羨望性,及びパレート効率性といった望ましい性質を同時に満たすメカニズムが存在しないという不可能性定理が示されている.
本論文では参加者が用いる名義数に応じた費用がかかるときに,架空名義操作不可能性,非羨望性,パレート効率性,及び個人合理性を同時に満たすメカニズムが存在することを示した.
この費用は,メールアドレスを新たに作成するときの労力や,協力した友人に渡す金銭に対応する.
この結果は費用という自然な仮定を導入することにより,既存の不可能性定理を克服できることを示す. |
(英) |
(Not available yet) |
キーワード |
(和) |
ケーキ分割問題 / メカニズムデザイン / 架空名義操作 / 非羨望性 / パレート効率性 / / / |
(英) |
/ / / / / / / |
文献情報 |
信学技報, vol. 115, no. 381, AI2015-45, pp. 113-118, 2015年12月. |
資料番号 |
AI2015-45 |
発行日 |
2015-12-11 (AI) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
AI2015-45 |