Research map / Learning theory and algorithms / Submodular and game algorithms
Achieving Maximin Share and EFX/EF1 Guarantees Simultaneously
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.
Shows that partial allocations that are 2/3-MMS and EFX, and complete allocations that are 2/3-MMS and EF1, exist for additive valuations, via a modified MMS algorithm combined with envy-based repair.
Problem
Simultaneously achieving share-based (maximin share, MMS) and envy-based (EFX, EF1) fairness guarantees for indivisible goods with additive valuations.
Approach
Modifies the 2/3-MMS algorithm of prior work, which removes agents once they receive bundles, so that already-allocated bundles can be reshaped later (shrinking and reallocating to most envious agents), maintaining EFX while preserving 2/3-MMS; then runs envy-cycle elimination on leftover goods to get EF1.
Key results
- Existence of a partial allocation that is 2/3-MMS and EFX, improving the prior 1/2-MMS and EFX pseudo-polynomial result.
- Existence of a complete allocation that is 2/3-MMS and EF1, improving the prior 4/7-MMS and EF1 result.
- Both results are computable in pseudo-polynomial time for 2/3-epsilon MMS, and polynomial time with (1-delta)-EFX/EF1 relaxation.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Improve the MMS guarantee while retaining EFX for partial allocations | Partial allocation algorithm for additive valuations · Additive valuations (partial allocation) | MMS approximation: 1/2-MMS -> 2/3-MMS | Helped |
| Improve the MMS guarantee while retaining EF1 for complete allocations | Complete allocation algorithm for additive valuations · Additive valuations (complete allocation) | MMS approximation: 4/7-MMS -> 2/3-MMS | Helped |
| Combine the 2/3-MMS partial EFX allocation with envy-cycle elimination | approxMMSandEF1 · Additive valuations (complete allocation) | MMS approximation | Helped |
| Relax exact MMS to (2/3-ε)-MMS | Partial EFX allocation algorithm · Additive valuations (partial allocation) | runtime guarantee | Helped |
| Relax EFX to (1-δ)-EFX in addition to relaxing MMS to (2/3-ε)-MMS | Partial EFX allocation algorithm · Additive valuations (partial allocation) | runtime guarantee | Helped |
| Relax EF1 to (1-δ)-EF1 and MMS to (2/3-ε)-MMS | Complete allocation algorithm · Additive valuations (complete allocation) | runtime guarantee | Helped |
| Apply envy-cycle elimination to the partial EFX allocation and allocate remaining goods | approxMMSandEF1 · Additive valuations (complete allocation) | MMS approximation | No clear effect |
| Use the charity procedure on the partial EFX allocation | EFX allocation with charity · Additive valuations (partial allocation with charity) | MMS approximation | Helped |
Surprising findings
- EFX allocations are not necessarily alpha-MMS for alpha above 0.5914 for large n, so EFX alone gives weak share guarantees.
Limitations
- Exact 2/3-MMS with EFX/EF1 runs only in pseudo-polynomial time; polynomial time requires relaxing to 2/3-epsilon and (1-delta)-EFX/EF1.
- Results are for additive valuations only.
- Partial EFX allocation leaves goods unallocated (charity) in the partial case.
Experimental setup
Metrics: approximation factor for MMS approximation factor for EFX approximation factor for EF1
Baselines: 1/2-MMS and EFX partial allocation (pseudo-polynomial) 0.553-MMS and 0.618-EFX allocation 4/7-MMS and EF1 allocation
Builds on: envy-cycle elimination 2/3-MMS algorithm of Amanatidis et al. EFX with charity algorithm
Closest papers by meaning
- On Optimal Tradeoffs between EFX and Nash Welfare (AAAI 2024 · similarity 0.95)
- Understanding EFX Allocations: Counting and Variants (AAAI 2025 · similarity 0.95)
- Epistemic EFX Allocations Exist for Monotone Valuations (AAAI 2025 · similarity 0.94)
- EF2X Exists for Four Agents (AAAI 2025 · similarity 0.93)
- Epistemic Pairwise Maximin Share (NeurIPS 2026 · similarity 0.93)
- (Almost Full) EFX for Three (and More) Types of Agents (AAAI 2025 · similarity 0.93)
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.