On Hill's Worst-Case Guarantee for Indivisible Bads

Bo Li, Hervé Moulin, Ankang Sun, Yu Zhou

Introduction

Fair division research traditionally focuses on the allocation of "goods"—items with positive utility like land or jewelry. However, many practical scenarios involve the division of "bads," such as chores, liabilities, or costs. A standard benchmark for fairness in these contexts is the MaxMinShare (MMS): the utility an agent expects if they partition items into $n$ bundles but are the last to choose.

Despite its popularity, MMS suffers from two critical drawbacks: finding the MMS value is an NP-hard computational problem, and in certain edge cases, it is mathematically impossible to guarantee every participant their MMS. This paper addresses these issues by extending Hill’s 1987 "worst-case share" framework to the domain of indivisible bads, providing a guarantee that is both computationally simple and universally achievable.

The Hill’s Share Framework

Hill’s approach defines a share based on only two parameters: the number of agents $n$ and the disutility of the agent's single most "hated" item, denoted as $\alpha$. By focusing on the worst item, the framework captures the "Chore from Hell" effect, where one extremely undesirable task dominates the entire division process.

Characterizing the Guarantee

The researchers derived a tight closed-form function, $\Delta_n^\oplus(\alpha)$, representing the worst-case MinMaxShare for $n$ agents. A surprising discovery in this characterization is the non-monotonicity of the function. Counter-intuitively, there are specific ranges where increasing the disutility of the worst item actually makes it easier to find a balanced partition, resulting in a "jagged" mathematical curve.

The worst-case MinMaxShare function for n=2 and n=3, illustrating the non-monotonic, 'jagged' nature of the guarantee as a function of alpha.

To ensure a robust and fair threshold, the authors defined a "monotonic cover" $V_n(\alpha)$. This serves as a bona fide guarantee: a value that every agent can be certain to achieve regardless of the preferences of others.

Algorithmic Feasibility

One of the primary advantages of Hill’s share over MMS is its feasibility. The authors prove that the guarantee $V_n(\alpha)$ can always be satisfied for all participants. They demonstrate this using an adapted version of the Dubins-Spanier moving-knife algorithm for indivisible items. Unlike the NP-hard search for MMS, this algorithm operates in polynomial time, making it a practical tool for real-world applications where transparency and speed are essential.

Empirical Performance and Key Results

The theoretical findings were validated using both synthetic data and real-world disutility functions from the Spliddit platform (comprising over 8,000 instances). The results highlight the effectiveness of Hill's share as a design constraint:

  • Proximity to MMS: In real-world data, Hill’s share is remarkably close to the ideal MMS. Over 65% of instances showed Hill's share within a 1.1x factor of the MMS value.
  • Superiority to Approximations: For most values of $\alpha$, Hill’s share provides a tighter (lower) disutility guarantee than the best-known general approximations of MMS, such as the $4/3$ or $11/9$ factors commonly cited in literature.
Comparison of Hill's share ratios across different numbers of agents (n=2, 10, 100) against standard MMS approximation benchmarks.

Conclusion and Future Work

This research provides the first tight characterization of Hill’s share for bads, offering a computationally efficient and mathematically guaranteed alternative to MMS. While the current work focuses on the existence of fair allocations, future research will look toward designing "truthful" mechanisms that incentivize agents to report their true disutilities. Additionally, the paper notes that while the problem for "bads" is now well-characterized, the tight characterization for the original "goods" problem for $n \ge 3$ remains an intriguing open question.

Summary updated

BibTeX
@article{li2024hill,
  author = {Bo Li and Hervé Moulin and Ankang Sun and Yu Zhou},
  title = {{On Hill's Worst-Case Guarantee for Indivisible Bads}},
  journal = {ACM Trans. Economics and Comput.},
  year = {2024},
  doi = {10.1145/3703845},
}
Figure