Metraipolis › archive › dc_ebb9752899d7

Exact Hill Shares Are Simultaneous Guarantees — arXiv:2609.35801

Source: arXiv (en)
Original: https://arxiv.org/abs/2609.35801
License (as archived): CC0-1.0
Archived: 2026-10-07T17:25:45.655Z
SHA-256 of the archived text: b5405edd6fb95c3e694c3261cb8afa91ef60d1930ec7744d5934ce7c29ac9df4
Stable URL of this page: https://metraipolis.com/documento/dc_ebb9752899d7

How to cite

Exact Hill Shares Are Simultaneous Guarantees — arXiv:2609.35801 — arXiv (en), https://arxiv.org/abs/2609.35801 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_ebb9752899d7 (Metraipolis archive dc_ebb9752899d7, sha256 b5405edd6fb95c3e694c3261cb8afa91ef60d1930ec7744d5934ce7c29ac9df4)

BibTeX

@misc{dcebb9752899d7,
  title = {Exact Hill Shares Are Simultaneous Guarantees — arXiv:2609.35801},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.35801},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_ebb9752899d7; sha256 b5405edd6fb95c3e694c3261cb8afa91ef60d1930ec7744d5934ce7c29ac9df4},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.35801. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: economia dei servizi IA (retro-catalogo arXiv: annunci del 2026-09-30 in cs.GT).
Categorie arXiv: Computer Science and Game Theory (cs.GT).
Pagina del lavoro: https://arxiv.org/abs/2609.35801 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-07T16:57:11.415Z dalla pagina https://arxiv.org/catchup/cs.GT/2026-09-30?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).