An Allocation Algorithm of Indivisible Goods

Abstract—This paper proposes a new allocation algorithm of indivisible goods. We consider the case when the total value of the whole goods is the same for every participant, which models allocation at divorce or inheritance. The worst participant’s obtained value must be maximized. There are not good allocation algorithms for our rating scale. We show that this problem is NP-complete. Therefore we propose four types of approximation algorithms. Among the four algorithms, the raising standard algorithm has the best ratio that the algorithm outputs the optimal solution by a computer simulation. I