電子情報通信学会総合大会講演要旨
D-1-6
分割不可能な財に対する配分方式
○清水航平・真鍋義文(工学院大)
分割不可能な財に対する配分方式に関して、配分された財に対するその人自身が感じる価値のうち、価値が最も小さい人の価値の値が出来るだけ大きくなる分割を求める問題を考える。Maximin share guaranteeなどの異なる評価尺度に対する近似アルゴリズムは考察されているが、これらは上記の評価尺度でよい配分結果を得ることはできない。また、この問題はNP完全である分割問題から帰着可能であるため、NP完全である。したがって、最適解に出来るだけ近い近似解を求めることを目指し、最大Pointアルゴリズム、Point差アルゴリズム、底上げアルゴリズム、平均考慮底上げアルゴリズムという4つのアルゴリズムをあげ、それぞれのアルゴリズムと優位性について考察する。