Optimal approximation for the submodular welfare problem in the value oracle model

In the Submodular Welfare Problem, m items are to be distributed among n players with utility functions wi: 2m → R+. The utility functions are assumed to be monotone and submodular. Assuming that player i receives a set of items Si, we wish to maximize the total utility ∑i=1n wi (Si). In this paper, we work in the value oracle model where the only access to the utility functions is through a black box returning wi (S) for a given set S. Submodular Welfare is in fact a special case of the more general problem of submodular maximization subject to a matroid constraint: maxf (S): S ∈ I, where f is monotone submodular and I is the collection of independent sets in some matroid.