Column aggregation-based pricing combinatorial auctions

Combinatorial auctions permitting bids on bundles of items have been developed to remedy the exposure problem associated with single-item auctions. Given winning bundle prices a set of item prices is called market clearing or equilibrium if all the winning bids are greater than or equal and if all the losing bids are less than or equal to the total price of the bundle items. However, the prices for individual items are not readily computed once the winner determination problem is solved. This is due to the duality gap of integer programming caused by the indivisibility of the items. In this paper we propose a family of linear programming models the optimal solution of which is integral "almost always", producing linear prices at the expense of having reduced cost zero for the aggregate winning bids only. We provide a computational proof of this conjecture by an in-depth experimental study of 18,000 instances from the combinatoriaI auction test suite (CATS; see [13]). Summarizing this analysis we have linear prices for all but five of the whole bunch of instances and, hence, there exists a linear price function that supports the optimal allocation of winning bundles.