hu / en

Schlotter Ildikó szerzőtársakkal írt tudományos cikke megjelent az Algorithmica szakfolyóiratban

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.

2023

Feb

03

H

K

Sz

Cs

P

Sz

V

30

31

1

2

3

4

5

7

8

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

1

2

3

4

5

Következő hónap >