New fair-division proof: EFX/MMS flexibility still impossible for submodular items

Researchers Hadi Hosseini, Payas Khurana, Shraddha Pathak, and Rohit Vaish tackle a long-standing question in fair division: if you let every agent choose between two fairness notions—EFX (envy-free up to any item) and MMS (maximin share guarantee)—does a fair allocation always exist? Their new arXiv paper (2608.10397) answers with a surprising no for submodular goods and chores. They construct counterexamples with only three agents and eight submodular goods, and three agents and seven submodular chores, significantly strengthening earlier impossibility results for EFX alone. Even this flexible disjunction fails to guarantee existence in these general settings.

On the positive side, the authors prove that for additive mixed items—where goods and chores can coexist—with at most three valuation types (and one type being a singleton), an EFX∨MMS allocation always exists. Their proof extends beyond additivity for goods and yields approximation schemes for three-agent chores instances. They also uncover a clean separation: for additive chores with two valuation types, EFX and MMS individually fail, yet an EFX∨MMS allocation always exists. Finally, with identical additive valuations, they show the even stronger conjunction EFX∧MMS is achievable for mixed items. Overall, this work maps the frontier of flexible agent-specific fairness certificates, revealing both surprising impossibilities and new existential guarantees.