Theory of Computing
-------------------
Title : The Submodular Welfare Problem with Demand Queries
Authors : Uriel Feige and Jan Vondrak
Volume : 6
Number : 11
Pages : 247-290
URL : http://www.theoryofcomputing.org/articles/v006a011
Abstract
--------
We consider the Submodular Welfare Problem where we have
m items and n players with given utility functions
w_i: 2^[m] --> R_+. The utility functions are assumed
to be monotone and submodular. We want to find an allocation
of disjoint sets S_1, S_2, ... , S_n of items maximizing
\sum_i w_i(S_i). A (1-1/e)-approximation for this problem
in the demand oracle model has been given by Dobzinski and
Schapira (2006). We improve this algorithm by presenting a
(1-1/e + \epsilon)-approximation for some small fixed \epsilon > 0.
We also show that the Submodular Welfare Problem is NP-hard
to approximate within a ratio better than some \rho < 1.
Moreover, this holds even when for each player there are only
a constant number of items that have nonzero utility. The
constant size restriction on utility functions makes it easy
for players to efficiently answer any `reasonable' query about
their utility functions. In contrast, for classes of instances
that were used for previous hardness of approximation results,
we present an incentive compatible (in expectation) mechanism
based on `fair division queries' that achieves an optimal
solution.