Combinatorial auction
Encyclopedia
A combinatorial auction is a type of smart market
in which participants can place bids on combinations of discrete items, or “packages,” rather than just individual items or continuous quantities.
Simple combinatorial auction
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.
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-complete
, meaning that a polynomial-time algorithm to find the optimal allocation is unlikely to be found, unless P = NP. 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 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.
A bit dated, but a classic survey.
Early work that popularized the idea of a combinatorial auction.
An influential early paper on computational considerations.
An overview in textbook form; see Section 11.3. Downloadable free online.
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, but rather to or from a pool...
in which participants can place bids on combinations of discrete items, or “packages,” rather than just individual items or continuous quantities.
Simple combinatorial auction
Auction
An auction is a process of buying and selling goods or services by offering them up for bid, taking bids, and then selling the item to the highest bidder...
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.
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-complete
NP-complete
In computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...
, meaning that a polynomial-time algorithm to find the optimal allocation is unlikely to be found, unless P = NP. 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 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
Incentive compatibility
In mechanism design, a process is said to be incentive-compatible if all of the participants fare best when they truthfully reveal any private information asked for by the mechanism. As an illustration, voting systems which create incentives to vote dishonestly lack the property of incentive...
and demand revelation in combinatorial auctions.
Further reading
- Cramton, Peter, Yoav Shoham, and Richard Steinberg (2006). Combinatorial Auctions. MIT PressMIT PressThe MIT Press is a university press affiliated with the Massachusetts Institute of Technology in Cambridge, Massachusetts .-History:...
. ISBN 0-262-03342-9. A contributed book with broad coverage of the topic.
A bit dated, but a classic survey.
- Nisan, N., Roughgarden, T., Tardos, E., Vazirani, V (2007). Algorithmic Game Theory. Cambridge University PressCambridge University PressCambridge University Press is the publishing business of the University of Cambridge. Granted letters patent by Henry VIII in 1534, it is the world's oldest publishing house, and the second largest university press in the world...
. ISBN 9780521872829. 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 overview in textbook form; see Section 11.3. Downloadable free online.