A combinatorial procurement auction featuring bundle price revelation without free-riding

Combinatorial auctions are currently becoming a common practice in industrial procurement, allowing bidders (sellers of goods and services in the procurement setting) to avoid the risk of selling good or service bundles that are incomplete, inefficient, or excessively expensive to deliver. Two major concerns in combinatorial auction design are the revelation or discovery of market price information over the course of the auction, and the inherent computational difficulty (NP-hardness) of the underlying “winner-determination” problem. In this paper we describe a new general auction format maintaining the benefits of the adaptive user-selection approach without the problems of free-riding, inefficiency, or distortionary linear prices. This auction format is particularly well-suited to the largest combinatorial auctions for which winner-determination is computationally tractable, because it provides bundle synergy information that is computable in polynomial time for all interactive phases.