Compatibility of Fairness and Nash Welfare under Subadditive Valuations

We establish a compatibility between fairness and efficiency, captured via Nash Social Welfare (NSW), under the broad class of subadditive valuations. We prove that, for subadditive valuations, there always exists a partial allocation that is envy-free up to the removal of any good (EFx) and has NSW at least half of the optimal; here, optimality is considered across all allocations, fair or otherwise. We also prove, for subadditive valuations, the universal existence of complete allocations that are envy-free up to one good (EF1) and also achieve a factor 1/2 approximation to the optimal NSW. Our EF1 result resolves an open question posed by Garg, Husic, Li, Végh, and Vondrák (STOC 2023).