Parameterized Complexity of Manipulating Sequential Allocation

Michele Flammini, Hugo Gilbert
ECAI 2020


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 recently shown that finding a successful manipulation for an agent is an NP-hard problem (Aziz et al., AAAI 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 $\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. $\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.

PDF