Approximate Envy-Freeness and Pareto Optimality Beyond Additivity

Abstract

We study the compatibility of envy-freeness up to one good (EF1) and Pareto optimality (PO) beyond additive valuations. For two agents with monotone submodular valuations, we prove that a $2/3$-EF1+PO allocation always exists, while for every $\alpha >3/4$, an $\alpha$-EF1+PO allocation may fail to exist even for unweighted coverage valuations. A six-good EF1+PO counterexample resolves the longstanding exact existence question negatively. Exact EF1+PO does exist when one agent has a monotone submodular valuation and the remaining agents have identical additive valuations. For two agents, we also establish tight EF$k$+PO item thresholds of $4k+1$, $2k+1$, and $3k+1$ for two submodular agents, two subadditive agents, and one subadditive and one additive agent, respectively. Finally, deciding whether an EF$k$+PO allocation exists is NP-hard for every fixed integer $k\ge 1$, even for three agents with unweighted coverage valuations, one of whom has an additive valuation.

arXiv comment25 pages, which includes three appendices