hide
Free keywords:
Computer Science, Data Structures and Algorithms, cs.DS,Computer Science, Computer Science and Game Theory, cs.GT
Abstract:
We present the first constant-factor approximation algorithm for maximizing
the Nash social welfare when allocating indivisible items to agents with
budget-additive valuation functions. Budget-additive valuations represent an
important class of submodular functions. They have attracted a lot of research
interest in recent years due to many interesting applications. For every
$\varepsilon > 0$, our algorithm obtains a $(2.404 +
\varepsilon)$-approximation in time polynomial in the input size and
$1/\varepsilon$.
Our algorithm relies on rounding an approximate equilibrium in a linear
Fisher market where sellers have earning limits (upper bounds on the amount of
money they want to earn) and buyers have utility limits (upper bounds on the
amount of utility they want to achieve). In contrast to markets with either
earning or utility limits, these markets have not been studied before. They
turn out to have fundamentally different properties.
Although the existence of equilibria is not guaranteed, we show that the
market instances arising from the Nash social welfare problem always have an
equilibrium. Further, we show that the set of equilibria is not convex,
answering a question of [Cole et al, EC 2017]. We design an FPTAS to compute an
approximate equilibrium, a result that may be of independent interest.
