PaperlayerView exact revision on arXiv

Source-linked AI summary

Exact Hill Shares Are Simultaneous Guarantees

Bo Li, Hanyu Li, Chenghua Liu

arXiv:2609.35801v1cs.GT

TL;DR

The paper asks whether agents can simultaneously receive their exact Hill shares, a question left open after prior work established a guarantee only for the monotone closure. It proves that such an allocation exists for arbitrary heterogeneous exact maxima and gives a polynomial-time algorithm to find one.

  • Problem

    Prior work left open whether the exact Hill share, which can be smaller than its monotone closure, is simultaneously guaranteed for three or more agents.

    Source: §1 · p. 2

  • Method

    The algorithm combines an ordered moving-knife recursion protected by tail domination with a trimmed subset-sum routine for the two-agent base case.

    Source: §1 · p. 3, §3.2 · p. 4, §6 · p. 11

  • Results

    Every normalized nonnegative additive instance with n ≥2 admits an allocation meeting every agent’s exact Hill share.

    Source: §1 · p. 2, §7 · p. 12

  • Takeaways & Limitations

    Tail domination and one-sided trimming yield a polynomial-time construction without requiring an exact solution to Partition.

    Source: §1 · p. 3, §7 · p. 12

    The recursive invariant applies to active agents on the current suffix, with each target set by the exact q-agent Hill bound.

    Source: §6 · p. 11

Abstract

from arXiv · show

Fair division of indivisible bads seeks allocations that guarantee every agent a bundle whose cost is no larger than a meaningful fairness benchmark. The canonical minimax share has widely been used; unfortunately, it is not a simultaneous guarantee. Hill (Ann. Probab., 1987) initiated a complementary approach in which the share depends only on the number of agents and the largest possible single-item value. Li et al. (ACM Trans. Econ. Comput., 2024) gave the exact Hill formula and proved that its monotone closure is a simultaneous guarantee. The closure treats the largest-item cost only as an upper bound and can be strictly larger than the share conditioned on the \emph{actual} largest item. They asked whether this smaller exact share is itself simultaneously guaranteed for three or more agents. We resolve this open question affirmatively. For any number of agents and arbitrary heterogeneous largest-item costs, there is one allocation that satisfies every agent's exact Hill's share. We further provide a polynomial-time algorithm computes such an allocation. Our algorithm combines an ordered moving knife with a tail-domination invariant, and a one-sided trimmed subset-sum routine for the two-agent endpoint without computing an exact minimax partition.

1 Introduction

The paper resolves whether exact Hill shares can be guaranteed simultaneously, despite the exact share’s nonmonotonicity. It also gives a polynomial-time construction using tail domination and a trimmed subset-sum routine.

1 Introduction

  • The minimax share depends on an agent’s full valuation, is NP-hard to compute exactly, and is not always simultaneously feasible for heterogeneous agents [9].It asks the agent to partition the bads into n bundles and minimize the cost of the most costly bundle.Source: §1 · pp. 1–2
  • The monotone closure of Hill’s share guarantees simultaneous costs, but can exceed the exact share conditioned on each agent’s actual largest-item cost [14].The prior work left open whether those exact shares are simultaneously guaranteed for three or more agents.Source: §1 · p. 2
  • Every normalized nonnegative additive instance with n ≥2 admits one allocation meeting every agent’s exact Hill share.The allocation can be found in O(m3) time.Source: §1 · p. 2
  • Tail domination compensates for changes in the number of agents, remaining total cost, and largest remaining bad when a bundle is removed.This lets the moving-knife recursion continue and an induction prove the exact simultaneous guarantee.Source: §1 · p. 3
  • A trimmed subset-sum routine replaces the exact minimax partition in the two-agent base case, avoiding a computation that can encode Partition.The exact Hill formula leaves enough room to use a sufficiently balanced split.Source: §1 · p. 3

2 Related work

Related work establishes that familiar guarantees for goods do not automatically transfer to bads. The closest prior work gave the exact Hill share and its monotone-closure guarantee, leaving simultaneous exact shares open.

2 Related work

  • Prop1, PropX, EF1, and EFX are verifiable after allocation, whereas guaranteed shares give agents a numerical target they can compute from their own disutility [3].The truncated proportional share is another efficiently verifiable target, but for goods it can be stronger than the maximin share and not always guaranteed.Source: §2 · p. 3
  • Results for goods do not transfer to bads simply by changing signs, and even one-object relaxations behave differently across the two settings.Exact simultaneous feasibility for maximin shares may fail for chores [9].Source: §2 · p. 3
  • The closest prior work derived the exact Hill share for bads and guaranteed its monotone closure, but left simultaneous exact shares open for n ≥3 [14].The present theorem resolves that question using ordered-instance reduction, tail domination, and a polynomial two-agent construction.Source: §2 · p. 3

3 The recursive allocation framework

The framework sorts each agent’s costs into a common ordered-rank instance, then uses a moving-knife recursion with a threshold based on the exact Hill share of the current suffix. Tail domination allows this step to protect the remaining agents as the recursion removes prefixes.

3.1 Ordered instances reduction

  • The ordered-instance reduction sorts each agent’s item costs from largest to smallest and permits converting any rank allocation back without increasing anyone’s cost.Ranks denote each agent’s own ordered costs and need not refer to the same original item across agents.Source: §3.1 · p. 4

3.2 The recursive prefix step

  • For each active agent, the prefix step stops immediately before her first strict crossing of the exact Hill bound for the current suffix.The algorithm selects the agent whose crossing rank is largest, assigns her the preceding prefix, and recurses on the remaining suffix.Source: §3.2 · p. 4
  • Tail domination ensures that after a prefix is removed, every survivor’s exact Hill bound for the residual tail with one fewer agent is no greater than her old limit.This comparison replaces the prior analysis based on the larger monotone share, whose argument does not establish the comparison for the exact share.Source: §3.2 · pp. 4–5

4 Tail domination

Tail domination supplies the comparison needed to continue the moving-knife recursion despite the exact Hill share’s nonmonotonicity in the largest-item parameter. The proof uses an upper-envelope family to establish the comparison for four or more agents and for the transition from three agents to two.

4 Tail domination

  • The recursive step reduces to showing that after a strict crossing, the residual tail’s exact Hill bound with one fewer agent is at most the old bound.Monotonicity cannot establish this because the exact share can move in either direction as the largest-item ratio changes.Source: §4 · p. 5, §4.2 · p. 6

4.1 Exact-formula tools

  • The envelope family dominates the exact share and lets the proof choose an index from the old state to control either a small or large new maximum.Its two branches correspond to large-item costs and residual mass that is difficult to spread evenly.Source: §4.1 · pp. 5–6

4.2 Four or more agents

  • For four or more agents, the proof switches envelope indices at p = d/(k + 2): a larger new maximum is offset by enough mass removed in the prefix.The crossing and ordered costs imply the prefix contains enough items to bound the residual mass.Source: §4.2 · pp. 6–7

4.3 The transition from three agents to two

  • The same tail-domination conclusion holds for three agents, covering the exceptional transition to two-agent shares and yielding the comparison for every q ≥3.For large maxima, the tail can be handled directly by isolating its largest item when necessary and otherwise balancing greedily between two bundles.Source: §4.3 · p. 7

5 Polynomial two-agent terminal routine

The two-agent terminal routine replaces an exact minimax partition with a polynomial-time trimmed subset-sum search. It uses the slack in the exact Hill formula to find a feasible split, then applies divide-and-choose.

5 Polynomial two-agent terminal routine

  • The two-agent existence proof already follows from divide-and-choose, but computing its exact minimax partition can encode Partition.The contribution is to replace that exact computation with a polynomial-time trimmed subset-sum routine.Source: §5 · p. 7

5.1 The feasible interval

  • The exact two-agent formula provides a feasible interval wide enough for polynomial trimming, and its width is an inverse-polynomial fraction of the total cost.The interval width is the source of the polynomial state bound.Source: §5.1 · p. 8
  • When p/T ≥1/3, assigning a maximum item alone and all remaining items to the other bundle makes both bundles feasible.For p/T < 1/3, the routine instead searches for a subset sum in the feasible interval.Source: §5.1 · p. 8, §5.2 · p. 9

5.2 One-sided trimmed subset sum

  • The one-sided trimmed routine runs largest- and smallest-representative tables so a feasible sum is approximated in the needed direction while each retained value remains an exact subset sum.At least one final table contains a stored exact sum in [L, U].Source: §5.2 · pp. 9–10

5.3 Divide-and-choose

  • The two-bin construction uses O(s3) exact rational operations, O(s2) rolling working states, and O(s3) predecessor words.The resulting split lets the chooser take her cheaper bundle while the divider receives a bundle within her bound.Source: §5.2 · p. 10, §5.3 · p. 10

6 Proof of the main theorem

The main proof uses a constructive induction on active agents: it assigns a safe ordered prefix and recurses on the tail. Tail domination protects the survivors’ bounds, while a polynomial two-agent routine supplies the base case.

6 Proof of the main theorem

  • The induction repeatedly assigns a safe prefix and uses tail domination to protect the remaining agents, with the polynomial two-agent routine as its base case.The same induction establishes existence, correctness, and termination.Source: §6 · p. 11
  • At the top call, the invariant gives every agent her exact-maximum Hill bound, and rank lifting returns an original-item allocation without increasing any cost.This proves the allocation claim for the original items.Source: §6 · p. 12
  • The full algorithm runs in O(m3) time, including the two-agent base and identical-order reduction.The two-agent base uses O(m3) operations; sorting and order reduction are also included in the running-time analysis.Source: §6 · p. 12

7 Conclusion

The exact-maximum Hill share is simultaneously guaranteed for any number of agents with heterogeneous exact maxima, resolving an open problem. A constructive induction yields a polynomial-time allocation algorithm.

7 Conclusion

  • The exact-maximum Hill share is simultaneously guaranteed for any number of agents with arbitrary heterogeneous exact maxima, resolving the open problem in [14].The guarantee applies to one allocation satisfying every agent's exact Hill share.Source: §7 · p. 12
  • A constructive induction computes the allocation in polynomial time.It combines an ordered moving knife and tail-domination invariant with one-sided trimming for the two-agent endpoint, avoiding an exact minimax partition.Source: §7 · p. 12
  • The exact-maximum question for goods and Pareto-efficient or incentive-compatible variants for bads remains open.Source: §7 · p. 12

A Proof of Lemma 4.3

The proof bounds the tail quantity by splitting on the size of its largest item and selecting a corresponding branch parameter. Comparing the resulting bounds establishes the needed envelope inequality.

A Proof of Lemma 4.3

  • The two branches meet at α0, and their common value gives a lower bound on their maximum; an algebraic comparison verifies the required inequality.The comparison reduces to (n − 2)k + n − 4 ≥ 0.Source: A Proof of Lemma 4.3 · p. 15
  • The proof splits at p = d/(k + 2), choosing h = k + 1 for the smaller-item case and h = k for the larger-item case.Source: A Proof of Lemma 4.3 · p. 15
  • When p ≤ d/(k + 2), the increasing branch is bounded by d, while the crossing condition constrains the number and total cost of removed items.The proof uses these constraints to control the other branch as well.Source: A Proof of Lemma 4.3 · p. 15
  • When p > d/(k + 2), the proof uses C + p > α + k + 1 and the decreasing branch to bound the tail quantity by d.Source: A Proof of Lemma 4.3 · pp. 15–16

B Proof of Lemma 4.4

The proof handles the two exceptional indices directly with two-bin arguments, then uses an envelope comparison for the remaining indices. Its case split bounds the relevant branches by d.

B Proof of Lemma 4.4

  • For k = 0, the tail admits a two-partition with maximum load at most d, by isolating its largest item when p > d/2 and otherwise greedily balancing.The tail satisfies p ≤ d and T ≤ 1 − α ≤ 3d/2.Source: B Proof of Lemma 4.4 · p. 17
  • For k = 1, C ≥ α + p, and greedy balancing bounds the maximum tail load by T + p.Source: B Proof of Lemma 4.4 · p. 17
  • For k ≥ 2, the proof applies the exact two-agent formula and checks the exceptional ranges before using the envelope comparison.The exceptional ranges are split at x = 1/5 and x = 1/3.Source: B Proof of Lemma 4.4 · p. 17
  • When p ≤ d/(k + 2), the increasing branch is at most d, and the accompanying inequalities control the other branch.Source: B Proof of Lemma 4.4 · p. 17
  • When p > d/(k + 2), the increasing branch is at most d, while C + p > α + k + 1 bounds the decreasing branch by d.Source: B Proof of Lemma 4.4 · p. 18
Loading 2609.35801v1…