Question

Combinatorial Auctions (K&T Ch8.Ex13). 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.) Heres a simple type of combinatorial auction. There are n items for sale, labeled I,..., 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 S of the items, and an offering price z, that the bidder is willing to pay for the items in the set S, as a single unit. (Well represent this bid as the pair (Si,ri).) 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 auctioneers goal is to collect as much money as possible. Thus, the problem of Winner Determination for Combinatorial Auctions asks: Given items I,.., In, bids S1,Srm), 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? ework 6 Prove that the problem of Winner Determination for Combinatorial Auctions is NP-complete. 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 s, = [PC, monitor], S2-1PC, printer], S3-kronitor, printer, scanner] and The bids are (Si, ?1), (S2,#2), (S3,23), 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.

Answer 1

Answer Proof This given problem is NP-complete. The reason is that for the set of bidders, it is possible to check in polynomial time that no two bidders bought the bid on the same item and also verify that the value of the bids is <= B Now the problem can be reduced from INDEPENDENT SET problem. Given a Graph “G', and a value "t", represent bidder as the node in “G', and represent item for each edge in “G". Each bidder “u" places a bid on item "e, so that "e is happening to "u" in Graph "G". Now set the value for each bid to "1. At last, we ask over whether the auctioneer can agree to a set of bids that gives total B- t This becomes true if and only if G has an INDEPENDENT SET of size t". If there exist a set of agreeing bids that has the total value "t then the matching set of nodes satisfy the property that no two bidder are happening to the same edge. In opposition, if there exists an INDEPENDENT SET of size “t", then the bidders has the characteristic that the bids are disjoint and total value is t" Therefore, Winner Determination problem in Combinatorial Auctions is NP- complete