Research map / Learning theory and algorithms / Submodular and game algorithms
Improved Maximin Share Approximations for Chores by Bin Packing
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 via the HFFD bin-packing algorithm new existence results for chore fair division: 1-out-of-floor(9n/11) MMS for additive costs, exact MMS for factored instances, and 15/13-MMS for personalized bivalued instances, with polynomial-time algorithms for the latter two.
Problem
Fair division of indivisible chores among n agents with additive costs under maximin share (MMS) fairness, where exact MMS allocations may not exist for more than two agents; the paper seeks better multiplicative and ordinal approximations and special cases with exact MMS.
Approach
Analyzes the Heterogeneous First Fit Decreasing (HFFD) bin-packing-style algorithm: reduces HFFD outputs to FFD outputs via First-Fit-Valid tuples and swap-based transformations, yielding improved ordinal bound for general additive instances and exact/tight bounds for factored and personalized bivalued instances.
Key results
- Existence of 1-out-of-floor(9n/11) MMS allocations for additive chore instances, improving the prior 1-out-of-floor(3n/4).
- HFFD with thresholds equal to MMS allocates all chores for factored instances, resolving an open question of Ebadian et al. (2021), i.e., exact MMS for factored instances.
- 15/13-MMS for personalized bivalued instances (tight for HFFD), improving 13/11; polynomial-time computable.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Improve the ordinal guarantee from 1-out-of-$\lfloor \frac{3}{4}n\rfloor$ to 1-out-of-$\lfloor \frac{9}{11}n\rfloor$ | HFFD for general additive chores · General additive chores | 1-out-of-d MMS guarantee: 1-out-of-$\lfloor \frac{3}{4}n\rfloor$ -> 1-out-of-$\lfloor \frac{9}{11}n\rfloor$ | Helped |
| Apply HFFD to factored instances | HFFD · Factored instances | MMS approximation factor: MMS allocations | Helped |
| Use the $15/13$ guarantee for personalized bivalued instances instead of the general-instance $13/11$ factor | HFFD · Personalized bivalued instances | MMS approximation factor: $13/11$ -> $15/13$ | Helped |
Limitations
- Monotonicity of FFD/HFFD for general instances remains open, so the binary-search approach does not extend to general additive instances.
- Existence of exact MMS for general personalized bivalued instances is unresolved.
- Ordinal bound 9/11 is still not the bin packing bound for general instances.
Experimental setup
Metrics: 1-out-of-d MMS approximation factor multiplicative MMS approximation factor
Baselines: 1-out-of-floor(3n/4) MMS 13/11-MMS MultiFit
Builds on: HFFD algorithm (Huang and Lu 2021) First Fit Decreasing bin packing MultiFit Ebadian et al. 2021 factored instances
Closest papers by meaning
- Almost Envy-Free Allocations of Indivisible Goods or Chores with Entitlements (AAAI 2024 · similarity 0.89)
- Achieving Maximin Share and EFX/EF1 Guarantees Simultaneously (AAAI 2025 · similarity 0.89)
- 1/2-Approximate MMS Allocation for Separable Piecewise Linear Concave Valuations (AAAI 2024 · similarity 0.88)
- Settling the Maximin Share Fairness for Scheduling among Groups of Machines (ICML 2025 · similarity 0.88)
- Fair Division via the Cake-Cutting Share (AAAI 2025 · similarity 0.88)
- Repeated Fair Allocation of Indivisible Items (AAAI 2024 · similarity 0.87)
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.