15th European Conference on Artificial Intelligence
  July 21-26 2002     Lyon     France  
   

ECAI-2002 Conference Paper

[PDF] [full paper] [prev] [tofc] [next]

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.


[prev] [tofc] [next]


ECAI-2002 is organised by the European Coordinating Committee for Artificial Intelligence (ECCAI) and hosted by the UniversitÚ Claude Bernard and INSA, Lyon, on behalf of Association Franšaise pour l'Intelligence Artificielle.