A formulation of combinatorial auction via reverse convex programming

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 anearlierpaperacontinuousapproximationofthisproblem,whereordersareaggregated and integrality constraints are relaxed. It was proved that this problem could be solved efficientlyintwostepsbycalculatingtwofixedpoints,firstthefixedpointofacontraction 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.