Parameterized Complexity of Manipulating Sequential Allocation

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 [1]. 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 μ(a1) of times the manipulator a1 picks in the picking sequence, and the maximum range rgmax of an item. This third parameter is a correlation measure on the preference rankings of the agents. In particular, we provide XP algorithms for parameters n and μ(a1), and we show that the problem is fixed-parameter tractable w.r.t. rgmax and n + μ(a1). Interestingly enough, we show that w.r.t. the single parameters n and μ(a1) it is W[1]-hard.