Simultaneous EF1 and approximate MMS allocations for submodular valuations
It provides the first simultaneous EF1 and approximate MMS guarantees for submodular valuations, addressing a key open problem in fair division.
The paper designs allocations that simultaneously satisfy EF1 and constant-factor MMS guarantees for submodular valuations, extending prior results from additive to submodular valuations.
There are two common classes of fairness notions that are considered when allocating $m$ indivisible items to $n$ agents of equal entitlements. One is that of share-based fairness notions, with the maximin share (MMS) and its relaxations to $ρ$-MMS being prominent representatives of this class. The other is that of comparison-based fairness notions, with envy-freeness (EF) and its relaxations such as EF1 being prominent representatives of this class. In general, no class offers good guarantees for the other class. In this work, we design allocations that simultaneously satisfy notions from both classes, and specifically, are $ρ$-MMS for constant $ρ$ and EF1 (in fact, also EFL). Such results were previously known when agents have additive valuations, and we prove such results for the more general class of submodular valuations.