On Optimal Tradeoffs between EFX and Nash Welfare

A major problem in fair division is how to allocate a set of indivisible resources among agents fairly and efficiently. We give optimal tradeoffs between fairness and efficiency, with respect to well-studied measures of fairness and efficiency -- envy freeness up to any item (EFX) for fairness, and Nash welfare for efficiency. Our results improve upon the current state of the art, for both additive and subadditive valuations. For additive valuations, we show the existence of allocations that are simultaneously $\alpha$-EFX and guarantee a $\frac{1}{\alpha+1}$-fraction of the maximum Nash welfare, for any $\alpha\in[0,1]$. For $\alpha\in[0,\varphi-1 \approx 0.618]$ these are complete allocations (all items are assigned), whereas for larger $\alpha$ these are partial allocations (some items may be unassigned). We partially extend this to subadditive valuations where we show the existence of complete allocations that give $\alpha$-EFX and a $\frac{1}{\alpha+1}$-fraction of the maximum Nash welfare (as above), for any $\alpha\in[0,1/2]$. We also give impossibility results that show that our tradeoffs are tight, even with respect to partial allocations.