Improved Maximin Share Approximations for Chores by Bin Packing

Jugal Garg, Xin Huang, Erel Segal-HaleviAAAI 2025 · DOI

TL;DR

This paper tackles the challenge of fairly dividing indivisible chores among agents, a problem where perfect fairness (maximin share) is often unattainable. The authors introduce novel approximation algorithms that improve existing bounds for several special cases, including factored and personalized bivalued instances, by cleverly adapting bin-packing techniques.

What Problem Does This Paper Address?

Fairly dividing indivisible tasks (chores) among multiple agents is a fundamental problem with real-world applications. A popular fairness criterion is the "maximin share" (MMS), which aims to give each agent at least the minimum cost they can guarantee for themselves. However, finding an exact MMS allocation is computationally hard and, crucially, guaranteed to exist only for two agents. This has led researchers to focus on approximations. This paper addresses the limitations of existing MMS approximation algorithms by developing new methods that achieve better fairness guarantees for specific types of chore preferences. They tackle three main areas: improving the "1-out-of-d-MMS" approximation, achieving exact MMS for "factored instances," and improving the approximation factor for "personalized bivalued instances."

Methods

The core of this paper's contribution lies in leveraging and extending the Heterogeneous First Fit Decreasing (HFFD) algorithm, originally developed for bin packing. HFFD is a variant of the classic First Fit Decreasing (FFD) algorithm, adapted to handle agents with different cost preferences. The authors' approach involves:

  • Adapting HFFD for Ordinal Approximations: They extend the analysis of HFFD to achieve a better "1-out-of-d-MMS" approximation, improving upon existing bounds.
  • Optimizing for Factored Instances: They demonstrate that HFFD is optimal for "factored instances" (where chore costs have a specific multiplicative relationship), resolving an open question. This involves a reduction lemma and a swapping-based algorithm to transform an FFD output into a desired allocation.
  • Improving Approximations for Personalized Bivalued Instances: For instances where each agent's cost for a chore can only take one of two values (which can differ between agents), they achieve a tighter approximation factor of 15/13, improving the previous best of 13/11. This relies on a detailed case analysis and further adaptation of the HFFD algorithm.

A key technical tool used throughout is the concept of "First Fit Valid" (FFV), which characterizes the output of the HFFD algorithm and is crucial for proving the approximation guarantees. The proofs often involve intricate inductive arguments and a "swapping" mechanism to transform one allocation into another while maintaining desired properties.

Datasets

Not discussed in the paper. The paper focuses on theoretical results and algorithmic design for abstract instances of fair division problems, rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Bin Packing as a Powerful Tool for Fair Division: The paper strongly reinforces the idea that techniques from bin packing (like FFD and its variants) are highly effective for solving complex fair division problems, particularly for indivisible items.
  • HFFD's Versatility: The HFFD algorithm proves to be a surprisingly versatile tool, capable of achieving state-of-the-art results across different types of fairness relaxations (ordinal, multiplicative) and chore preference structures (factored, bivalued).
  • The Power of "First Fit Valid": The FFV property acts as a crucial bridge, connecting the behavior of the HFFD algorithm to the theoretical guarantees of MMS approximations.
  • Factored Instances are "Easy" for HFFD: The finding that HFFD is optimal for factored instances is significant, as it means exact MMS allocations can be found efficiently for this specific class.
  • Tighter Bounds for Bivalued Preferences: The improvement to a 15/13 approximation for personalized bivalued instances is a concrete step forward, narrowing the gap between achievable fairness and the ideal MMS.

Key Results

  • 1-out-of-[n] MMS Allocations: The paper shows the existence of 1-out-of-[n] MMS allocations for all additive instances, improving the current best-known factor.
  • Exact MMS for Factored Instances: They resolve an open question by showing that MMS allocations can be achieved for factored instances. This also leads to polynomial-time algorithms for computing such allocations.
  • 15/13-MMS for Personalized Bivalued Instances: The authors establish a 15/13-MMS approximation for personalized bivalued instances, improving the previous 13/11 factor. This also comes with a polynomial-time algorithm.

Limitations and Future Work

  • Monotonicity of HFFD: A key open question is whether the HFFD (and FFD) algorithm is monotonic in a certain range for general chore costs. The paper demonstrates monotonicity for factored and bivalued instances but not in the general case. This is closely related to finding efficient algorithms for exact MMS approximations.
  • Existence of MMS for Personalized Bivalued Instances: The paper poses the question of whether MMS allocations always exist for personalized bivalued instances. Currently, there are no known counterexamples, suggesting this might be an area for further investigation.
  • Generalizing Bin Packing Connections: The authors express interest in discovering additional connections between bin packing and fair allocation, potentially extending beyond chores to goods, and inspiring new algorithmic solutions.

Summary updated

BibTeX
@inproceedings{garg2025improved,
  author = {Jugal Garg and Xin Huang and Erel Segal-Halevi},
  title = {{Improved Maximin Share Approximations for Chores by Bin Packing}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.1609/aaai.v39i13.33518},
}
Figure