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].
Achieving Maximin Share and EFX/EF1 Guarantees Simultaneously
Authors: Hannaneh Akrami, Nidhi Rathi
AAAI 2025 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | Our main contribution is to constructively prove the existence of (i) a partial allocation that is both 2/3-MMS and EFX, and (ii) a complete allocation that is both 2/3-MMS and EF1. Our algorithms run in pseudo-polynomial time if the approximation factor for MMS is relaxed to 2/3 ε for any constant ε > 0 and in polynomial time if, in addition, the EFX (or EF1) guarantee is relaxed to (1 δ)-EFX (or (1 δ)-EF1) for any constant δ > 0. |
| Researcher Affiliation | Academia | 1Max Planck Institute for Informatics 2Graduiertenschule Informatik, Universit at des Saarlandes 3Saarland Informatics Campus EMAIL, EMAIL |
| Pseudocode | Yes | Algorithm 1: approx MMS(I), Algorithm 2: approx MMSand EFX(I), Algorithm 3: approx MMSand EF1(I) |
| Open Source Code | No | The paper does not provide any concrete access information to source code (no repository link, explicit code release statement, or code in supplementary materials). |
| Open Datasets | No | The paper discusses fair division instances in a theoretical context and does not utilize or refer to any specific publicly available datasets for experimental evaluation. |
| Dataset Splits | No | The paper focuses on theoretical algorithms and proofs, and as such, does not involve experimental evaluation with dataset splits for training, validation, or testing. |
| Hardware Specification | No | The paper describes theoretical algorithms and provides proofs of existence and approximation factors; it does not report on experimental results that would require specific hardware. |
| Software Dependencies | No | The paper focuses on theoretical algorithm design and analysis, and therefore does not specify any software dependencies with version numbers for experimental replication. |
| Experiment Setup | No | The paper is theoretical, presenting algorithms and proofs without empirical evaluation, and thus does not include details on experimental setup, hyperparameters, or training configurations. |