Compact Bidding Formats for Combinatorial Auctions

Research by Robert Day, S. Raghavan

New research at the Smith School is making important theoretical contributions in the area of auction research which are currently being used in development efforts to improve auction technology in the telecommunications and transportation industries. Raghu Raghavan, associate professor of decision and information technology, and former Smith PhD student Robert Day, now an assistant professor of operations and information management at the University of Connecticut, have developed innovative strategies for dealing with two key problems with the design of combinatorial auctions: preference elicitation and pricing.

Combinatorial auctions differ from traditional auctions, where a single good is auctioned off to the highest bidder. Instead, bidders are permitted to bid on a combination of items, like landing rights in an airport or telecommunications rights in several cities. Some items are substitutes and some are complements, and combinations may change over the course of an auction. Allowing bidders to state their preferences on combinations, as opposed to single goods, allows a bidder to more accurately express his or her preferences. However, as the number of items increase, the number of combinations on which people can bid increases exponentially, resulting in a computational problem for the auctioneer, who now has massive amounts of data to process. This has been one of the key issues limiting the successful adoption of combinatorial auctions in practice.

In the past, this limitation was dealt with by the simple expedient of restricting the number of bundles a bidder could bid on. Day and Raghavan looked at the problem differently, developing two compact polynomial bidding formats where bidders submit compact bids that express preferences over an exponential number of bundles.

The research shows that using Bid Tables allows for the expression of substitute
preferences and removes many of the problems associated with using a Simultaneous Ascending Auction (SAA) as the first stage of a multi-stage combinatorial auction. In Day’s dissertation, he expands on this research by developing a three-stage auction, where the first stage deals with substitute preferences, the second stage is an intermediate bundle revelation phase to allow bidders the opportunity for price discoveries on combinations, and followed by a final sealed bidproxy auction.

The second compact bidding format, called Matrix Bids, allows for the expression of both substitute and complementary preferences. These bids express a bidder’s preferences succinctly in polynomial space using a new type of mathematical bidding language that expresses bids in a matrix format.

Day and Raghavan also describe a new method of computing Bidder-Pareto- Optimal-Core (BPOC) points. The technique for generating BPOC points has been extremely arduous and time-consuming. Day and Raghavan develop a new way of computing

BPOC points as a linear program with an exponential number of constraints, and shows a novel constraint generation procedure that starts with a few constraints in the linear program and adds constraints iteratively. Each constraint corresponds to a coalition of bidders that are willing to offer a higher total payment for the goods at auction. The Core Constraint Generation (CCG) technique is several orders of magnitude faster than the best prior methods to determine BPOC points.

Many industries, like electricity and telecommunications, now use high-stakes combinatorial auctions involving the sale of assets or contracts worth many billions of dollars. These new techniques will allow these industries to conduct increasingly sophisticated auctions, resulting in better alignment and pricing of items with concomitant potential gains of many millions of dollars. The methods developed through this research have already been adopted for testing by the Federal Communications Commission in its implementation of the clock-proxy auction and other combinatorial auctions with a last-and-final bidding round. The Federal Aviation Administration used bid tables for bidding in a recent mock auction of landing slots at congested airports. If they decide to use an auction mechanism to allocate landing slots at congested airports, they may use the CCG technique to efficiently find a BPOC core point in the final round of bidding.

Day’s dissertation on compact bidding formats for combinatorial auctions received the INFORMS George B. Dantzig Dissertation Award in 2005. Raghavan’s work in this area continues, with several papers under review.

For more information about this research, please contact rraghava@rhsmith.umd.edu.