@online{Chaudhury_arXiv2005.06511,
TITLE = {Fair and Efficient Allocations under Subadditive Valuations},
AUTHOR = {Ray Chaudhury, Bhaskar and Garg, Jugal and Mehta, Ruta},
LANGUAGE = {eng},
URL = {https://arxiv.org/abs/2005.06511},
EPRINT = {2005.06511},
EPRINTTYPE = {arXiv},
YEAR = {2020},
ABSTRACT = {We study the problem of allocating a set of indivisible goods among agents<br>with subadditive valuations in a fair and efficient manner. Envy-Freeness up to<br>any good (EFX) is the most compelling notion of fairness in the context of<br>indivisible goods. Although the existence of EFX is not known beyond the simple<br>case of two agents with subadditive valuations, some good approximations of EFX<br>are known to exist, namely $\tfrac{1}{2}$-EFX allocation and EFX allocations<br>with bounded charity.<br> Nash welfare (the geometric mean of agents' valuations) is one of the most<br>commonly used measures of efficiency. In case of additive valuations, an<br>allocation that maximizes Nash welfare also satisfies fairness properties like<br>Envy-Free up to one good (EF1). Although there is substantial work on<br>approximating Nash welfare when agents have additive valuations, very little is<br>known when agents have subadditive valuations. In this paper, we design a<br>polynomial-time algorithm that outputs an allocation that satisfies either of<br>the two approximations of EFX as well as achieves an $\mathcal{O}(n)$<br>approximation to the Nash welfare. Our result also improves the current<br>best-known approximation of $\mathcal{O}(n \log n)$ and $\mathcal{O}(m)$ to<br>Nash welfare when agents have submodular and subadditive valuations,<br>respectively.<br> Furthermore, our technique also gives an $\mathcal{O}(n)$ approximation to a<br>family of welfare measures, $p$-mean of valuations for $p\in (-\infty, 1]$,<br>thereby also matching asymptotically the current best known approximation ratio<br>for special cases like $p =-\infty$ while also retaining the fairness<br>properties.<br>},
}