Research map / Learning theory and algorithms / Submodular and game algorithms

Approximate Envy-Free Allocations up to any k Goods

NeurIPS 2026 · Learning theory and algorithms › Submodular and game algorithms · approach: Fair division of indivisible goods · 0 citations (OpenAlex)

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.

Generalizes the 3PA/PPA approximate-EFX algorithm to approximate EFkX allocations, giving (k+1)/(k+2)-EFkX for any number of agents with additive valuations, plus 2/3-EFX for 8 agents and NP-completeness of EFkX orientations.

Problem

Existence and polynomial-time computation of approximate envy-free allocations up to any k goods (alpha-EFkX) for indivisible goods with additive valuations, and the complexity of EFkX graph orientations.

Approach

Generalizes the property-preserving partial allocation (PPA) algorithm to bundles of size k+1 and a single modified envy graph with proxy valuations, followed by a new algorithm (AEC) for allocating critical goods and a partial-to-full allocation lemma; the critical-goods step works for any number of agents once k>=2.

Key results

• For any k>2 (and k=2 via the same algorithm), (k+1)/(k+2)-EFkX allocations exist for any number of additive agents and are computable in polynomial time; in particular 3/4-EF2X for any number of agents.
• A 2/3-EFX allocation is computed in polynomial time for instances with up to 8 agents, improving the previous 7-agent bound.
• EFkX orientations on graphs need not exist for k = Omega(n), and deciding their existence is NP-complete for any k <= n-1.

Surprising findings

• The original PPA polynomial-time proof has an oversight regarding edge reduction in the enhanced envy graph; the modified envy graph used here corrects it.

Limitations

• Result for k=1 only extends EFX-type guarantee from 7 to 8 agents; general EFX remains open.
• Guarantees are approximate (alpha < 1) rather than exact EFkX.
• Orientation hardness results use constructed instances; the paper does not resolve the complexity of EF1 orientations.

Experimental setup

Baselines: k-RoundRobin with EnvyCycleElimination 2/3-EFX for 7 agents (Amanatidis et al., 2024)

Builds on: PPA algorithm (Amanatidis et al., 2024) envy cycle elimination EFX existence results EF2X allocations

Closest papers by meaning

• (Almost Full) EFX for Three (and More) Types of Agents (AAAI 2025 · similarity 0.93)
• EF2X Exists for Four Agents (AAAI 2025 · similarity 0.92)
• The Complexity of Extending Fair Allocations of Indivisible Goods (AAAI 2025 · similarity 0.91)
• Achieving Maximin Share and EFX/EF1 Guarantees Simultaneously (AAAI 2025 · similarity 0.90)
• Epistemic EFX Allocations Exist for Monotone Valuations (AAAI 2025 · similarity 0.90)
• Understanding EFX Allocations: Counting and Variants (AAAI 2025 · similarity 0.90)