Journal of Applied Mathematics and Decision Sciences
Volume 2005 (2005), Issue 1, Pages 19-32
doi:10.1155/JAMDS.2005.19
A formulation of combinatorial auction via reverse convex programming
Ecole des Hautes Etudes Commercials (HEC), Université de Lausanne, Lausanne 1015, Switzerland
Received 10 January 2004; Revised 12 July 2004
Copyright © 2005 Henry Schellhorn. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Abstract
In combinatorial auctions, buyers and sellers bid not only for single items but also for combinations (or “bundles”, or “baskets”) of items. Clearing the auction is in general an NP-hard problem; it is usually solved with integer linear programming. We proposed in an earlier paper a continuous approximation
of this problem, where orders are aggregated and integrality constraints are relaxed. It was proved that this problem could be solved efficiently in two steps by calculating two fixed points, first the fixed point of a contraction mapping, and then of a set-valued function. In this paper, we generalize the problem to incorporate constraints on maximum price changes between two auction rounds. This generalized problem cannot be solved by the aforementioned methods and necessitates reverse convex programming techniques.