摘要：We consider the Submodular Welfare Problem wherewe have $m$ items and $n$ players with given utility functions$w_i: 2^{[m]} \rightarrow \mathbb R_+$. The utility functions are assumedto be monotone and submodular. We want to find an allocationof disjoint sets $S_1, S_2, \ldots, S_n$ of items maximizing $\sum_i w_i(S_i)$.A $(1-1/\mathrm e )$-approximation for this problem in the demand oracle modelhas been given by Dobzinski and Schapira (2006).We improve this algorithm by presenting a $(1-1/\mathrm e + \epsilon)$-approximationfor 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 playerthere are only a constant number of items that have nonzeroutility. The constant size restriction on utility functions makesit easy for players to efficiently answer any “reasonable” query about their utility functions. In contrast, for classes ofinstances that were used for previous hardness of approximationresults, we present an incentive compatible (in expectation)mechanism based on fair division queries that achievesan optimal solution.
