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 μ(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 provide XP algorithms for parameters n and μ(a 1 ), and we show that the problem is fixed-parameter tractable w. r. t. r gmax and n + μ(a 1 ). Interestingly enough, we show that w. r. t. the single parameters n and μ(a 1 ) it is W[1]-hard.

Authors

• Michele Flammini
• Hugo Gilbert

Keywords

No keywords are indexed for this paper.