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 [1].
Fair Division of Indivisible Goods for a Class of Concave Valuations
Authors: Bhaskar Ray Chaudhury, Yun Kuen Cheung, Jugal Garg, Naveen Garg, Martin Hoefer, Kurt Mehlhorn
JAIR 2022 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | Our main contribution is a polynomial-time algorithm to compute an allocation x that is e1/e 1.445-approximation of the optimal NSW when the agents have CASC valuation functions. The allocation x our algorithm computes is also approximately EF1, i.e., the allocation is 1/(2 + γ)-EF1 such that for any two agents i and k, ui(xi) 1/(2 + γ) ui(xk \ {g}) for some g xk for any given constant γ > 0. Furthermore, x is also (1 + γ/4)-approximately Pareto-optimal when the agents have uncapped valuation functions... In this work, we present a polynomial-time algorithm that computes an approximately NSW-optimal allocation, while the allocation also approximately satisfies Pareto-optimality and EF1, for instances where the agents have CASC valuation functions. |
| Researcher Affiliation | Academia | Bhaskar Ray Chaudhury EMAIL Univ. of Illinois at Urbana-Champaign, USA Yun Kuen Cheung EMAIL Royal Holloway University of London, United Kingdom Jugal Garg EMAIL Univ. of Illinois at Urbana-Champaign, USA Naveen Garg EMAIL IIT Delhi, India Martin Hoefer EMAIL Goethe-Universit at Frankfurt am Main, Germany Kurt Mehlhorn EMAIL MPI for Informatics, Saarland Informatics Campus, Germany |
| Pseudocode | Yes | Algorithm 1: Approximate the NSW for Capped Additively Separable Concave Valuations |
| Open Source Code | No | The paper does not contain any explicit statement about releasing source code for the methodology described, nor does it provide a link to a code repository or mention code in supplementary materials. |
| Open Datasets | No | The paper focuses on theoretical contributions related to fair division algorithms and valuation functions. It defines a problem setting with agents and goods, but it does not use or refer to any specific, publicly available datasets for experimental evaluation. The examples provided (e.g., in Section 4.3) are illustrative and hypothetical, not empirical evaluations on real-world data. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical experiments using datasets, so there is no mention of dataset splits for training, validation, or testing. |
| Hardware Specification | No | The paper is theoretical, presenting algorithms and their analysis rather than empirical experiments. Therefore, no hardware specifications for running experiments are mentioned. |
| Software Dependencies | No | The paper presents a theoretical algorithm and its analysis. It does not describe an implementation or empirical evaluation, thus no specific software dependencies or version numbers are mentioned. |
| Experiment Setup | No | The paper is theoretical and focuses on algorithmic design and approximation guarantees. It does not describe an experimental setup with hyperparameters, model initialization, or training schedules because no empirical experiments are conducted. |