Combinatorial auction

A combinatorial auction is a type of smart market in which participants can place bids on combinations of discrete items, or “packages”, rather than individual items or continuous quantities.

Simple combinatorial auctions have been used for many years in estate auctions, where a common procedure is to accept bids for packages of items. They have been used recently for truckload transportation, bus routes, industrial procurement, and in the allocation of radio spectrum for wireless communications.

Combinatorial auctions present challenges compared to traditional auctions. Some 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 instances. Specifically, it is NP-hard, meaning that it is conjectured that there does not exist a polynomial-time algorithm which finds the optimal allocation. The combinatorial auction problem can be modeled as a set packing problem. Therefore, many algorithms have been proposed to find approximated solutions for combinatorial auction problem. For example, Hsieh (2010) proposed a Lagrangian relaxation approach for combinatorial reverse auction problems.

Many of these aspects of combinatorial auctions, including some real-world examples, are also 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. Their paper introduced many 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.

See also

• Optimization (mathematics)
• Combinatorial game theory
• First-price auction

Further reading

• Peter Cramton, Yoav Shoham, and Richard Steinberg (2006). Combinatorial Auctions. MIT Press. ISBN 0-262-03342-9. A contributed book with broad coverage of the topic.
• de Vries, S.; Vohra, R. (2003). "Combinatorial auctions: A survey" (PDF). INFORMS Journal on Computing. 15 (3): 284–309. doi:10.1287/ijoc.15.3.284.16077. ISSN 1526-5528. A bit dated, but a classic survey.
• Vazirani, Vijay V.; Nisan, Noam; Roughgarden, Tim; Tardos, Éva (2007). Algorithmic Game Theory (PDF). Cambridge, UK: Cambridge University Press. ISBN 0-521-87282-0.. A contributed book with a good introductory chapter on combinatorial auctions from a computer science theory perspective; see Chapter 11.
• Rassenti, Stephen J.; Smith, Vernon L.; Bulfin, Robert L. (1982). "A Combinatorial Auction Mechanism for Airport Time Slot Allocation" (PDF). Bell Journal of Economics. 13 (2): 402–417. doi:10.2307/3003463. Early work that popularized the idea of a combinatorial auction.
• Rothkopf, M.; Pekec, A.; Harstad, R. (1998). "Computationally manageable combinatorial auctions". Management Science. 44 (8): 1131–1147. doi:10.1287/mnsc.44.8.1131. An influential early paper on computational considerations.
• Hsieh, Fu-Shiung (2010). "Combinatorial reverse auction based on revelation of Lagrangian multipliers". Decision Support Systems. 48 (2): 323–330. doi:10.1016/j.dss.2009.08.009.
• Shoham, Yoav; Leyton-Brown, Kevin (2009). Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations. New York: Cambridge University Press. ISBN 978-0-521-89943-7. An overview in textbook form; see Section 11.3. Downloadable free online.