Column aggregation-based pricing combinatorial auctions

Arbeitspapier

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.

Object Details

• Language: Englisch

References and Relationships

• Bibliographic citation: Series: Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel ; No. 624

Classification and Topics

• Classification: Management
• Subject: Combinatorial auctions ; set packing ; dual prices ; linear programming ; Auktionstheorie ; Scheduling-Verfahren ; Duales Optimierungsproblem ; Mathematische Optimierung ; Test

Contributors, Places and Time

• Event: Geistige Schöpfung
• (who): Drexl, Andreas ; Jørnsten, Kurt ; Knof, Diether
• Event: Veröffentlichung
• (who): Universität Kiel, Institut für Betriebswirtschaftslehre ; ZBW – Leibniz Information Centre for Economics
• (where): Kiel
• (when): 2007

Further information

• Handle: http://hdl.handle.net/10419/147677
• Last update: 10.03.2025, 11:41 AM CET