7 - Sealed-Bid Multi-Object Auctions

Summary

The strategic complexity of bidding in simultaneous auctions such as the SMRA has led to the development of combinatorial auctions. They allow bidders to express superand subadditive valuations, which is not the case in SMRA.We first focus on sealed-bid combinatorial auction designs, before we discuss iterative auctions in the next chapter. There are two important design parameters for sealed-bid combinatorial auctions: the bid language and the payment rule. First, we discuss generic bid languages as they are widely used in the literature and the resulting allocation or winner determination problem. Then we discuss payment rules such as those used in the Vickrey–Clarke– Groves (VCG) mechanism and those used to compute bidder-optimal core payments. The latter were designed to address some of the problems in the VCG mechanism. Finally, we introduce examples of compact bid languages for specific domains. Such bid languages make additional assumptions on the shape of the value or cost functions, but they allow bidders to express their preferences with a low number of parameters, which is typically important for generic bid languages.

Generic Bid Languages

A bid in an auction is an expression of the bidder's willingness to pay particular monetary amounts for various outcomes. Bidders formulate bids according to their private preferences and bidding strategies. A bid language defines the way (the format of the communicated messages and the interpretation rules) in which bidders are allowed to formulate their bids.

In combinatorial auctions every auction outcome corresponds to a particular allocation. From the point of view of a particular bidder, the auction outcome is defined by the set of items allocated to her and the monetary amount she has to pay for it. Therefore, the most direct way of bid formulation is to let each bidder attach a bid price to each possible bundle. This allows a bidder to express any kind of preference, but in the worst case it requires an exponential number (2^m − 1) of bundles to be evaluated and monitored by every bidder and the same amount of messages to be communicated to the auctioneer. Although in many cases not every possible combination of items has a positive value for every bidder, the number of interesting bundles can quickly become overwhelming.