In class we have gone over four main types of auctions: ascending bid, descending bid, first priced sealed bid and second price sealed bid. So far our discussions have focused on independent private values for individual items, but what if there are multiple items and bidders have different valuations depending on what combination of items they receive? Combinatorial auctions allow bidders have valuations for bundles of items.

As an example, let’s say you are bidding on 20 plots of land. You require eight plots of land (a 2 by 4 rectangle) adjacent to a road for a house you want to build. Your valuation for this combination is the highest. If you only win four plots of land that are adjacent to each other you can’t have that big back yard you wanted (a medium valuation). If you win eight plots of land scattered across the area, your plans will not work at all (the lowest valuation). Because there is a high risk of getting scattered land, you may not bid at all. If the seller realizes there is a high demand for adjacent plots, the seller could package plots of land together. Bidders, such as your self, would feel more confident in placing bids because you are guaranteed adjacent plots. Now the set of items up for auction decreases while your valuation for each combination of plots remains the same. You are guaranteed useful land if you win a bid on an area that meets your requirements.

Holland and O’ Sullivan’s paper Super Solutions for Combinatorial Auctions deals with finding items the seller can package together to maximize revenue. The paper focuses on sets of solutions that are within a certain percentage of the optimum revenue called super solutions. These super solutions can partially account for the unreliability of bidders (e.g. withdrawing or disqualifying bids) by providing a set of solutions instead of only one. Because combinatorial auctions allow the bidder to express complex relationships between bids for different items, it is important to have sets of solutions in the same sense bidders have sets of valuations.

This paper offers a broader introduction to combinatorial auctions.