The Complexity of Fair Division of Indivisible Items with Externalities
Authors: Argyrios Deligkas, Eduard Eiben, Viktoriia Korchemna, Šimon Schierreich
AAAI 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study the computational complexity of fairly allocating a set of indivisible items under externalities. 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 fixedparameter tractable. |
| Researcher Affiliation | Academia | Royal Holloway, University of London 2TU Wien 3Czech Technical University in Prague |
| Pseudocode | No | The paper does not contain structured pseudocode or algorithm blocks. It provides proof sketches and theoretical discussions. |
| Open Source Code | No | The paper does not provide any concrete access to source code for the methodology described. |
| Open Datasets | No | The paper is theoretical and does not involve datasets or experimental training. Therefore, no information about public datasets is provided. |
| Dataset Splits | No | The paper is theoretical and does not involve datasets or experimental validation. Therefore, no information about dataset splits is provided. |
| Hardware Specification | No | The paper is theoretical and does not describe any experiments that would require specific hardware. Therefore, no hardware specifications are mentioned. |
| Software Dependencies | No | The paper is theoretical and does not describe any experiments or implementations that would require specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe any experimental setup, hyperparameters, or training configurations. |