Open Competition 4 - Information Technology

Scalable and Usable Technology for Markets with Expressive Bidding

Sponsor: CombineNet, Inc.

• Project Performance Period: 6/1/2002 - 5/31/2005
• Total project (est.): $1,905,400.00
• Requested ATP funds: $1,836,530.00

On-line auctions have become an important new tool of business, but the common on-line merchandise auctions familiar to many people use a relatively simple model. In more advanced "B2B" trading, the interactions are much more complex. On-line auctions are being used to procure electrical components, valves, flexible film, satellite time, trucking, offal, sea freight, and many other commodities. Other possibilities are to allocate radio spectrum bandwidth, daily electricity supplies, air pollution credits, airport landing slots, and many other exchanges. General Electric, for example, conducted over $6 billion in on-line auctions in 2000. A peculiarity of such auctions is that a bidder may value a particular bundle of items significantly more (or less) than the sum of its parts -- for example, if the collection is worth a lot if complete but is valueless if missing some elements. One way to improve the economic efficiency of such transactions is to hold "combinatorial auctions" -- bidders can offer an "all or nothing" bid for a particular bundle of the items at auction. While combinatorial auctions are more efficient in theory, there's a big catch. If there are many items and many bidders (and possibly many sellers), the task of sorting through all the bids to achieve the optimal combination of bids rapidly becomes so complex as to be virtually impossible, even with computers. A further complexity is the need to deal with bids that involve possibly non-monetary "side constraints." ("We want at most 60 winners.") The difficulty increases exponentially with the size of the auction. CombineNet has developed an industry-independent technology that supports combinatorial auctions with side constraints either with one seller and multiple buyers or one buyer and multiple sellers. However current technology does not even come close to the problem of optimally resolving ("clearing") a combinatorial exchange -- a market with multiple sellers and multiple buyers. In this ATP project, CombineNet proposes to develop new algorithms that would dramatically extend the reach of existing technology to the mathematically challenging situation of real-world sized combinatorial exchanges. A key feature of the proposed system will be an "elicitor," a program that would interact with bidders to help them narrow their focus to bundles on which they are likely to be competitive. The elicitor will help both the buyer, by reducing the amount of time spent analyzing and preparing bids that are not actually competitive, and the seller, by helping to narrow the field of possible solutions and so improve the efficiency of the system. CombineNet will receive consulting support from leading researchers at Carnegie-Mellon University (Pittsburgh, Pa.), Harvard University (Cambridge, Mass.), Northwestern University (Evanston, Ill.), University of California (Santa Barbara, Calif.), University of Toronto (Ontario), and University of British Columbia (Vancouver, B.C.). A small start-up company, CombineNet has been unable to find backing for this research outside the ATP because of the high technical risk of the project and the fact that the proposed markets do not yet exist (in part because of the lack of technology). If successful, the CombineNet project will open up new potentials for sophisticated, combinatorial auctions and exchanges in emerging markets such as industrial buying consortia, resale of radio spectrum licenses, and many others, bringing new efficiencies, increased liquidity, reduced risk, and increased speed to the market -- while enhancing competition.

For project information:

Tuomas Sandholm, (412) 654-5994
tsandholm@combinenet.com

ATP Project Manager

Barbara Cuthill, (301) 975-3273
barbara.cuthill@nist.gov