On the Hardness of Welfare Maximization in Combinatorial Auctions with Submodular Valuations

Details On the Hardness of Welfare Maximization in Combinatorial Auctions with Submodular Valuations On the Hardness of Welfare Maximization in Combinatorial Auctions with Submodular Valuations

2012-02-13

arxiv.org/abs/1202.2792v1

Computer Science

Data Structures and Algorithms

Scientific paper

We present a new type of monotone submodular functions: \emph{multi-peak submodular functions}. Roughly speaking, given a family of sets $\cF$, we construct a monotone submodular function $f$ with a high value $f(S)$ for every set $S \in {\cF}$ (a "peak"), and a low value on every set that does not intersect significantly any set in $\cF$. We use this construction to show that a better than $(1-\frac{1}{2e})$-approximation ($\simeq 0.816$) for welfare maximization in combinatorial auctions with submodular valuations is (1) impossible in the communication model, (2) NP-hard in the computational model where valuations are given explicitly. Establishing a constant approximation hardness for this problem in the communication model was a long-standing open question. The valuations we construct for the hardness result in the computational model depend only on a constant number of items, and hence the result holds even if the players can answer arbitrary queries about their valuation, including demand queries. We also study two other related problems that received some attention recently: max-min allocation (for which we also get hardness of $(1-\frac 1 {2e}+\epsilon)$-approximation, in both models), and combinatorial public projects (for which we prove hardness of $(3/4+\epsilon)$-approximation in the communication model, and hardness of $(1 -\frac 1 e+\epsilon)$-approximation in the computational model, using constant size valuations).

Affiliated with

Also associated with

No associations

Rating

On the Hardness of Welfare Maximization in Combinatorial Auctions with Submodular Valuations does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the Hardness of Welfare Maximization in Combinatorial Auctions with Submodular Valuations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Hardness of Welfare Maximization in Combinatorial Auctions with Submodular Valuations will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-684091