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       : https://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.