Obtaining a Proportional Allocation by Deleting Items.

We consider the following control problem on fair allocation of indivisible goods. Given a set of items and a set of agents, each having strict linear preferences over the items, we ask for a minimum subset of the items whose deletion guarantees the existence of a proportional allocation in the remaining instance; we call this problem Proportionality by Item Deletion (PID). Our main result is a polynomial-time algorithm that solves PID for three agents. By contrast, we prove that PID is computationally intractable when the number of agents is unbounded, even if the number of item deletions allowed is small-we show that the problem is -hard with respect to the parameter . Additionally, we provide some tight lower and upper bounds on the complexity of PID when regarded as a function of || and . Considering the possibilities for approximation, we prove a strong inapproximability result for PID. Finally, we also study a variant of the problem where we are given an allocation in advance as part of the input, and our aim is to delete a minimum number of items such that is proportional in the remainder; this variant turns out to be -hard for six agents, but polynomial-time solvable for two agents, and we show that it is -hard when parameterized by the number of.