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.
展开▼
机译：我们考虑以下关于不可分割货物公平分配的控制问题。给定一组项I和一组代理，每个组对项都有严格的线性偏好，我们要求获得项的最小子集，这些子集的删除保证其余实例中按比例分配。我们称此问题为按项目删除（PID）的比例。我们的主要结果是多项式时间算法，该算法可以求解三个主体的PID。相比之下，我们证明，即使代理删除的数量k很小，当代理的数量不受限制时，PID在计算上也很棘手，因为相对于参数k来说，问题是W [3]难的。另外，当我们将PID的复杂度作为| I |的函数时，我们提供了一些严格的上下限。和k。
展开▼
