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 2-value additive valuations. Our goal is to find an allocation with
maximum Nash social welfare, i.e., the geometric mean of the valuations of the
agents. We give a polynomial-time algorithm to find a Nash social welfare
maximizing allocation when the valuation functions are integrally 2-valued,
i.e., each agent has a value either $1$ or $p$ for each good, for some positive
integer $p$. We then extend our algorithm to find a better approximation factor
for general 2-value instances.
