- 著者
-
梅田 博之
浅野 孝夫
- 雑誌
- 第80回全国大会講演論文集
- 巻号頁・発行日
- vol.2018, no.1, pp.161-162, 2018-03-13
誰からも不満が出ないようにケーキを分けるにはどうすればよいか?ケーキは均一でなく、人の好み(評価関数)も様々である。これに挑むのがケーキ分割問題である。一般に(a)無羨望性=各人が他人の割当を羨まないことと(b)カット数の最小性が望まれるが、これらを同時に満たす分割を求める問題はPPAD完全である。そこでAlijaniら (AAAI,2017) は、ケーキが(ロールケーキ状の)閉区間の場合、各人の評価関数が単純(ある1つの部分区間にのみ正定数の効用を持つ)であれば、多項式時間可解と示した。本発表ではこの結果をホールケーキ版へ一般化し、多項式時間可解と示す。ここでホールケーキとは円形のケーキであり、閉区間の一般化とみなせる。