Feige & Grinberg break MMS fairness barrier, achieving >27.5% approximation

A new theoretical result from Weizmann Institute researchers Uriel Feige and Vadim Grinberg pushes past a long-standing barrier in fair division. In their paper "On MMS, APS and XOS," they tackle the problem of allocating indivisible goods among agents with equal entitlements but complex preferences. Specifically, agents have XOS valuations—a broad class of subadditive preferences that model complementarities without superadditivity. The goal is to ensure each agent receives at least a certain fraction (α-approximation) of their maximin share (MMS), the value they could guarantee by partitioning the goods into n bundles and taking the worst one. Previous work had only achieved α = 4/17 (~23.5%), just under 1/4.

Feige and Grinberg first analyze the gap between the anyprice share (APS) and MMS when all agents share identical XOS valuations. They design an algorithm that guarantees each agent at least 11/40 (27.5%) of their APS, which directly implies the same for MMS. Then, they adapt the approach for heterogeneous XOS valuations, proving that for some sufficiently large n₀, an α-approximation to MMS (and APS) exists for all n ≥ n₀. This is the first result to consistently beat the 1/4 ceiling, opening new avenues for practical fair division in multi-agent systems.