情報処理学会 第80回全国大会講演要旨

　誰からも不満が出ないようにケーキを分けるにはどうすればよいか?ケーキは均一でなく、人の好み(評価関数)も様々である。これに挑むのがケーキ分割問題である。一般に(a)無羨望性=各人が他人の割当を羨まないことと(b)カット数の最小性が望まれるが、これらを同時に満たす分割を求める問題はPPAD完全である。そこでAlijaniら (AAAI,2017) は、ケーキが(ロールケーキ状の)閉区間の場合、各人の評価関数が単純(ある1つの部分区間にのみ正定数の効用を持つ)であれば、多項式時間可解と示した。本発表ではこの結果をホールケーキ版へ一般化し、多項式時間可解と示す。ここでホールケーキとは円形のケーキであり、閉区間の一般化とみなせる。