Cargando…

Obtaining a Proportional Allocation by Deleting Items

We consider the following control problem on fair allocation of indivisible goods. Given a set I of items and a set of agents, each having strict linear preferences over the items, we ask for a minimum subset of the items whose deletion guarantees the existence of a proportional allocation in the re...

Descripción completa

Detalles Bibliográficos
Autores principales: Dorn, Britta, de Haan, Ronald, Schlotter, Ildikó
Formato: Online Artículo Texto
Lenguaje:English
Publicado: Springer US 2021
Materias:
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC8550255/
https://www.ncbi.nlm.nih.gov/pubmed/34720294
http://dx.doi.org/10.1007/s00453-020-00794-4
Descripción
Sumario:We consider the following control problem on fair allocation of indivisible goods. Given a set I of items and a set of agents, each having strict linear preferences over the items, we ask for a minimum subset of the items whose deletion guarantees the existence of a proportional allocation in the remaining instance; we call this problem Proportionality by Item Deletion (PID). Our main result is a polynomial-time algorithm that solves PID for three agents. By contrast, we prove that PID is computationally intractable when the number of agents is unbounded, even if the number k of item deletions allowed is small—we show that the problem is [Formula: see text] -hard with respect to the parameter k. Additionally, we provide some tight lower and upper bounds on the complexity of PID when regarded as a function of |I| and k. Considering the possibilities for approximation, we prove a strong inapproximability result for PID. Finally, we also study a variant of the problem where we are given an allocation [Formula: see text] in advance as part of the input, and our aim is to delete a minimum number of items such that [Formula: see text] is proportional in the remainder; this variant turns out to be [Formula: see text] -hard for six agents, but polynomial-time solvable for two agents, and we show that it is [Formula: see text] -hard when parameterized by the number k of