Epistemic EFX Allocations Exist for Monotone Valuations
Authors: Hannaneh Akrami, Nidhi Rathi
AAAI 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We answer the above question affirmatively and establish computational hardness and information-theoretic lower bounds for finding EEFX allocations: 1. EEFX allocations are guaranteed to exist for any fair division instance with an arbitrary number of agents having general monotone valuations; see Theorem 3.5. 2. Exponentially (in the number of goods) many valuation queries is required by any deterministic algorithm to compute an EEFX allocation for fair division instances with an arbitrary number of agents with identical submodular valuations; see Theorem 4.7. 3. The problem of computing EEFX allocations for fair division instances with an arbitrary number of agents having identical submodular valuations is PLS-hard; see Theorem 4.8. |
| Researcher Affiliation | Academia | Hannaneh Akrami1,2, Nidhi Rathi1,3 1Max Planck Institute for Informatics 2Graduiertenschule Informatik, Universit at des Saarlandes 3Saarland Informatics Campus EMAIL, EMAIL |
| Pseudocode | Yes | Algorithm 1: ALG = EEFX(I) Input: A fair division instance I = (N, M, V) where agent i N = [n] has monotone valuation vi over the set of items M Output: An allocation X = (X1, X2, . . . , Xn) |
| Open Source Code | No | The paper does not contain any explicit statements about code availability, nor does it provide links to a code repository. |
| Open Datasets | No | The paper is theoretical and focuses on proving the existence of allocations and computational hardness. It discusses "fair division instances" as theoretical constructs rather than empirical datasets used in experiments. There is no mention of specific datasets or access information for them. |
| Dataset Splits | No | The paper is theoretical and does not use empirical datasets, therefore, there is no information about dataset splits. |
| Hardware Specification | No | The paper is theoretical and focuses on mathematical proofs and algorithmic analysis, not empirical experiments. Therefore, no hardware specifications are mentioned. |
| Software Dependencies | No | The paper is theoretical and does not describe any implementation details that would require specific software dependencies or versions. |
| Experiment Setup | No | The paper is theoretical and focuses on existence proofs and computational hardness, not empirical experiments. Therefore, there are no details on experimental setup or hyperparameters. |