The Complexity of Fair Division of Indivisible Items with Externalities

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F24%3A00369990" target="_blank" >RIV/68407700:21240/24:00369990 - isvavai.cz</a>

Result on the web

<a href="https://doi.org/10.1609/aaai.v38i9.28822" target="_blank" >https://doi.org/10.1609/aaai.v38i9.28822</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1609/aaai.v38i9.28822" target="_blank" >10.1609/aaai.v38i9.28822</a>

Result language

angličtina

Original language name

The Complexity of Fair Division of Indivisible Items with Externalities

Original language description

We study the computational complexity of fairly allocating a set of indivisible items under externalities. In this recently-proposed setting, in addition to the utility the agent gets from their bundle, they also receive utility from items allocated to other agents. We focus on the extended definitions of envy-freeness up to one item (EF1) and of envy-freeness up to any item (EFX), and we provide the landscape of their complexity for several different scenarios. We prove that it is NP-complete to decide whether there exists an EFX allocation, even when there are only three agents, or even when there are only six different values for the items. We complement these negative results by showing that when both the number of agents and the number of different values for items are bounded by a parameter the problem becomes fixed-parameter tractable. Furthermore, we prove that two-valued and binary-valued instances are equivalent and that EFX and EF1 allocations coincide for this class of instances. Finally, motivated from real-life scenarios, we focus on a class of structured valuation functions, which we term agent/item-correlated. We prove their equivalence to the "standard" setting without externalities. Therefore, all previous results for EF1 and EFX apply immediately for these valuations.

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/EH22_008%2F0004590" target="_blank" >EH22_008/0004590: Robotics and advanced industrial production</a><br>

Continuities

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>S - Specificky vyzkum na vysokych skolach

Publication year

2024

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

Proceedings of the 38th AAAI Conference on Artificial Intelligence

ISBN

—

ISSN

2159-5399

e-ISSN

2374-3468

Number of pages

9

Pages from-to

9653-9661

Publisher name

AAAI Press

Place of publication

Menlo Park

Event location

Vancouver

Event date

Feb 20, 2024

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

001241512400025