hide
Free keywords:
Computer Science, Computer Science and Game Theory, cs.GT,
Abstract:
We study the problem of allocating a set of indivisible goods among agents
with subadditive valuations in a fair and efficient manner. Envy-Freeness up to
any good (EFX) is the most compelling notion of fairness in the context of
indivisible goods. Although the existence of EFX is not known beyond the simple
case of two agents with subadditive valuations, some good approximations of EFX
are known to exist, namely $\tfrac{1}{2}$-EFX allocation and EFX allocations
with bounded charity.
Nash welfare (the geometric mean of agents' valuations) is one of the most
commonly used measures of efficiency. In case of additive valuations, an
allocation that maximizes Nash welfare also satisfies fairness properties like
Envy-Free up to one good (EF1). Although there is substantial work on
approximating Nash welfare when agents have additive valuations, very little is
known when agents have subadditive valuations. In this paper, we design a
polynomial-time algorithm that outputs an allocation that satisfies either of
the two approximations of EFX as well as achieves an $\mathcal{O}(n)$
approximation to the Nash welfare. Our result also improves the current
best-known approximation of $\mathcal{O}(n \log n)$ and $\mathcal{O}(m)$ to
Nash welfare when agents have submodular and subadditive valuations,
respectively.
Furthermore, our technique also gives an $\mathcal{O}(n)$ approximation to a
family of welfare measures, $p$-mean of valuations for $p\in (-\infty, 1]$,
thereby also matching asymptotically the current best known approximation ratio
for special cases like $p =-\infty$ while also retaining the fairness
properties.
