Contiguous Allocation of Indivisible Items on a Path

We study the problem of allocating indivisible items on a path among agents.The objective is to find a fair and efficient allocation in which each agent'sbundle forms a contiguous block on the line. We demonstrate that, even when thevaluations are binary additive, deciding whether every item can be allocated toan agent who wants it is NP-complete. Consequently, we provide twofixed-parameter tractable (FPT) algorithms for maximizing utilitarian socialwelfare, with respect to the number of agents and the number of items.Additionally, we present a 2-approximation algorithm for the special case whenthe valuations are binary additive and the maximum utility is equal to thenumber of items. Furthermore, we establish that deciding whether the maximumegalitarian social welfare is at least 2 or at most 1 is NP-complete, even whenthe valuations are binary additive. We also explore the case where the order ofthe blocks of items allocated to the agents is predetermined. In this case, weshow that both maximum utilitarian social welfare and egalitarian socialwelfare can be computed in polynomial time. However, we determine that checkingthe existence of an EF1 allocation is NP-complete, even when the valuations arebinary additive.