Parameterized Complexity of Manipulating Sequential Allocation

Abstract

The sequential allocation protocol is a simple and popular mechanism to allocate indivisible goods, in which the agents take turns to pick the items according to a predefined sequence. While this protocol is not strategy-proof, it has been shown recently that finding a successful manipulation for an agent is an NP-hard problem (Aziz et al., 2017). Conversely, it is also known that finding an optimal manipulation can be solved in polynomial time in a few cases: if there are only two agents or if the manipulator has a binary or a lexicographic utility function. In this work, we take a parameterized approach to provide several new complexity results on this manipulation problem. More precisely, we give a complete picture of its parameterized complexity w.r.t. the following three parameters: the number $n$ of agents, the number $\mu (a_1)$ of times the manipulator $a_1$ picks in the picking sequence, and the maximum range ${\mathtt{rg}}^{\max }$ of an item. This third parameter is a correlation measure on the preference rankings of the agents. In particular, we show that the problem of finding an optimal manipulation can be solved in polynomial time if $n$ or $\mu (a_1)$ is a constant, and that it is fixed-parameter tractable w.r.t. ${\mathtt{rg}}^{\max }$ and $n+\mu (a_1)$. Interestingly enough, we show that w.r.t. the single parameters $n$ and $\mu (a_1)$ it is W[1]-hard. Moreover, we provide an integer program and a dynamic programming scheme to solve the manipulation problem and we show that a single manipulator can increase the utility of her bundle by a multiplicative factor which is at most 2.

Changes w.r.t. previous version: new W[1]-result on the parameter number of agents