A combinatorial auction is an auction in which bidders can place bids on combinations of items, or “packages,” rather than just individual items. Simple combinatorial auctions have been used for many years in estate auctions, where a common procedure is to auction the individual items and then at the end to accept bids for packages of items. They have been used recently for truckload transportation, bus routes, industrial procurement, the allocation of radio spectrum for wireless communications and in forestry for the allocation of timber to private mills (http://www.vicforests.com.au/ind-fr-auct-frame.html], Australia). This article needs additional references or sources for verification. ...

Combinatorial auctions present a host of new challenges as compared to traditional auctions. Some of these challenges are computational, some economic, and some hybrid. An example of a computational problem is how to efficiently determine the allocation once the bids have been submitted to the auctioneer. This is called the winner determination problem. It can be stated as follows: Given a set of bids in a combinatorial auction, find an allocation of items to bidders—including the possibility that the auctioneer retains some items—that maximizes the auctioneer’s revenue. This problem is difficult for large problems. Specifically, it is NP-complete, meaning that a polynomial-time algorithm to find the optimal allocation is unlikely ever to be found. An economic challenge is how to provide incentives for bidders to reveal their true preferences (incentive compatibility). To address this issue, some auction solutions resort to second-price auction (or Vickrey auction). In complexity theory, the NP-complete problems are the most difficult problems in NP, in the sense that they are the ones most likely not to be in P. The reason is that if you could find a way to solve an NP-complete problem quickly, then you could use... In computational complexity theory, polynomial time refers to the computation time of a problem where the time, m(n), is no greater than a polynomial function of the problem size, n. ... A Vickrey auction is a type of sealed-bid auction, where bidders submit written bids without knowing the bid of the other people in the auction. ...

An example of a hybrid problem is the difficulty of concisely describing bids, and efficiently transmitting them to the auctioneer.

Many of these aspects of combinatorial auctions, including some real-world examples, are discussed in the comprehensive book edited by Cramton, Shoham and Steinberg (2006).

Combinatorial auctions were first proposed by Rassenti, Smith, and Bulfin (1982), for the allocation of airport landing slots. This paper introduced many of the key ideas on combinatorial auctions, including the mathematical programming formulation of the auctioneer’s problem, the connection between the winner determination problem and the set packing problem, the issue of computational complexity, the use of techniques from experimental economics for testing combinatorial auctions, and consideration of issues of incentive compatibility and demand revelation in combinatorial auctions.

Further reading

• Cramton, Peter, Yoav Shoham, and Richard Steinberg (2006). Combinatorial Auctions. MIT Press. ISBN 0-262-03342-9. (Hardcover, 649 pages)

• Rassenti, Stephen J., Vernon L. Smith, and Robert L. Bulfin (1982), "A Combinatorial Auction Mechanism for Airport Time Slot Allocation," Bell Journal of Economics, 13, 402-417.

To meet Wikipedias quality standards, this article or section may require cleanup. ...

Related Websites

• Real Estate Auction Information & News