View article

In fair division of indivisible goods, ℓ-out-of-d maximin share (MMS) is the value that an agent can guarantee by partitioning the goods into d bundles and choosing the ℓ least preferred bundles. Most existing works aim to guarantee to all agents a constant fraction of their 1-out-of-n MMS. But this guarantee is sensitive to small perturbation in agents' cardinal valuations. We consider a more robust approximation notion, which depends only on the agents' ordinal rankings of bundles. We prove the existence of ℓ-out-of-⌊(ℓ+ 1/2) n⌋ MMS allocations of goods for any integer ℓ≥ 1, and present a polynomial-time algorithm that finds a 1-out-of-⌈ 3n/2⌉ MMS allocation when ℓ= 1. We further develop an algorithm that provides a weaker ordinal approximation to MMS for any ℓ> 1.