An online allocation algorithm of indivisible goods

摘要

This paper proposes a new online allocation algorithm of indivisible goods. In online algorithms, participants arrive to execute the algorithm at any time and exit from the algorithm when his/her allocation is given. We assume that the total value of the whole goods is the same for every participant. In cake-cutting algorithms for divisible goods, immediately envy-free has been defined as the desirable property. The property means that for any participants, any other participants who arrive after and depart before the participant obtain no more value than the participant. However, it is difficult for online allocation algorithms for indivisible goods to satisfy immediately envy-free. Therefore we propose a weakly immediately envy-free algorithm, which means that participants do not value goods allocated to participants who arrived later but departs earlier than them, more than their own. Our algorithm aims to maximize the worst obtained value among all participants. We show that this problem involves an NP-complete problem. Thus, it is very difficult to always output an optimal solution. We propose an approximation algorithm and prove its approximation ratio.