Meta-envy-free Cake-cutting and Pie-cutting Protocols
スポンサーリンク
概要
- 論文の詳細を見る
This paper discusses cake-cutting protocols when the cake is a heterogeneous good, represented by an interval on the real line. We propose a new desirable property, the meta-envy-freeness of cake-cutting, which has not been formally considered before. Meta-envy-free means there is no envy on role assignments, that is, no party wants to exchange his/her role in the protocol with the one of any other party. If there is an envy on role assignments, the protocol cannot be actually executed because there is no settlement on which party plays which role in the protocol. A similar definition, envy-freeness, is widely discussed. Envy-free means that no player wants to exchange his/her part of the cake with that of any other player's. Though envy-freeness was considered to be one of the most important desirable properties, envy-freeness does not prevent envy about role assignment in the protocols. We define meta-envy-freeness to formalize this kind of envy. We propose that simultaneously achieving meta-envy-free and envy-free is desirable in cake-cutting. We show that current envy-free cake-cutting protocols do not satisfy meta-envy-freeness. Formerly proposed properties such as strong envy-free, exact, and equitable do not directly consider this type of envy and these properties are very difficult to realize. This paper then shows cake-cutting protocols for two and three party cases that simultaneously achieves envy-free and meta-envy-free. Last, we show meta-envy-free pie-cutting protocols.
- 2012-06-15
著者
-
真鍋 義文
Nttコミュニケーション科学基礎研究所
-
真鍋 義文
Ntt基礎研究所
-
真鍋 義文
NTTソフトフェア研究所
-
Manabe Yoshifumi
Ntt Corp. Atsugi‐shi Jpn
-
Yoshifumi Manabe
Ntt Communication Science Laboratories
-
Tatsuaki Okamoto
NTT Secure Platform Laboratories
-
真鍋 義文
Ntt Communication Science Laboratories
関連論文
- 「出会いの場」としての学会
- Linuxファイルシステムの信頼性についての一考察(高信頼性)
- 汎用的結合可能性による暗号システムの安全性証明(セキュリティ,フォーマルアプローチ論文)
- センサ情報処理のためのコーパス構築(生活メディア)
- センサネットワーク環境における情報検索プラットフォームの提案(セッション2-A:RFID,センサーネットワーク)
- センサネットワーク環境における情報検索プラットフォームの提案(セッション2-A:RFID,センサーネットワーク)
- グリッドコンピューティングによる実世界情報マイニングの提案(セッション4: メタデータとWebデータベース応用)
- グリッドコンピューティングによる実世界情報マイニングの提案(セッション4: メタデータとWebデータベース応用)
- 特集「待ち行列の数理」にあたって
- h-out of-k相互排除問題を解く(h, k)-arbiterの一構成法
- メッセージ通信モデルでの均一な自己安定アルゴリズムへの拡張について
- 周期的リアルタイムタスクのRate Monotonic法によるスケジュール可能性判定問題について
- 5. 分散チェックポイント・ロールバックアルゴリズム (<特集> フォールトトレラント分散システム向けアルゴリズム)
- 分散k-相互排除問題について
- 分散プログラムデバッガのためのチェックポイントアルゴリズム
- 分散システムにおける全域状態監視アルゴリズム
- ミッションクリティカルシステムのためのLinux
- 小型・低電力のHDTV対応MPEG-2リアルタイムビデオエンコーダを開発 : 1ボードで電池駆動を世界で初めて実現
- 3Tbit/s光伝送実験に成功
- 視覚的データマイニング支援を実現
- 世界最高速のATMスイッチシステム"OPTIMA"を開発
- 1チップ指紋センサ認証LSIを開発
- 実写型カーナビゲーションシステムの開発
- 40Gbit/s光ソリトン伝送技術に進展 : 現場に布設された光ファイバで1,360km伝送に(NTT), 室内実験で10,000km伝送に(KDD)成功
- 分散移動システムのための全域チェックポイントアルゴリズム
- モーバイルプロセスを含んだ分散システム向けチェックポイントアルゴリズム
- A Universally Composable Secure Channel Based on the KEM-DEM Framework(Public Key Cryptography, Cryptography and Information Security)
- Coterie for Generalized Mutual Exclusion Problem
- ジョンズ・ホプキンス大学計算科学科(海外,ラボラトリーズ)
- チェックポイント数最小の分散チェックポイントアルゴリズム
- フォールトトレラント分散システム向けアルゴリズム (リスポンシブシステム実時間性と高信頼性の統合を目指して)
- 分散最始・最終全域チェックポイントアルゴリズム
- 固定コストのある場合のオンライン値段づけアルゴリズムについて
- 特集「フォールトトレラント分散システム向けアルゴリズム」の編集にあたって
- Universally Composable Identity-Based Encryption
- On the Equivalence of Several Security Notions of KEM and DEM
- 89-26 可変トポロジネットワーク上での固定トポロジアルゴリズムの効率よい実行
- 樹枝状単調減少論理回路を実現するCMOS回路に対する最小分離度配置問題
- 超立方体環グラフと超立方体グラフの最小2分割幅
- 一層一行配線問題の片側トラック数の最小性
- Meta-envy-free Cake-cutting and Pie-cutting Protocols