Simultaneous EF1 and approximate MMS allocations for submodular valuations
2026-06-04 • Computer Science and Game Theory
Computer Science and Game Theory
AI summaryⓘ
The authors study how to fairly divide a set of items among people so everyone feels treated well in two different ways: one based on guaranteed minimum shares (like maximin share) and another based on comparison (like envy-freeness). They focus on creating divisions that satisfy both fairness types at the same time. While this was known for simple cases where values add up directly, the authors extend it to more complex situations where values can have diminishing returns (called submodular valuations). Their results show it's possible to achieve both fairness conditions together even in these harder cases.
maximin share (MMS)ρ-MMSenvy-freeness (EF)EF1EFLindivisible items allocationsubmodular valuationsfair divisionadditive valuations
Authors
Uriel Feige, Assaf Fine
Abstract
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.