A combinatorial auction is a particular mechanism developed by economists for selling a co...

A combinatorial auction is a particular mechanism developed by economists for selling a collection of items to a collection of potential buyers. (The Federal Communications Commission has studied this type of auction for assigning stations on the radio spectrum to broadcasting companies.)

Here s a simple type of combinatorial auction. There are n items forsale, labeled In. Each item is indivisible and can only be sold to one

person. Now, m different people place bids: The ith bid specifies a subset Si of the items, and an offering price Xi that the bidder is willing to pay for the items in the set Si, as a single unit. (We ll represent this bid as the pair (Si, Xi).)

An auctioneer now looks at the set of all m bids; she chooses to accept some of these bids and to reject the others. Each person whose bid i is accepted gets to take all the items in the corresponding set Si. Thus the rule is that no two accepted bids can specify sets that contain a common item, since this would involve giving the same item to two different people.

The auctioneer collects the sum of the offering prices of all accepted bids. (Note that this is a "one-shot" auction; there is no opportunity to place further bids.) The auctioneer s goal is to collect as much money as possible.

Thus, the problem of Winner Determination for Combinatorial Auctions asks: Given items I1,...,In, bids (S1, X1),...,(Sm, Xm), and a bound B, is there a collection of bids that the auctioneer can accept so as to collect an amount of money that is at least B?

Example. Suppose an auctioneer decides to use this method to sell some excess computer equipment. There are four items labeled "PC," "monitor," "printer", and "scanner"; and three people place bids. Define

S1 = {PC, monitor}, S2 = {PC, printer}, S3 = {monitor, printer, scanner}

and

x1 = x2 = x3 = 1.

The bids are (S1, x1), (S2, x2), (S3, x3), and the bound B is equal to 2.

Then the answer to this instance is no: The auctioneer can accept at most one of the bids (since any two bids have a desired item in common), and this results in a total monetary value of only 1. Prove that the problem of Winner Determination in Combinatorial Auctions is NP-complete.