arXiv:2610.25320 · v2

MMS Allocation for Chores with Item Disposals

首次提交 2026-10-18 22:57

版本更新 2026-10-26 17:56

雷达观测 2026-10-29 00:36

摘要

Web platforms organize collective work, including content review and community maintenance, that imposes heterogeneous effort costs on participants. Fairly distributing these burdens while leaving as few tasks unassigned as possible is a natural objective for the design of such platforms. We study this through the maximin share (MMS) allocation problem with chore disposals under nonnegative additive costs. Our goal is to minimize the number of unassigned chores while guaranteeing every agent her MMS benchmark from the original instance. We prove that, for every instance with $n \ge 4$ agents, at most $n-3$ chore disposals suffice. We improve the bound of $2m/11+n$ disposals established by Barman et al. (2025), where $m$ is the number of chores, and eliminate the dependence on $m$. For four agents, we obtain a tight bound: one disposal always suffices, whereas known instances admit no complete MMS allocation (Ezra and Garbuz, 2026). We also prove the same result for goods: $n-3$ duplications suffice to ensure MMS.