pdf icon
Volume 6 (2010) Article 11 pp. 247-290
The Submodular Welfare Problem with Demand Queries
Received: April 17, 2009
Published: December 9, 2010
Download article from ToC site:
[PDF (393K)]    [PS (1842K)]    [PS.GZ (435K)]
[Source ZIP]
Keywords: auction, combinatorial auction, mechanism design, welfare maximization, submodularity
ACM Classification: F.2.2
AMS Classification: 68W25, 68W20

Abstract: [Plain Text Version]

We consider the Submodular Welfare Problem where we have $m$ items and $n$ players with given utility functions $w_i: 2^{[m]} \rightarrow \mathbb R_+$. The utility functions are assumed to be monotone and submodular. We want to find an allocation of 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 model has been given by Dobzinski and Schapira (2006). We improve this algorithm by presenting a $(1-1/\mathrm 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.