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

The Complexity of Extending Fair Allocations of Indivisible Goods

AAAI 2025 · 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.

Initiates the complexity study of extending partial envy-free allocations of indivisible goods, giving FPT/XP/W[1]-hardness classification by open items, agent types, item types, and number of recipients, plus EF1/EFX extension results.

Problem

Computing envy-free (and EF1/EFX) allocations of indivisible items when part of the allocation is already fixed (the extension setting), under additive valuations, and its parameterized complexity.

Approach

Study envy-free allocation extension via parameterizations (number of open items, agent types, item types, recipients) yielding a sharp dichotomy: FPT with few agent types, W[1]-hard with few item types for open-item parameter, and FPT/XP results for recipient-bounded variants; also shows every envy-free partial allocation extends to EF1 while some EFX partial allocations cannot extend to EF1.

Key results

• Envy-Free Allocation Extension is W[1]-hard when parameterized by number of open items k alone and also by k plus number of item types m_t, while FPT when parameterized by k plus number of agent types n_t.
• Restricted and free EF extension are strongly NP-hard even with p<=2 recipients; both are in XP under unary valuations when parameterized by p plus n_t, and REFAE is FPT by p plus m_t (FEFAE is XP).
• Every envy-free partial allocation can be extended to an EF1 allocation, while there exist EFX partial allocations (2 agents) that cannot be extended to EF1.

Surprising findings

• Fixing a small number of item types does not give FPT for the open-item parameterization, unlike few agent types, which reverses for the recipient parameterization.
• An envy-free partial allocation for 2 agents may not extend to an EFX allocation, in contrast to EFX existence from scratch for 2 agents.

Limitations

• Purely theoretical; no empirical evaluation or implementation.
• Tightness of XP results relies on literature lower bounds for the agent-count parameterization.

Experimental setup

Builds on: Envy Cycle Elimination

Closest papers by meaning

• The Complexity of Fair Division of Indivisible Items with Externalities (AAAI 2024 · similarity 0.95)
• Reachability of Fair Allocations via Sequential Exchanges (AAAI 2024 · similarity 0.92)
• Achieving Maximin Share and EFX/EF1 Guarantees Simultaneously (AAAI 2025 · similarity 0.92)
• Towards Optimal Subsidy Bounds for Envy-Freeable Allocations (AAAI 2024 · similarity 0.92)
• Fair and Efficient Completion of Indivisible Goods (AAAI 2025 · similarity 0.91)
• (Almost Full) EFX for Three (and More) Types of Agents (AAAI 2025 · similarity 0.91)