[Solved]: Auction where each bidder bids on a bundle of items

Problem Detail: 

Is there some optimal solution in an auction where each bidder bids on a bundle of items?

Asked By : Mike

Answered By : D.W.

This problem is NP-hard, by reduction from 3-dimensional matching.

An instance of 3-dimensional matching involves three disjoint vertex sets $X,Y,Z$ and a set $T \subseteq X \times Y \times Z$ of triples of the form $(x_i,y_j,z_k)$. The goal is to find a subset $T_0 \subseteq T$ such that each vertex of $X \cup Y \cup Z$ appears in at most one triple of $T_0$, and the cardinality of $T_0$ is maximized.

Given an instance of 3-dimensional matching, we can construct an auction with bidders $X$ and items $Y \cup Z$. For each $(x,y,z) \in T$, we'll have $x$ bid \$1 on the pair of items $y,z$. Now the optimal set of accepted bids for the auction is exactly the maximum 3-dimensional matching, so any algorithm to solve your problem would also solve 3-dimensional matching.

Since 3-dimensional matching is known to be NP-hard, it follows that your problem is also NP-hard, and in particular, there isn't likely to be any efficient algorithm for your problem.

The same reduction also shows that your problem is APX-hard, i.e., there is some $c>1$ such that there does not exist any $c$-approximation algorithm for your problem (unless P=NP).

I don't know whether there might be an approximation algorithm for some constant approximation factor. It's known that 3-dimensional matching can be approximated in polynomial time with a $3/2 + \varepsilon$ approximation factor; you might check whether any of those algorithms can be adapted to provide suitable solutions for your problem. For instance, one very simple approach might be to find a maximal matching of the associated hypergraph; this will give a $1+k$ approximation, if every bid mentions at most $k$ items. I don't know if you can find maximal matchings in hypergraphs in polynomial time, like you can in ordinary graphs.

---

Practical algorithms

If you have to deal with this problem in practice, I suggest formulating it as an integer linear programming (ILP) problem and then applying an off-the-shelf ILP solver.

Introduce zero-or-one variables $x_i$, with the intended meaning that $x_i=1$ means that the $i$th bid is accepted. Each constraint "at most one bid is accepted from each person" turns into a inequality of the form $\sum_{i \in S} x_i \le 1$. Each constraint "each item appears in at most one accepted bid" turns into another inequality of the same form. The objective function is a linear function of the $x_i$'s. Now apply an off-the-shelf ILP solver, like CPLEX.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/62814

3.2K people like this

 Download Related Notes/Documents