Simplified Bidding and Solution Mechanisms for VCG Combinatorial Auctions

Abstract

Combinatorial auctions are very useful in theory, but their applicability in practice has been limited by the need for bidders to bid on an exponential number of bundles and for the auctioneer to solve an exponentially large winner-determination problem. We present a new auction mechanism to eliminate these challenges for a broad class of VCG combinatorial auctions. This mechanism, which yields equivalent results to a fully-enumerated combinatorial auction, eliminates the need for the bidder to explicitly compute and communicate bids on each bundle by exploiting the fact that true-cost bidding is a dominant strategy for these auctions. It also eliminates the need for the auctioneer to solve an exponentially large combinatorial optimization problem to select the optimal bids. Instead, the bidders' true-cost types are explicitly incorporated within a mathematical program that is used to solve the winner- and payment- determination problems. A detailed example based on truckload procurement auctions is provided and several other applicable classes of problems are discussed as well.