In class we used a preferred-seller graph to model an ascending bid auction of multiple items, where the number of items and bidders is the same. Later, we adapted it for the auctioning of one item by adding “fake” items for which each bidder’s valuation is zero. However, not all types of auctions are easy to model, in particular combinatorial auctions, which is discussed in Noussair’s
Innovations in the Design of Bundled-Item Auctions.

Computational complexity is one of the obstacles to modeling combinatorial auctions. Consider the magnitude of the search space an algorithm would have to plow through to compute the prices standing bids if each bidder had 2ⁿ-1 bids for n items. In fact, the linear programming problem is usually nondeterministic polynomial complete (NP-complete). Banks and Porter’s Adaptive User Selective Mechanism (AUSM) solves this problem by accepting bids for package, P containing item i only if it’s higher than the sum of the standing bids for any packages, S that contain i. The example Noussair gives involves a scenario where the standing bids for items A and B is $500 and for items C and D is $700. If a bidder wanted items B ad C, he would have to bid $1201.

Efficiency and the revenue generated are often used to measure the performance of an auction. Efficiency is achieved when there is a matching where valuations are maximized. One of the faults of AUSM is that it might not be efficient. The example Noussair provides involves a situation where bidder i’s valuation of item A is $1,000 while bidder j’s valuation of item B is $800, but bidder k’s valuation for both A and B is $1,200 and $0 separately. Suppose bidder k’s bid is $1,001 then there is nothing i and j can bid to win the items (because it’s beyond their valuation for the item), unless they decide to work together to overbid k. However, bidder k can still find another bidder to outbid bidders i and j. This story illustrates the threshold problem.

A combinatorial clock auction fixes the threshold problem by having the seller raise prices of the items until one bidder remains (much like the way our auction algorithm we saw in class runs). Each round the bidders decide whether or not they want to buy the items and packages at the current price, but if they want a subset of the package the bidder must be willing to pay for the whole package. Afterwards if there are unclaimed packages and a program is run that searches for a configuration that maximizes the sum of the bids. This type of auction solves the cognitive complexity of combinatorial auctions that Noussair noted in the article. Each bidder doesn’t have to think about all the possible bids for all the items he wants, he just has to accept or reject the current price. Since the “clock” sets the prices, this type of auction also limits colluding among bidders.

For more an introduction to combinatorial auctions read dakru’s post.