Fair Division with Strictly Increasing Valuations: A Tight Threshold for Two-Agent EF1 and PO

This paper identifies the exact two-agent threshold for simultaneously achieving envy-freeness up to one good (EF1) and Pareto optimality (PO) under strictly increasing valuations. With at most seven goods, such an allocation always exists without assuming submodularity. At eight goods, the authors construct a normalized, integer-valued, strictly increasing, submodular instance in which every EF1 allocation is strictly Pareto dominated. The paper also strengthens a three-agent NP-hardness result: deciding whether an EF1-and-PO allocation exists remains NP-hard for normalized integer-valued monotone submodular valuations, even when zero marginals are restricted to eight fixed agent-good pairs involving one agent.