A new study by Ildikó Schlotter and co-authors published in Algorithmica

04/07/2021 | 10:18
A new study by Ildikó Schlotter and co-authors published in Algorithmica

Published: 26 March 2021

Obtaining a Proportional Allocation by Deleting Items

Britta Dorn - Ronald de Haan - Ildikó Schlotter

Abstract

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 W[3] -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 π in advance as part of the input.

 

« Back to list

Featured news

A new study by Ildikó Schlotter and co-authors published in Algorithmica

A new study by Ildikó Schlotter and co-authors published in Algorithmica Published: 26 March 2021

Research article by Erik Braun, Zita Iloskics et. al in Regional Statistics

Research article by Erik Braun, Zita Iloskics et. al in Regional Statistics Regional Statistics, Vol. 11. No. 2. 2021 - Peer-reviewed scientific periodical, 4 numbers published in English every year. Publisher: Hungarian Central Statistical Office.

Balázs Muraközy and Gábor Békés in the Blog of the Strategic Management Society

Balázs Muraközy and Gábor Békés in the Blog of the Strategic Management Society Date: March 10, 2021

More news »