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.