Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in [1]
The Complexity of Extending Fair Allocations of Indivisible Goods
Authors: Argyrios Deligkas, Eduard Eiben, Robert Ganian, Tiger-Lily Goldsmith, Stavros D. Ioannidis
AAAI 2025 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We initiate the study of computing envy-free allocations of indivisible items in the extension setting, i.e., when some part of the allocation is fixed and the task is to allocate the remaining items. Given the known NP-hardness of the problem, we investigate whether and under which conditions one can obtain fixed-parameter algorithms for computing a solution in settings where most of the allocation is already fixed. Our results provide a broad complexity-theoretic classification of the problem which includes: (a) fixed-parameter algorithms tailored to settings with few distinct types of agents or items; (b) lower bounds which exclude the generalization of these positive results to more general settings. We conclude by showing that unlike when computing allocations from scratch the non-algorithmic question of whether more relaxed EFX allocations exist can be completely resolved in the extension setting. |
| Researcher Affiliation | Academia | 1Department of Computer Science, Royal Holloway, University of London, UK 2Algorithms and Complexity Group, TU Wien, Austria EMAIL, EMAIL |
| Pseudocode | No | The paper includes 'Proof Sketch' sections for theorems (e.g., Theorem 1, Theorem 2, Theorem 3, Theorem 4, Theorem 5, Proposition 1, Proposition 2) that describe the logical steps and reasoning for the mathematical arguments. However, there are no clearly labeled figures, blocks, or sections titled 'Pseudocode' or 'Algorithm' presenting structured steps in a code-like format. |
| Open Source Code | No | The paper does not contain any explicit statements about releasing source code, direct links to code repositories (e.g., GitHub), or mentions of code being available in supplementary materials for the methodology described. |
| Open Datasets | No | The paper is theoretical, defining abstract problem inputs such as 'A set M of indivisible items, a set N of n agents with additive valuations'. It does not refer to any specific named or publicly available datasets that were used for empirical evaluation. Therefore, no access information for open datasets is provided. |
| Dataset Splits | No | The paper is theoretical and does not involve experiments on datasets, thus there is no mention of training/test/validation dataset splits. |
| Hardware Specification | No | The paper focuses on theoretical complexity analysis and algorithm design. It does not describe any experimental setup or specify the hardware used to run experiments. |
| Software Dependencies | No | The paper is theoretical and does not describe any experimental implementation. Therefore, it does not list specific software dependencies with version numbers (e.g., programming languages, libraries, or solvers). |
| Experiment Setup | No | The paper presents theoretical results, theorems, and proofs related to the complexity of fair allocation problems. It does not describe any experimental setup, hyperparameters, model initialization, or training schedules because no empirical experiments were conducted. |