Pricing in combinatorial auctions

Our objective is to find prices on individual items in a combinatorial auction that support the optimal allocation of bundles of items, i.e. the solution to the winner determination problem of the combinatorial auction. The item-prices should price the winning bundles according to the corresponding winning bids, whereas the bundles that do not belong to the winning set should have strictly positive reduced cost. That is the bid on a non-winning bundle is strictly less than the sum of prices of the individual items that belong to the bundle, thus providing information to the bidders why they are not in the winning set. Since the winner determination problem is an integer program, in general we cannot find a linear price-structure with these characteristics. However, integer programming duality can be used to obtain this kind of price-information. Normally, it is computationally too expensive to derive the integer programming dual function, but in an iterative combinatorial auction it might be worth to do it since the information provided to the bidders from the non-linear dual function is of great importance for the bidders. Throughout, the ideas are illustrated by means of numerical examples.