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 and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in Coakley et alK. L. Coakley, T. Snelleman, H. Hoos, and O. E. Gundersen, "The embrace of open science: An analysis of a decade of AI research and 56 800 conference papers," Under Review, 2026..
Pareto-Optimal Allocation of Indivisible Goods with Connectivity Constraints
Authors: Ayumi Igarashi, Dominik Peters2045-2052
AAAI 2019 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study the problem of finding an allocation that is Pareto-optimal. While it is easy to find an efficient allocation when the underlying graph is a path or a star, the problem is NP-hard for many other graph topologies, even for trees of bounded pathwidth or of maximum degree 3. We show that on a path, there are instances where no Pareto-optimal allocation satisfies envy-freeness up to one good, and that it is NP-hard to decide whether such an allocation exists, even for binary valuations. We also show that, for a path, it is NP-hard to find a Pareto-optimal allocation that satisfies maximin share, but show that a moving-knife algorithm can find such an allocation when agents have binary valuations that have a non-nested interval structure. Table 1: Overview of our complexity results. |
| Researcher Affiliation | Academia | Ayumi Igarashi Kyushu University Fukuoka, Japan EMAIL Dominik Peters University of Oxford Oxford, U.K. EMAIL |
| Pseudocode | No | While algorithms are described conceptually within the proofs (e.g., for paths and stars), they are presented in natural language rather than structured pseudocode blocks or algorithm listings. |
| Open Source Code | No | The paper does not provide a link to or explicitly state the release of any source code implementing the described algorithms or theoretical constructions. |
| Open Datasets | No | This is a theoretical paper and does not use any datasets, thus there is no information about publicly available or open datasets for training. |
| Dataset Splits | No | This is a theoretical paper and does not involve data splits for training, validation, or testing. |
| Hardware Specification | No | This paper is theoretical and describes mathematical proofs and algorithms, not computational experiments. Therefore, it does not mention any hardware specifications. |
| Software Dependencies | No | This paper is theoretical and does not involve computational implementations or experiments that would require specific software dependencies with version numbers. |
| Experiment Setup | No | This is a theoretical paper and does not describe any experimental setup, training configurations, or hyperparameter details. |