A Cryptographic Moving-Knife Cake-Cutting Protocol with High Social Surplus

• Item type: Journal(1)
• 公開日: 2015-05-15
• タイトル: A Cryptographic Moving-Knife Cake-Cutting Protocol with High Social Surplus
• タイトル / 言語: en
• タイトル: A Cryptographic Moving-Knife Cake-Cutting Protocol with High Social Surplus
• 言語: eng
• キーワード / 主題Scheme: Other
• キーワード / 主題: [特集：娯楽の離散数理] game-theory, cake-cutting, moving-knife, secure auction, social surplus
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: Kogakuin University
• 著者所属: Kogakuin University
• 著者所属: NTT Secure Platform Laboratories
• 著者所属(英): en
• 著者所属(英): Kogakuin University
• 著者所属(英): en
• 著者所属(英): Kogakuin University
• 著者所属(英): en
• 著者所属(英): NTT Secure Platform Laboratories
• 著者名: Yoshifumi, Manabe; Risako, Otsuka; Tatsuaki, Okamoto
• 著者名(英): Yoshifumi, Manabe; Risako, Otsuka; Tatsuaki, Okamoto
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: This paper proposes a cake-cutting protocol using cryptography when the cake is a heterogeneous good that is represented by an interval on a real line. Although the Dubins-Spanier moving-knife protocol with one knife achieves simple fairness and truthfulness, all players must execute the protocol synchronously. Thus, the protocol cannot be executed on asynchronous networks such as the Internet. We show that the moving-knife protocol can be executed approximately but asynchronously by a discrete protocol using a secure auction protocol. The number of cuts is n-1 where n is the number of players, which is the minimum. Sgall and Woeginger proposed another asynchronous protocol that satisfies simple fairness, truthfulness, and the minimum number of cuts. These two protocols are compared from the viewpoint of social surplus. The simulation result shows that the cryptographic moving-knife protocol is better than the Sgall-Woeginger protocol.; ------------------------------; This is a preprint of an article intended for publication Journal of; Information Processing(JIP). This preprint should not be cited. This; article should be cited as: Journal of Information Processing Vol.23(2015) No.3 (online); DOI http://dx.doi.org/10.2197/ipsjjip.23.299; ------------------------------
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: This paper proposes a cake-cutting protocol using cryptography when the cake is a heterogeneous good that is represented by an interval on a real line. Although the Dubins-Spanier moving-knife protocol with one knife achieves simple fairness and truthfulness, all players must execute the protocol synchronously. Thus, the protocol cannot be executed on asynchronous networks such as the Internet. We show that the moving-knife protocol can be executed approximately but asynchronously by a discrete protocol using a secure auction protocol. The number of cuts is n-1 where n is the number of players, which is the minimum. Sgall and Woeginger proposed another asynchronous protocol that satisfies simple fairness, truthfulness, and the minimum number of cuts. These two protocols are compared from the viewpoint of social surplus. The simulation result shows that the cryptographic moving-knife protocol is better than the Sgall-Woeginger protocol.; ------------------------------; This is a preprint of an article intended for publication Journal of; Information Processing(JIP). This preprint should not be cited. This; article should be cited as: Journal of Information Processing Vol.23(2015) No.3 (online); DOI http://dx.doi.org/10.2197/ipsjjip.23.299; ------------------------------
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN00116647
• 書誌情報: 情報処理学会論文誌; 巻 56, 号 5, 発行日 2015-05-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7764