ECAI-2002 Conference Paper

[full paper]

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

Viet Dung Dang, Nicholas R. Jennings

This paper develops new algorithms for clearing multi-unit single-item and multi-unit combinatorial reverse auctions. Specifically, we consider settings where bidders submit their bids 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.

Keywords: Multi-Agent Systems, Autonomous Agents

Citation: Viet Dung Dang, Nicholas R. Jennings: Polynomial algorithms for clearing multi-unit single-item and multi-unit combinatorial reverse auctions. In F. van Harmelen (ed.): ECAI2002, Proceedings of the 15th European Conference on Artificial Intelligence, IOS Press, Amsterdam, 2002, pp.23-27.