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

2021.04.07 | 10:07
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.

« Vissza a listához

Eseménynaptár

H

K

Sz

Cs

P

Szo

V

26
27
28
29
30
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
2
3
4
5
6
2021 Május

Kiemelt híreink

Call for Papers - 12th Annual Financial Market Liquidity Conference - Budapest, Hungary 11-12th November 2021

Call for Papers - 12th Annual Financial Market Liquidity Conference - Budapest, Hungary 11-12th November 2021 The Department of Finance, Corvinus University of Budapest and the Game Theory Research Group, Centre for Economic and Regional Studies are organizing the Annual Financial Market Liquidity Conference for the twelfth time. This year, Corvinus University of Budapest hosts the conference both onsite as well as on a virtual conferencing platform allowing for a hybrid and flexible format.

Egy évtizeddel a forradalmi hullámot követően javultak-e az arab államok gazdasági kilátásai? - Szigetvári Tamás válaszol a Portfolio KRTK Blogjában

Egy évtizeddel a forradalmi hullámot követően javultak-e az arab államok gazdasági kilátásai? - Szigetvári Tamás válaszol a Portfolio KRTK Blogjában Tíz éve, 2011 tavaszán rengette meg az arab tavaszként aposztrofált forradalmi hullám a Közel-Kelet és Észak-Afrika autoriter rezsimjeit. A Tunéziában kipattant szikra Egyiptomban, Líbiában, Jemenben, Szíriában és Bahreinben is komolyan megrengette az addigi politikai berendezkedést, de szinte az összes arab országban a kormányzat elleni tüntetésekhez, utcai demonstrációkhoz vezetett. Az arab tavasz elsődleges oka a romló életkörülményekben, a perspektívák hiányában volt keresendő – de vajon egy évtizeddel a forradalmi hullámot követően változott-e a helyzet, javultak-e az arab államok gazdasági kilátásai?

Fertő Imre és Štefan Bojnec cikke megjelent a NEW MEDIT szakfolyóiratban

Fertő Imre és Štefan Bojnec cikke megjelent a NEW MEDIT szakfolyóiratban Published online: 6 April 2021 in New Medit, A Mediterranean Journal of Economics, Agriculture and Environment, Vol 20 N. 1 (2021)

További híreink »