Fairly Allocating (Contiguous) Dynamic Indivisible Items with Few Adjustments

We study the problem of dynamically allocating indivisible items with nonnegative valuations to a group of agents in a fair manner. Due to the negative results to achieve fairness when allocations are irrevocable, we allow adjustments to make fairness attainable with the objective to minimize the number of adjustments. For restricted additive or general identical valuations, we show that envy-freeness up to one item (EF1) can be achieved at no cost. For additive valuations, we give an EF1 algorithm that requires $O(mT)$ adjustments, where $m$ is the maximum number of different valuations for items among all agents and $T$ is the number of items. We further impose the contiguity constraint on items such that items are arranged on a line by the order they arrive and require that each agent obtains a consecutive block of items. We present extensive results to achieve either proportionality with an additive approximate factor or EF1. In particular, we establish matching lower and upper bounds for identical valuations to achieve approximate proportionality. We also show that it is hopeless to make any significant improvement when valuations are nonidentical. Our results exhibit a large discrepancy between the identical and nonidentical cases in both contiguous and noncontiguous settings. All our positive results are computationally efficient.