Published: December 9, 2010

**Keywords:**auction, combinatorial auction, mechanism design, welfare maximization, submodularity

**Categories:**algorithms, combinatorial optimization, submodular function, game theory, algorithmic game theory, ecommerce, electronic commerce, welfare maximization

**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.