Compatibility of Fairness and Nash Welfare under Subadditive Valuations
<|reference_start|>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 et al. (STOC 2023).   In addition, we develop a polynomial-time algorithm which, given an arbitrary allocation \~A as input, returns an EF1 allocation with NSW at least $1/3$ times that of \~A. Therefore, our results imply that the EF1 criterion can be attained simultaneously with a constant-factor approximation to optimal NSW in polynomial time (with demand queries), for subadditive valuations. The previously best-known approximation factor for optimal NSW, under EF1 and among $n$ agents, was $O(n)$ - we improve this bound to $O(1)$.   It is known that EF1 and exact Pareto efficiency (PO) are incompatible with subadditive valuations. Complementary to this negative result, the current work shows that we regain compatibility by just considering a factor $1/2$ approximation: EF1 can be achieved in conjunction with $\frac{1}{2}$-PO under subadditive valuations. As such, our results serve as a general tool that can be used as a black box to convert any efficient outcome into a fair one, with only a marginal decrease in efficiency.<|reference_end|>
@article{barman2024compatibility,
    title={Compatibility of Fairness and Nash Welfare under Subadditive Valuations},
    author={Siddharth Barman and Mashbat Suzuki},
    journal={arXiv preprint arXiv:2407.12461},
    year={2024},
    archivePrefix={arXiv},
    eprint={2407.12461},
    primaryClass={cs.GT}
}