All-but-one MMS Allocation for Chores

摘要

We study the problem of fairly allocating m indivisible chores among n agents with additive cost functions. While the maximin share (MMS) is a prominent fairness criterion in theory, exact MMS allocations do not always exist. This has motivated relaxation that guarantees MMS fairness for only a subset of agents, aiming to maximize the number of satisfied agents. However, for chore allocation, guaranteeing most agents their full MMS is trivial but highly unsatisfactory, e.g., overburdening a single agent, which is undesirable in real-world platforms aiming for user retention and satisfaction. To address this, we propose a stronger and more practical notion called α-approximate all-but-one MMS (α-AMMS), which guarantees that n-1 agents receive their full MMS value, while the remaining agent receives an α-approximation. This model reflects common platform design goals, where satisfying the vast majority of users is critical, and near-fairness for the rest is acceptable. We show that there exist α-AMMS allocations, with α = 9/8 for three agents; α = 4/3 for four agents; and α = (n+1)2/4n for n ≥ 5 agents.