Polynomial algorithms for clearing multi-unit single-item and multi-unit combinatorial reverse auctions

摘要

This paper develops new algorithms for clearing multiunit single-item and multi-unit combinatorial reverse auctions. Specifically, we consider settings where bids are submitted in the form of a supply function and the auctions have sub-additive pricing with free disposal. Our algorithms are based on a greedy strategy and we show that they are of polynomial complexity. Furthermore, we show that the solutions they generate are within a finite bound of the optimal.