An Analysis of a Combinatorial Auction

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. I.e. 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, in this article we make use of sensitivity analysis and duality in linear programming to obtain this kind of price-information. The ideas are illustrated by means of numerical examples.