Research map / Learning theory and algorithms / Submodular and game algorithms
Fair and Efficient Completion of Indivisible Goods
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.
Formulates fair and efficient completion of indivisible goods (given frozen partial allocation) and maps the complexity of EF1, Prop1, MMS and PO variants under binary additive, lexicographic and general additive valuations.
Problem
Given a partial (frozen) allocation of indivisible goods, decide whether the remaining goods can be allocated so that the complete allocation satisfies fairness (EF1, Prop1, MMS) and/or Pareto optimality.
Approach
Treats pre-assigned (frozen) goods as fixed and studies the completion problem, adapting MMS thresholds to the frozen setting (MMS value computed by completing only unallocated goods), and giving a complexity map contrasting completion with the standard problem.
Key results
- For binary additive valuations, EF1 completion is NP-complete even when the frozen allocation is Pareto optimal, via reduction from Equitable Coloring.
- For binary additive valuations, MMS and Prop1 completion (and with PO) are solvable in polynomial time via a flow network with lower quotas; MMS+PO always exists if the frozen allocation is PO.
- For general additive valuations, EF1 and Prop1 completion are NP-complete already for two agents, and no alpha-MMS completion exists for any alpha in (0,1].
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| add frozen goods to the standard EF1 allocation problem | EF1 completion with binary additive valuations · EF1 completion, binary additive | computational complexity: Poly -> NP-complete | Hurt |
| add frozen goods to the standard EF1 allocation problem | EF1 completion with lexicographic valuations · EF1 completion, lexicographic | computational complexity: Poly -> NP-complete | Hurt |
| add frozen goods to the standard PROP1 allocation problem | PROP1 completion with general additive valuations · PROP1 completion, general additive | computational complexity: Poly -> NP-complete | Hurt |
| restrict valuations to binary additive | PROP1 completion · PROP1 completion, binary additive | computational complexity: NP-complete -> polynomial time | Helped |
| restrict valuations to binary additive | MMS completion · MMS completion, binary additive | computational complexity: NP-hard -> polynomial time | Helped |
| restrict valuations to lexicographic | PROP1 completion · PROP1 completion, lexicographic | computational complexity: NP-complete -> polynomial time | Helped |
| restrict valuations to lexicographic | MMS completion · MMS completion, lexicographic | computational complexity: NP-hard -> polynomial time | Helped |
| require Pareto optimality in addition to EF1 | EF1 completion with binary additive valuations · EF1+PO completion, binary additive | computational complexity: NP-complete -> NP-complete | No clear effect |
| require Pareto optimality in addition to PROP1 | PROP1 completion · PROP1+PO completion, binary additive | computational complexity: polynomial time -> polynomial time | No clear effect |
| restrict the instance to two agents with identical additive valuations | EF1 completion · EF1 completion, two agents with identical additive valuations | computational complexity: NP-complete -> polynomial time | Helped |
| restrict the instance to two agents with identical additive valuations | PROP1 completion · PROP1 completion, two agents with identical additive valuations | computational complexity: NP-complete -> polynomial time | Helped |
| require the frozen allocation to be EF1 with an acyclic envy graph | EF1 completion with additive valuations · EF1 completion | computational complexity: NP-hard -> polynomial time | Helped |
Surprising findings
- Under lexicographic valuations every allocation satisfies Prop1, yet MMS completion can fail to exist even when the frozen allocation is Pareto optimal.
- Completion is harder than the standard problem: EF1 completion is NP-complete for binary additive valuations, while standard EF1 is polynomial.
Limitations
- Only frozen (pre-assigned) goods are considered; forbidden assignments are left open.
- Several cells remain open, e.g., EF1+PO and MMS+PO under lexicographic valuations, and MMS+PO for general additive valuations.
Experimental setup
Builds on: EF1 round-robin maximin share Equitable Coloring reduction (Hosseini et al.) Rainbow Coloring Pareto optimality
Closest papers by meaning
- The Complexity of Extending Fair Allocations of Indivisible Goods (AAAI 2025 · similarity 0.91)
- Reachability of Fair Allocations via Sequential Exchanges (AAAI 2024 · similarity 0.91)
- The Complexity of Fair Division of Indivisible Items with Externalities (AAAI 2024 · similarity 0.90)
- Constrained Fair and Efficient Allocations (AAAI 2025 · similarity 0.90)
- Repeated Fair Allocation of Indivisible Items (AAAI 2024 · similarity 0.90)
- Towards Optimal Subsidy Bounds for Envy-Freeable Allocations (AAAI 2024 · similarity 0.90)
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.