Research map / Learning theory and algorithms / Submodular and game algorithms
Several Stories about High-Multiplicity EFx Allocation (Student Abstract)
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
The paper proves that finding EFx+PO allocations is NP-hard for two agents, proposes an ILP-based algorithm whose runtime depends on the number of EFx allocations, and empirically counts EFx allocations on randomly generated instances.
Problem
Finding allocations of indivisible goods that are simultaneously envy-free up to any item (EFx) and Pareto-optimal (PO), with a focus on algorithmic complexity and practical solvability.
Approach
Formulates EFx restrictions for two agents with item types as an integer linear program, iteratively finds EFx allocations, checks PO, and adds constraints to exclude already-examined allocations; runtime is bounded in terms of the number of EFx allocations, which is shown to be bounded by a combinatorial expression.
Key results
- Proves that the existence of an EFx+PO allocation is NP-hard even for two agents.
- Gives an upper bound on the number of EFx allocations for two agents of (ceil((m+k)/k))^k and an example with Omega lower-bound growth.
- Empirically the number of EFx allocations is much smaller than the upper bound; even the 0.99 quantile is well below it (max weight 10, k=4).
Surprising findings
- Despite the high theoretical upper bound on EFx allocation counts, empirical counts are significantly lower in practice.
Limitations
- Algorithm's runtime depends on the number of EFx allocations, which is only empirically small; no probabilistic upper bound proven.
- Experiments limited to smaller instances with two agents.
- Ignores the complete PO-check performance; percentage of EFx allocations that are PO is not bounded theoretically.
Experimental setup
Datasets: randomly generated synthetic fair division instances (own generator, uniform over instances with k item types and bounde
Metrics: number of EFx allocations runtime estimate of ILP fraction of EFx allocations that are PO
Builds on: EFx (Caragiannis et al. 2016) Bredereck et al. 2021 ILP for EF and PO Lenstra integer programming algorithm
Closest papers by meaning
- Achieving Maximin Share and EFX/EF1 Guarantees Simultaneously (AAAI 2025 · similarity 0.90)
- Understanding EFX Allocations: Counting and Variants (AAAI 2025 · similarity 0.90)
- On Optimal Tradeoffs between EFX and Nash Welfare (AAAI 2024 · similarity 0.89)
- EF2X Exists for Four Agents (AAAI 2025 · similarity 0.88)
- Epistemic EFX Allocations Exist for Monotone Valuations (AAAI 2025 · similarity 0.88)
- The Complexity of Fair Division of Indivisible Items with Externalities (AAAI 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.