Multivariate Algorithmics for Eliminating Envy by Donating Goods

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F22%3A00358172" target="_blank" >RIV/68407700:21240/22:00358172 - isvavai.cz</a>

Result on the web

<a href="https://doi.org/10.5555/3535850.3535866" target="_blank" >https://doi.org/10.5555/3535850.3535866</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.5555/3535850.3535866" target="_blank" >10.5555/3535850.3535866</a>

Result language

angličtina

Original language name

Multivariate Algorithmics for Eliminating Envy by Donating Goods

Original language description

Fairly dividing a set of indivisible resources to a set of agents is of utmost importance in some applications. However, after an allocation has been implemented the preferences of agents might change and envy might arise. We study the following problem to cope with such situations: Given an allocation of indivisible resources to agents with additive utility-based preferences, is it possible to socially donate some of the resources (which means removing these resources from the allocation instance) such that the resulting modified allocation is envy-free (up to one good). We require that the number of deleted resources and/or the caused utilitarian welfare loss of the allocation are bounded. We conduct a thorough study of the (parameterized) computational complexity of this problem considering various natural and problem-specific parameters (e.g., the number of agents, the number of deleted resources, or the maximum number of resources assigned to an agent in the initial allocation) and different preference models, including unary and 0/1-valuations. In our studies, we obtain a rich set of (parameterized) tractability and intractability results and discover several surprising contrasts, for instance, between the two closely related fairness concepts envy-freeness and envy-freeness up to one good and between the influence of the parameters maximum number and welfare of the deleted resources.

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

—

OECD FORD branch

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project

<a href="/en/project/EF16_019%2F0000765" target="_blank" >EF16_019/0000765: Research Center for Informatics</a><br>

Continuities

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year

2022

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection

21st International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2022

ISBN

978-1-4503-9213-6

ISSN

1548-8403

e-ISSN

—

Number of pages

9

Pages from-to

127-135

Publisher name

IFAAMAS

Place of publication

County of Richland

Event location

Aukland, Virtual

Event date

May 9, 2022

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—