Content area
Full Text
Combinatorial auctions have two features that greatly affect their design: computational complexity of winner determination and opportunities for cooperation among competitors. Dealing with these forces trade-offs between desirable auction properties such as allocative efficiency, revenue maximization, low transaction costs, fairness, failure freeness, and scalability. Computational complexity can be dealt with algorithmically by relegating the computational burden to bidders, by maintaining fairness in the face of computational limitations, by limiting biddable combinations, and by limiting the use of combinatorial bids. Combinatorial auction designs include single-round, first-price sealed bidding, Vickrey-Clarke-Groves (VCG) mechanisms, uniform and market-clearing price auctions, and iterative combinatorial auctions. Combinatorial auction designs must deal with exposure problems, threshold problems, ways to keep the bidding moving at a reasonable pace, avoiding and resolving ties, and controlling complexity.
(Auction Design; Combinatorial Bidding; Bidding with Synergies)
1. Introduction
Auctions have recently come into the spotlight because of their use in deregulation and their explosive propagation on the Internet. Sales of the rights to the use of radio spectrum by the U.S. Federal Communications Commission (FCC) and daily electricity supply auctions are examples of recent innovations in the use of auctions in deregulation. While millions participate in Internet auctions such as those on Ebay.com, the main impact of auctions has been in business-to-business (B2B) applications. For example, in its remarkable makeover that led to the title "E-Business of the Year 2000" by InternetWeek magazine, General Electric has pushed toward online auctions for most of its procurement operations, conducting more than $6 billion in online auctions in 2000 (General Electric Corp. 2001). It is likely that online auctions will continue to play an important role in procurement and, perhaps, in other aspects of business operations of most successful large organizations.
Auctions have a particularly convenient property of aggregating information. Even if no information on the bidders' valuations of an item is available, if there is sufficient demand, the bidtaker can arrange the sale of an item to the bidder who values it the most at a "fair" price. However, when multiple items are for sale, potential auction mechanisms may be impractical due to inherent complexities. There may be further complexities in analyzing equilibrium bidding strategies. While some theoretical limits still constrain what can realistically be done in practice, what...