New EPMMS fairness notion guarantees 80% optimal allocations for indivisible goods
A 4/5-EPMMS allocation always exists and is efficiently computable for additive valuations...
Researchers Michal Feldman, Amos Fiat, Yael Nissan, and Tomasz Ponitka introduced a new fairness notion called Epistemic Pairwise Maximin Share (EPMMS) in a paper published on arXiv (2606.18921). This concept relaxes the strong Pairwise Maximin Share (PMMS) criterion by taking an epistemic perspective—each agent considers what might be true under incomplete information. While PMMS is stronger than the widely studied Envy-Freeness up to any item (EFX), progress on EFX via epistemic relaxations motivated this work.
Key results show that for additive valuations, a 4/5-EPMMS allocation (each agent gets at least 80% of their PMMS) always exists and can be computed efficiently. For the special case of bivalued valuations, the researchers achieved full EPMMS allocations, and even strengthened it to Epistemic Groupwise Maximin Share (EGMMS). Critically, EPMMS allocations exist in settings where MMS allocations may not exist—specifically with three additive agents or two types of additive agents. This represents significant progress in fair division theory, potentially influencing resource allocation algorithms for cloud computing, data markets, and multi-agent AI systems.
- 4/5-EPMMS allocations exist for additive valuations and can be computed in polynomial time
- Full EPMMS allocations exist for bivalued valuations, also efficiently computable
- EPMMS guarantees hold in scenarios (3 additive agents, 2 types of additive agents) where MMS allocations are impossible
Why It Matters
Provides a practical fairness guarantee (80%) for complex resource allocation problems where perfect fairness is impossible.