Research map / Learning theory and algorithms / Submodular and game algorithms
1/2-Approximate MMS Allocation for Separable Piecewise Linear Concave Valuations
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 1/2-MMS (and symmetric 1/2-APS) allocations exist and are computable in polynomial time for separable piecewise-linear concave valuations via an LP relax-and-round, and gives a greedy 1/3-APS algorithm for submodular valuations using concave extensions.
Problem
Approximate fair division of indivisible goods under MMS and APS fairness for valuations beyond additive, specifically SPLC and submodular valuations, where the best known factors were 1/3-MMS for SPLC and 10/27-MMS for submodular.
Approach
Derive new upper bounds on MMS/APS values via market equilibrium (linear extension) and concave extensions of truncated functions; use an LP relaxation whose fractional solution is rounded acyclically so each agent loses at most one good, and a capped greedy algorithm analyzed through concave extension without computing it.
Key results
- Proves a 1/2-MMS allocation exists and can be computed in polynomial time for SPLC valuations, improving the prior 1/3-MMS; also gives symmetric 1/2-APS.
- Shows a greedy algorithm with capped marginals gives a 1/3-APS allocation for submodular valuations, matching the best known factor.
- Shows the MMS value can equal v_i(M) for SPLC/submodular valuations, unlike additive where MMS_i <= v_i(M)/n.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use the LP-based allocation instead of the best-known SPLC guarantee | SPLC fair division · SPLC fair division (symmetric agents) | MMS approximation factor: 1/3 -> 1/2 | Helped |
| use the LP-based allocation to guarantee APS | SPLC fair division · SPLC fair division (symmetric agents) | APS approximation factor: 1/2 | Helped |
| use the greedy algorithm for APS allocation | Submodular fair division · Submodular fair division | APS approximation factor: 1/3 | No clear effect |
| use the greedy-like allocation with a 1/2-MMS stopping threshold (ablation) | SPLC fair division · SPLC fair division (example with 4 agents and 8 goods) | MMS approximation factor: 1/2 | Hurt |
Surprising findings
- A greedy-like approach with a stopping rule at 1/2-MMS fails to give 1/2-MMS for SPLC valuations, showing the LP-based approach is needed.
- Under the multilinear extension with submodular valuations, there are instances where no fractional 1-MMS allocation exists.
Limitations
- Symmetric-agent guarantee for APS only; the 1/2-APS result does not extend to asymmetric entitlements.
- Submodular result is only 1/3-APS, the 1/2-MMS question for submodular valuations remains open.
- Concave extensions are hard to compute, so the submodular analysis bypasses computation rather than giving an efficient evaluation.
Experimental setup
Metrics: approximation factor of MMS approximation factor of APS
Baselines: 1/3-MMS for SPLC 10/27-MMS for submodular 1/3-APS for submodular
Builds on: maximin share any price share competitive equilibrium concave closure
Closest papers by meaning
- When Can the Maximin Share Guarantee Be Guaranteed? (AAAI 2016 · similarity 0.92)
- Approximations for Indivisible Concave Allocations with Applications to Nash Welfare Maximization (AAAI 2023 · similarity 0.92)
- Achieving Maximin Share and EFX/EF1 Guarantees Simultaneously (AAAI 2025 · similarity 0.91)
- Plant-and-Steal: Truthful Fair Allocations via Predictions (NeurIPS 2024 · similarity 0.90)
- Fair Division via the Cake-Cutting Share (AAAI 2025 · similarity 0.89)
- Epistemic Pairwise Maximin Share (NeurIPS 2026 · similarity 0.89)
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.