Ordinal Maximin Share Approximation for Chores

We study the problem of fairly allocating a set of m indivisible chores (items with non-positive value) to n agents. We consider the desirable fairness notion of 1-out-of-d maximin share (MMS)-the minimum value that an agent can guarantee by partitioning items into d bundles and receiving the least valued bundle-and focus on ordinal approximation of MMS that aims at finding the largest d ≤ n for which 1-out-of-d MMS allocation exists. Our main contribution is a polynomial-time algorithm for 1-out-of-⌊2n/3⌋ MMS allocation, and a proof of existence of 1-out-of-⌊3n/4⌋ MMS allocation of chores. Furthermore, we show how to use recently-developed algorithms for bin-packing to approximate the latter bound up to a logarithmic factor in polynomial time.