Researchers prove EF1 and Pareto optimality incompatible for submodular valuations

A foundational question in algorithmic fair division asks whether fairness and efficiency can coexist when dividing indivisible goods. For additive valuations, a landmark result by Caragiannis et al. showed that envy-freeness up to one good (EF1) and Pareto optimality (PO) are always compatible. But extending this to submodular valuations—which model diminishing returns—remained an open problem for over a decade. Now, Simon Mackenzie and Mashbat Suzuki have settled it in the negative. They construct an instance with just two agents and eight goods, each with submodular valuations, where every EF1 allocation fails even weak Pareto optimality. This shows that the celebrated additive-case compatibility breaks down for submodular valuations already with two agents.

The authors also map the boundaries of this impossibility. On the negative side, the incompatibility extends to weighted matroid rank valuations when paired with fractional Pareto optimality (fPO), ruling out broad classes of welfare-maximization and market-based approaches. On the positive side, they identify a "common-envelope" condition that restores EF1+PO existence for any number of agents, yielding new results for common-weight matroid-rank valuations. Finally, they quantify the efficiency loss forced by insisting on EF1: for submodular valuations, there is a constant α<1 such that no EF1 allocation is α-PO; for the broader class of subadditive valuations, they prove a tight bound: for any ε>0, no EF1 allocation can be (1/√2+ε)-PO. This work lays critical theoretical foundations for fair division in settings with diminishing returns.