Pareto-Optimal Allocation of Indivisible Goods with Connectivity Constraints
Authors: Ayumi Igarashi, Dominik Peters2045-2052
AAAI 2019 | Conference PDF | Archive PDF | Plain Text | 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 igarashi@agent.inf.kyushu-u.ac.jp Dominik Peters University of Oxford Oxford, U.K. dominik.peters@cs.ox.ac.uk |
| 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. |