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]
Dividing Conflicting Items Fairly
Authors: Ayumi Igarashi, Pasin Manurangsi, Hirotaka Yoneda
IJCAI 2025 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We significantly extend this result by establishing that a maximal EF1 allocation exists for any graph when the two agents have monotone valuations. To compute such an allocation, we present a polynomial-time algorithm for additive valuations, as well as a pseudo-polynomial time algorithm for monotone valuations. Moreover, we complement our findings by providing a counterexample demonstrating a maximal EF1 allocation may not exist for three agents with monotone valuations; further, we establish NP-hardness of determining the existence of such allocations for every fixed number n 3 of agents. All of our results for goods also apply to the allocation of chores. |
| Researcher Affiliation | Collaboration | 1University of Tokyo 2Google Research EMAIL, EMAIL, EMAIL |
| Pseudocode | Yes | Algorithm 1 CHAINEF1(S; G = (M, E), v) Algorithm 2 SWAPEF1(G = (M, E), v) |
| Open Source Code | No | The paper does not contain any explicit statement about providing open-source code for the methodology described, nor does it provide a link to a code repository. |
| Open Datasets | No | The paper defines a theoretical problem instance with M = [m] goods and G = (M, E) as an undirected graph. It does not mention using or providing access information for any publicly available or open dataset for experimental purposes. |
| Dataset Splits | No | The paper is theoretical and does not conduct experiments on a specific dataset, therefore, it does not provide dataset split information. |
| Hardware Specification | No | The paper is theoretical and does not describe any experiments that would require specific hardware. Therefore, no hardware specifications are provided. |
| Software Dependencies | No | The paper is theoretical and focuses on algorithms and proofs. It does not describe any experimental implementation or software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not present an experimental setup with specific details like hyperparameters or training configurations. |