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].
EF2X Exists for Four Agents
Authors: Arash Ashuri, Vasilis Gkatzelis, Alkmini Sgouritsa
AAAI 2025 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study the fair allocation of indivisible goods among a group of agents, aiming to limit the envy between any two agents. The central open problem in this literature, which has proven to be extremely challenging, is regarding the existence of an EFX allocation... Our main result shows that EF2X allocations exist for any instance with four agents... Our proof is constructive, proposing an algorithm that computes such an allocation in pseudo-polynomial time. Furthermore, for instances involving three agents we provide an algorithm that computes an EF2X allocation in polynomial time... Instead of a purely existential argument, we provide a constructive proof using an algorithm that computes an EF2X allocation in pseudo-polynomial time. |
| Researcher Affiliation | Academia | Arash Ashuri1, Vasilis Gkatzelis2, Alkmini Sgouritsa3, 1Sharif University of Technology, Iran 2Drexel University, USA 3Athens University of Economics and Business, and Archimedes/Athena RC, Greece EMAIL, EMAIL, EMAIL |
| Pseudocode | Yes | 3 Overview of Algorithm for Four Agents Our main result (Theorem 1) proves the existence of an EF2X allocation for instances involving an arbitrary number of goods and four agents with cancelable valuations; in fact, one of them can have an arbitrary monotone valuation. Theorem 1: For every instance involving four agents with cancelable valuation functions and any number of goods, there exists an EF2X allocation and we can compute one in pseudo-polynomial time. As the theorem statement suggests, instead of a purely existential argument, we provide a constructive proof using an algorithm that computes an EF2X allocation in pseudopolynomial time. The algorithm starts with some arbitrary initial partition of the goods into four bundles and it gradually manipulates this until it reaches a partition that is EF2X-feasible... Figure 1 illustrates the high-level structure of the algorithm by providing a node for each stage that a partition X may be in, and a directed edge between two stages for each step that transforms a partition X to X. E.g., the edge from stage B1 to stage B2 corresponds to a transformation that takes as input a partition X in stage B1 and returns a partition X in stage B2 (see Theorem 22). The algorithm starts with an arbitrary initial partition and it uses the PR algorithm to get a partition whose bundles are all EFX-feasible for agent 1. |
| Open Source Code | No | The paper does not contain any explicit statements about the release of source code, nor does it provide links to code repositories. The paper mentions a "full version" (Ashuri, Gkatzelis, and Sgouritsa 2024) for technical details, but this does not constitute a code release. |
| Open Datasets | No | The paper is theoretical in nature, focusing on the existence of fair allocations and algorithms to compute them. It does not use or refer to any specific datasets for experimental evaluation, thus there is no mention of publicly available or open datasets. |
| Dataset Splits | No | The paper is theoretical, presenting proofs and algorithms related to fair allocation. It does not involve experimental evaluation with datasets, and therefore, no training/test/validation dataset splits are mentioned. |
| Hardware Specification | No | The paper is purely theoretical, focusing on mathematical proofs and algorithm design. It does not describe any experimental evaluations that would require specific hardware, and thus no hardware specifications are mentioned. |
| Software Dependencies | No | The paper presents theoretical work on algorithms for fair allocation. It does not describe any implementation details or experimental setups that would require specific software dependencies with version numbers. |
| Experiment Setup | No | The paper focuses on theoretical proofs and algorithm design for fair allocation. It does not include any experimental results or evaluations, and therefore, no details about an experimental setup, hyperparameters, or system-level training settings are provided. |