Fair and Efficient Completion of Indivisible Goods

Vishwa Prakash Hv, Ayumi Igarashi, Rohit VaishAAAI 2025 · DOI

TL;DR

This paper introduces and analyzes the "fair and efficient completion" problem for indivisible goods, where some items are already assigned (frozen). They investigate the computational complexity of achieving various fairness and efficiency goals (like envy-freeness and Pareto optimality) when allocating the remaining items, finding that some goals become significantly harder with frozen items.

What Problem Does This Paper Address?

Imagine you're dividing up a set of indivisible items – say, assigning tasks to people or allocating limited resources. The standard "fair division" problem assumes all items are up for grabs. However, in many real-world scenarios, some items are already pre-assigned or "frozen." For example, in a course allocation system, certain mandatory courses might already be assigned to specific student groups. This paper tackles the challenge of finding a "completion" – an allocation of the remaining items – that satisfies fairness and efficiency criteria, given these pre-assigned "frozen" items. The core question is: how does the presence of frozen items affect the difficulty of achieving fair and efficient outcomes, and what are the computational trade-offs?

Methods

The authors formulate the "completion problem" as a computational task: given a partial allocation of frozen goods, does a completion exist that satisfies a given property (e.g., envy-freeness up to one good, proportionality up to one good, maximin share, Pareto optimality)? They analyze the computational complexity of this problem under different assumptions about agents' preferences, specifically focusing on additive valuations and their subclasses: binary additive and lexicographic valuations.

Their approach involves:

  • Formalizing the problem: Defining "frozen allocation," "completion," and how they combine to form a final allocation.
  • Complexity analysis: Using reductions from known hard problems (like EQUITABLE COLORING and RAINBOW COLORING) to prove NP-hardness for certain fairness notions.
  • Algorithmic design: Developing polynomial-time algorithms for cases where the completion problem is tractable, often leveraging network flow techniques or specific properties of the valuation classes.
  • Case analysis: Systematically examining different combinations of fairness criteria (EF1, Prop1, MMS, PO) and valuation types (binary additive, lexicographic, general additive).

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and computational complexity rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Frozen goods significantly complicate fairness: The presence of pre-assigned items can make achieving fairness properties, especially envy-freeness, much harder than in the standard fair division setting.
  • Valuation types matter greatly: The computational complexity of the completion problem varies dramatically depending on the type of agent valuations. Binary additive and lexicographic valuations, while restricted, still present significant challenges for envy-freeness.
  • Threshold-based fairness is more tractable: Notions like proportionality up to one good (Prop1) and maximin share (MMS) are generally more amenable to efficient algorithms in the completion setting compared to envy-based notions like EF1.
  • Pareto optimality interacts interestingly: Combining Pareto optimality (PO) with other fairness criteria doesn't always simplify the problem, but in some cases (like with binary additive valuations and a Pareto optimal frozen allocation), it can guarantee the existence of a solution.
  • Envy cycles are problematic: Even if a frozen allocation is "fair" (EF1), if the envy relationships among agents form a cycle, finding an EF1 completion becomes computationally hard.

Key Results

The paper presents a detailed complexity landscape for the fair and efficient completion problem:

  • Binary Additive Valuations:
    • EF1-COMPLETION is NP-complete, even for Pareto optimal frozen allocations.
  • Prop1-COMPLETION and MMS-COMPLETION are solvable in polynomial time.
  • MMS+PO and Prop1+PO completions are also polynomial-time solvable.
  • If the frozen allocation is Pareto optimal, an MMS+PO completion is guaranteed to exist and be computable in polynomial time.
  • Lexicographic Valuations:
    • EF1-COMPLETION is NP-complete.
  • Prop1-COMPLETION is polynomial-time solvable.
  • MMS-COMPLETION is polynomial-time solvable.
  • General Additive Valuations:
    • EF1-COMPLETION and Prop1-COMPLETION are NP-complete, even for just two agents.
  • MMS-COMPLETION is NP-hard for two agents.
  • The paper also shows that a-MMS completions may not exist even for "fair" frozen allocations.

Limitations and Future Work

The authors acknowledge several avenues for future research:

  • Other resource types: Extending the study to include chores, mixed divisible and indivisible goods, or combinations of goods and chores.
  • Forbidden assignments: While this paper focuses on "frozen" (pre-assigned) items, future work could explore "forbidden" assignments, where certain items cannot be assigned to specific agents in any completion.
  • Approximation: Investigating approximation algorithms for problems that are proven to be intractable.
  • Specific valuation classes: Exploring the completion problem under other valuation structures beyond additive, binary additive, and lexicographic.
  • Guarantees for a-MMS: Further understanding the conditions under which a-MMS completions exist and can be found.

Summary updated

BibTeX
@inproceedings{hv2025fair,
  author = {Vishwa Prakash HV and Ayumi Igarashi and Rohit Vaish},
  title = {{Fair and Efficient Completion of Indivisible Goods}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.1609/aaai.v39i13.33537},
}
Figure