On Hill's Worst-Case Guarantee for Indivisible Bads

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

TL;DR

This paper extends Hill’s "worst-case share" framework from the fair division of goods to the division of "bads" (chores or costs). The authors provide a tight mathematical characterization of a guarantee that is computationally simple and—unlike the popular MaxMinShare—is actually proven to be achievable for all participants in polynomial time.

What Problem Does This Paper Address?

Fair division usually focuses on "goods" (like jewelry or land), but many real-world problems involve "bads" (like chores, liabilities, or toxic waste). A common benchmark for fairness is the MaxMinShare (MMS): the utility an agent would get if they partitioned the items into $n$ bundles but were the last to choose.

However, MMS has two major flaws:

  1. Computational Complexity: Finding the MMS value is an NP-hard problem.
  2. Feasibility: In rare cases, it is mathematically impossible to give everyone their MMS.

The authors look to a 1987 approach by Hill, which defines a share based only on an agent's total disutility and the disutility of their worst single item ($\alpha$). This paper seeks to determine the exact "Hill's share" for bads and prove that it can always be guaranteed to every agent.

Methods

The researchers use a mix of combinatorial optimization and social choice theory:

  • Mathematical Characterization: They derive the tight closed-form function $\Delta_n^\oplus(\alpha; m)$, which represents the worst-case MinMaxShare for $n$ agents sharing $m$ bads, where the most "hated" item has a disutility of $\alpha$.
  • Monotonic Cover: Because the raw Hill's share isn't always monotonic (counter-intuitively, sometimes having a slightly worse "worst item" makes it easier to partition the rest), they define a "monotonic cover" $V_n(\alpha)$ to serve as a robust guarantee.
  • Moving-Knife Algorithm: To prove the guarantee is feasible, they adapt the classic "Dubins-Spanier moving-knife" algorithm for indivisible items. This algorithm ensures that each agent receives a bundle with a disutility no higher than the calculated guarantee in polynomial time.

Datasets

The authors evaluated their theoretical findings using two primary sources:

  1. Synthetic Data: 100 randomly generated instances for various combinations of agents ($n$) and items ($m$).
  2. Real-World Data (Spliddit): They extracted 10,000 disutility functions from the Spliddit platform, a well-known fair division site. This dataset included 8,409 real-world instances involving over 22,000 agents and 42,000 objects.

Key Insights and Ideas

  • The "Chore from Hell" Effect: Just as one "diamond" can ruin the fair division of goods (the "diamond effect"), one extremely bad chore can dominate the division of bads. Hill’s share captures this by making the guarantee a function of that worst item.
  • Non-Monotonicity: Surprisingly, the worst-case MinMaxShare is not always monotonic in $\alpha$. There are specific ranges where increasing the disutility of the worst bad actually makes it easier to find a balanced partition, leading to a "jagged" function.
  • Efficiency vs. Fairness: While Hill's share is more "conservative" (pessimistic) than MMS, the authors argue it is "effective." It provides a transparent, hard design constraint that participants can understand and verify immediately without solving NP-hard problems.

Key Results

  • Tight Bounds: The paper provides the first tight characterization of Hill’s share for bads for any number of agents and items.
  • Proven Guarantee: They prove that the monotonic cover $V_n(\alpha)$ is a "bona fide guarantee"—it is always possible to find an allocation where everyone's cost is below this threshold.
  • Empirical Performance: In real-world Spliddit 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 Existing Approximations: For most values of $\alpha$, Hill’s share provides a better (lower) disutility guarantee than the best-known general approximations of MMS (like the $4/3$ or $11/9$ factors).

Limitations and Future Work

  • Truthfulness: The paper focuses on the existence of fair allocations but does not address incentives. A major future direction is designing "truthful" mechanisms where agents are incentivized to report their true disutilities.
  • Domain Tightness: While the guarantee is tight for the domain of all additive disutilities, the authors note it remains an open question whether it is tight for more restricted sub-domains.
  • The "Goods" Mirror: Interestingly, the tight characterization of Hill’s share for the original "goods" problem (for $n \ge 3$) actually remains an open problem, which this paper highlights as a point of comparison.

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