# Parameterized Complexity of Manipulating Sequential Allocation

arXiv: https://arxiv.org/abs/1909.08920 · HTML: https://mlsanity.com/paper/1909.08920/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Sep 2019.

## Built on by (most cited first, 1 of 1)

- [Constrained Serial Dictatorships can be Fair](https://mlsanity.com/paper/2301.06086/) (2023)

## Abstract (arXiv)

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 μ(a1) of times the manipulator a1 picks in the picking sequence, and the maximum range mathttrgmax 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 μ(a1) is a constant, and that it is fixed-parameter tractable w.r.t. mathttrgmax and n+μ(a1). Interestingly enough, we show that w.r.t. the single parameters n and μ(a1) 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.