Multi-round iterative auctions are motivated by the fact that the market maker often lacks complete and truthful information about the bidders private valuations of the resources on sale. The literature on the design of iterative mechanisms for combinatorial auctions has addressed only the most basic cases and has been dominated by primal-dual approaches. In this paper, we consider a general production/consumption economy of interdependent goods, for which we investigate iterative auction mechanisms based on mathematical programming decomposition methods. We focus specifically on two well-known approaches: the Lagrangian relaxation, and Dantzig-Wolfe column-generation.

In an application of real time fleet allocation, an integer multicommodity network flow problem has to be solved repeatedly and a solution is needed very quickly. The problem is decomposed geographically and by commodity. A fast heuristic checks feasibility of demands and a continuous algorithm provides near optimal solutions.