文献

J-GLOBAL ID：201702231963403503   整理番号：17A1477880

二値効用下でのケーキ分割問題

Cake Cutting for All-or-Nothing Utility

著者 (4件)： 伊原尚正 (九州大学大学院システム情報科学府) ,  東藤大樹 (九州大学大学院システム情報科学研究院) ,  櫻井祐子 (産業技術総合研究所人工知能研究センター) ,  横尾真 (九州大学大学院システム情報科学研究院)
資料名： 人工知能学会論文誌(Web)  (TJSAI (Web))
巻： 32  号： 5  ページ： AG16-E_1-9(J-STAGE)  発行年： 2017年 
JST資料番号： U0128A  ISSN： 1346-8030  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 参加者が選好表明において戦略を有することを考慮するケーキ分割メカニズムで戦略的操作不可能性を満たすには,参加者の効用関数が加法的であることを仮定していた。本論文では,効用関数が加法性を満たさない二値効用である場合を対象とし,戦略的操作不可能性を満たすケーキ分割メカニズムを提案した。まず,二値効用下ではパレート効率性と非羨望性を満たすメカニズムは存在しないことを示し,Serial Dictatorshipメカニズムをもとに非羨望性を諦めて,戦略的操作不可能性とパレート効率性を満たすSSDメカニズムを提案した。次に,SSDメカニズムがパレート効率的な割当を発見する問題はNP困難なので,参加者数に対して多項式時間で求解可能なSSDFメカニズムを示した。また,SSDFメカニズムに基づきパレート効率性を諦めて,戦略的操作不可能性と非羨望性を満たすEF-SSDFメカニズムを提案した。さらに,戦略的操作不可能性を拡張した架空名義操作不可能性を満たすメカニズムを検討し,二値効用下でパレート効率性と両立するメカニズムは存在しないことを証明して,EF-SSDFメカニズムをもとに架空名義操作不可能性と非羨望性を満たすFNP-SSDFメカニズムを示した。各メカニズムの割当人数を比較する実験を行い,条件が加わるごとに平均割当人数が減少し,実行時間が増加することを確かめた。

シソーラス用語： *分割法 ,  ケーキ ,  効用関数 ,  最適条件 ,  *NP困難 ,  評価試験 ,  時間 ,  Pareto最適
準シソーラス用語： 実行時間

著者キーワード (10件)： mechanism design ,  cake cutting ,  all-or-nothing utility ,  strategy-proofness ,  false-name-proofness ,  mechanism design ,  cake cutting ,  all-or-nothing utility ,  strategy-proofness ,  false-name-proofness

分類 (2件)： その他のオペレーションズリサーチの手法  (KA03070E) ,  計算理論  (JB02000A)

引用文献 (18件)：

• [Abdulkadiroglu 98] Abdulkadiroglu, A. and Sonmez, T.: Random serial dictatorship and the core from random endowments in house allocation problems, em Econometrica, Vol.66, No.3, pp.689--701 (1998)
• [Asharov 11] Asharov, G., Canetti,R., and Hazay,C.: Towards a game theoretic view of secure computation, in Proceedings of the 30th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT-2011), pp.426--445 (2011)
• [Austin 82] Austin, A.: Sharing a cake, The Mathematical Gazette, Vol.66, No.437, pp.212--215 (1982)
• [Barbanel 04] Barbanel, J. B. and Brams,S.J.: Cake division with minimal cuts: Envy-free procedures for three persons, four persons, and beyond, Mathematical Social Sciences, Vol.48, No.3, pp. 251--269 (2004)
• [Bonzon 06] Bonzon, E., Lagasquie-Schiex, M. C., Lang, J., and Zanuttini, B.: Boolean games revisited, in Proceedings of the 17th European Conference on Artificial Intelligence (ECAI-2006), pp.265--269 (2006)

タイトルに関連する用語 (3件)： 二値 ,  効用 ,  ケーキ