A combinatorial auction is a type of
smart market A smart market is a periodic auction which is cleared by the operations research technique of mathematical optimization, such as linear programming. The smart market is operated by a market manager. Trades are not bilateral, between pairs of people, ...
in which participants can place bids on combinations of discrete heterogeneous items, or “packages”, rather than individual items or continuous quantities. These packages can be also called lots and the whole auction a multi-lot auction. Combinatorial auctions are applicable when bidders have non-additive valuations on bundles of items, that is, they value combinations of items more or less than the sum of the valuations of individual elements of the combination.
Simple combinatorial
auction
An auction is usually a process of Trade, buying and selling Good (economics), goods or Service (economics), services by offering them up for Bidding, bids, taking bids, and then selling the item to the highest bidder or buying the item from th ...
s 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. In recent years, procurement teams have applied reverse combinatorial auctions in the procurement of goods and services. This application is often referred to as sourcing optimization. Since construction
procurement
Procurement is the process of locating and agreeing to terms and purchasing goods, services, or other works from an external source, often with the use of a tendering or competitive bidding process. The term may also refer to a contractual ...
often involves negotiations over multiple components, combinatorial
reverse auction Reverse or reversing may refer to:
Arts and media
* ''Reverse'' (Eldritch album), 2001
* ''Reverse'' (2009 film), a Polish comedy-drama film
* ''Reverse'' (2019 film), an Iranian crime-drama film
* ''Reverse'' (Morandi album), 2005
* ''Reverse'' ...
s are suggested to reduce costs in this industry.
Although they allow bidders to be more expressive, combinatorial auctions present both computational and game-theoretic challenges compared to traditional auctions. 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.
The winner determination problem 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
In computational complexity theory, a computational problem ''H'' is called NP-hard if, for every problem ''L'' which can be solved in non-deterministic polynomial-time, there is a polynomial-time reduction from ''L'' to ''H''. That is, assumi ...
, meaning that it is conjectured that there does not exist a
polynomial-time
In theoretical computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations p ...
algorithm which finds the optimal allocation. The combinatorial auction problem can be modeled as a
set packing
Set packing is a classical NP-complete problem in computational complexity theory and combinatorics, and was one of Karp's 21 NP-complete problems. Suppose one has a finite set ''S'' and a list of subsets of ''S''. Then, the set packing problem as ...
problem. Therefore, many algorithms have been proposed to find approximated solutions for combinatorial auction problem. For example, Hsieh (2010) proposed a
Lagrangian relaxation
In the field of mathematical optimization, Lagrangian relaxation is a relaxation method which approximates a difficult problem of constrained optimization by a simpler problem. A solution to the relaxed problem is an approximate solution to the o ...
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).
History
Combinatorial auctions were first proposed by Rassenti, Smith, and Bulfin (1982), for the allocation of airport
landing slot
__NOTOC__
A landing slot, takeoff slot, or airport slot is a permission granted by a slot coordinator to use the infrastructure of an airport designated as Level 3 (Coordinated Airport) for take-off and/or landing at a specific time and date. Slo ...
s. 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
In game theory and economics, a mechanism is called incentive-compatible (IC) if every participant can achieve their own best outcome by reporting their true preferences. For example, there is incentive compatibility if high-risk clients are bette ...
and demand revelation in combinatorial auctions.
Combinatorial Clock Auction
A special case of a combinatorial auction is the combinatorial clock auction (CCA), which combines a clock auction, during which bidders may provide their confirmations in response to the rising prices, with a subsequent sealed bid auction, in which bidders submit sealed package bids. The auctioneer uses the final bids to compute the best value allocation and the
Vickrey payments. CCAs have been shown to be prone to the possibility of raising rivals’ cost.
[ Janssen, M. and B. Kasberger. 2019. On the clock of the combinatorial clock auction. Theoretical Economics 14, pp. 1271-1307. https://doi.org/10.3982/TE3203]
See also
*
*
*
References
Further reading
* Peter Cramton, Yoav Shoham, and Richard Steinberg (2006). ''Combinatorial Auctions''.
MIT Press
The MIT Press is the university press of the Massachusetts Institute of Technology (MIT), a private research university in Cambridge, Massachusetts. The MIT Press publishes a number of academic journals and has been a pioneer in the Open Ac ...
. . A contributed book with broad coverage of the topic.
* A bit dated, but a classic survey.
*. A contributed book with a good introductory chapter on combinatorial auctions from a computer science theory perspective; see Chapter 11.
* Early work that popularized the idea of a combinatorial auction.
* An influential early paper on computational considerations.
* An application of combinatorial auctions for transportation services procurement.
*
* Palacios-Huerta, Ignacio, David C. Parkes, and Richard Steinberg. 2024.
Combinatorial Auctions in Practice" ''Journal of Economic Literature'', 62 (2): 517-53.
* {{cite book , last1=Shoham , first1=Yoav , last2=Leyton-Brown , first2=Kevin , title=Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations , publisher=
Cambridge University Press
Cambridge University Press was the university press of the University of Cambridge. Granted a letters patent by King Henry VIII in 1534, it was the oldest university press in the world. Cambridge University Press merged with Cambridge Assessme ...
, isbn=978-0-521-89943-7 , url=http://www.masfoundations.org , year=2009 , location=New York An overview in textbook form; see Section 11.3
Downloadable free online
Types of auction