ホールケーキ分割問題に対するカット数最小の無羨望メカニズム
この論文をさがす
抄録
誰からも不満が出ないようにケーキを分けるにはどうすればよいか?ケーキは均一でなく、人の好み(評価関数)も様々である。これに挑むのがケーキ分割問題である。一般に(a)無羨望性=各人が他人の割当を羨まないことと(b)カット数の最小性が望まれるが、これらを同時に満たす分割を求める問題はPPAD完全である。そこでAlijaniら (AAAI,2017) は、ケーキが(ロールケーキ状の)閉区間の場合、各人の評価関数が単純(ある1つの部分区間にのみ正定数の効用を持つ)であれば、多項式時間可解と示した。本発表ではこの結果をホールケーキ版へ一般化し、多項式時間可解と示す。ここでホールケーキとは円形のケーキであり、閉区間の一般化とみなせる。
収録刊行物
-
- 第80回全国大会講演論文集
-
第80回全国大会講演論文集 2018 (1), 161-162, 2018-03-13
- Tweet
キーワード
詳細情報 詳細情報について
-
- CRID
- 1050292572146741248
-
- NII論文ID
- 170000176619
-
- NII書誌ID
- AN00349328
-
- Web Site
- http://id.nii.ac.jp/1001/00187520/
-
- 本文言語コード
- ja
-
- 資料種別
- conference paper
-
- データソース種別
-
- IRDB
- CiNii Articles