Title: Obtaining a Proportional Allocation by Deleting Items,
Abstract: We consider the following control problem on fair allocation of indivisible
goods. Given a set $I$ of items and a set of agents, each having strict linear
preference 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 $k$ of item deletions allowed is small,
since the problem turns out to be W[3]-hard with respect to the parameter $k$.
Additionally, we provide some tight lower and upper bounds on the complexity of
PID when regarded as a function of $|I|$ and $k$.