Ordinal Maximin Share Approximation for Chores

We study the problem of fairly allocating a set of 𝑚 indivisible chores (items with non-positive value) to 𝑛 agents. We consider the desirable fairness notion of 1-out-of-𝑑 maximin share (MMS)-the minimum value that an agent can guarantee by partitioning items into 𝑑 bundles and receiving the least valued bundle-and focus on ordinal approximation of MMS that aims at finding the largest 𝑑 ≤ 𝑛 for which 1-out-of-𝑑 MMS allocation exists. Our main contribution is a polynomial-time algorithm for 1-out-of-⌊ 2𝑛 3 ⌋ MMS allocation, and a proof of existence of 1-out-of-⌊ 3𝑛 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.