An Efficient and Incentive Compatible Ascending Auction for Multiple Complements1

Abstract: This paper proposes an ascending auction for efficiently allocat-ing multiple complementary indivisible commodities. The seller has a reserve price for every bundle of goods and determines the quantity for sale based upon bidders ’ reported demands. The auctioneer announces a price for every bundle of goods, every bidder subsequently responds with a set of goods de-manded at those prices, and then the auctioneer adjusts prices upwards for those over-demanded bundles and so on. First, we prove that the auction finds an efficient allocation and a market-clearing price for each bundle in finitely many steps, provided that all bidders bid sincerely or quasi-sincerely. Quasi-sincere bidding strategies can tolerate certain inaccurate or dishonest bidding behaviors of bidders. Second, when bidders are not assumed to be price-takers and can exercise their market power strategically, built on the above-mentioned auction we propose an incentive compatible dynamic procedure that always in-duces bidders to bid sincerely and finds an efficient allocation and a generalized Vickrey-Clarke-Groves payment for every bidder