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.
Parameterized Complexity of Manipulating Sequential Allocation
Flammini Michele
;
2020-01-01
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 [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.File | Dimensione | Formato | |
---|---|---|---|
2020_24EConfAI_ECAI_325_99_Flammini.pdf
accesso aperto
Tipologia:
Versione Editoriale (PDF)
Licenza:
Creative commons
Dimensione
714.41 kB
Formato
Adobe PDF
|
714.41 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.