Nonexistence of Simultaneously EF1 and Pareto Optimal Allocations for Submodular Valuations
2026-07-20 • Computer Science and Game Theory
Computer Science and Game TheoryData Structures and Algorithms
AI summaryⓘ
The authors study how to fairly and efficiently divide items that cannot be split between people who have special types of preferences called monotone submodular valuations. They show with a simple example of two people that it's impossible to make everyone almost envy-free and efficient at the same time. They also prove that figuring out if such an allocation exists is computationally hard. Their example uses a specific kind of valuation called unweighted coverage, expanding known limitations beyond previous cases. They further extend their findings to show similar impossibility results when dividing chores instead of goods.
indivisible goodsenvy-free up to one item (EF1)Pareto optimality (PO)monotone submodular valuationscoverage valuationsadditive valuationsNash Social WelfareNP-hardnessfair divisionchores allocation
Authors
Harish Chandramouleeswaran, Prajakta Nimbhorkar
Abstract
The existence of allocations of indivisible goods that are simultaneously fair (envy-free up to one item (EF1)) and efficient (Pareto optimal (PO)) when agents have monotone submodular valuations has been a longstanding open problem. We settle this question negatively by giving an example with two agents where no allocation is simultaneously EF1 and PO. We also show that determining the existence of such allocations is NP-hard for monotone submodular valuations. Our example uses (unweighted) coverage valuations, which is a strict subclass of monotone submodular valuations. Since EF1+PO allocations are known to always exist for additive valuations via the maximization of Nash Social Welfare (Caragiannis et al. (ACM TEAC 2019)), and for matroid-rank valuations (Benabbou et al. (ACM TEAC 2021)), nonexistence was known only for monotone subadditive valuations (Caragiannis et al. (ACM TEAC 2019)). Our work moves the nonexistence frontier to unweighted coverage valuations. We also show that the example we designed for goods also proves nonexistence of EF1+PO in general, for chores with unweighted coverage costs, by interpreting the valuations as disutilities.