Guaranteeing MMS for All but One Agent When Allocating Indivisible Chores

Abstract

We study the problem of allocating $m$ indivisible chores to $n$ agents with additive cost functions under the fairness notion of maximin share (MMS). In this work, we propose a notion called $\hat{I}\pm$-approximate all-but-one maximin share ($\hat{I}\pm$-AMMS) which is a stronger version of $\hat{I}\pm$-approximate MMS. An allocation is called $\hat{I}\pm$-AMMS if $n-1$ agents are guaranteed their MMS values and the remaining agent is guaranteed $\hat{I}\pm$-approximation of her MMS value. We show that there exist $\hat{I}\pm$-AMMS allocations, with $\hat{I}\pm =9/8$ for three agents; $\hat{I}\pm =4/3$ for four agents; and $\hat{I}\pm =(n+1{)}^2/4n$ for $n\ge 5$ agents.

18 pages, 7 figures