How to Resolve Envy by Adding Goods
Authors: Matthias Bentert, Robert Bredereck, Eva Deltl, Pallavi Jain, Leon Kellerhals
IJCAI 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study the computational complexity of alleviating unfairness by adding items from a pool of goods to an initial allocation. Herein, we focus solely on envy-freeness and additive, non-negative valuations. ... We give a characterization of the instances where envy can be resolved by adding an arbitrary number of copies of the items in the pool. From this characterization, we derive a polynomialtime algorithm returning a respective solution if it exists. If the number of copies or the total number of added items are bounded, the problem becomes computationally intractable even in various restricted cases. We perform a parameterized complexity analysis, focusing on the number of agents and the pool size as parameters. |
| Researcher Affiliation | Academia | Matthias Bentert1 , Robert Bredereck2 , Eva Deltl2 , Pallavi Jain3 , Leon Kellerhals2 1University of Bergen, Norway 2TU Clausthal, Germany 3Indian Institute of Technology Jodhpur, India EMAIL, EMAIL, EMAIL |
| Pseudocode | No | The paper describes algorithms and their complexity verbally (e.g., in the proof of Theorem 3: "Our algorithm proceeds in two phases."), but does not present any structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not contain any explicit statement about releasing source code, nor does it provide any links to a code repository. |
| Open Datasets | No | This paper is theoretical and focuses on computational complexity and algorithm design for fair allocation problems. It does not use or refer to any datasets for experimental evaluation. |
| Dataset Splits | No | This paper is theoretical and does not involve experimental evaluation using datasets, therefore, no dataset splits are discussed or provided. |
| Hardware Specification | No | The paper is theoretical, analyzing computational complexity and algorithms. It does not describe any experiments that would require specific hardware, hence no hardware specifications are mentioned. |
| Software Dependencies | No | The paper is theoretical, focusing on mathematical proofs and algorithmic complexity. It does not describe any implementation details or mention specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is purely theoretical, presenting algorithms, proofs, and complexity analysis. It does not conduct experiments, and therefore, no experimental setup details such as hyperparameters or training configurations are provided. |