Reducing Complexity In Winner Determination For Combinatorial Ascending Auctions

Chihiro Ono*, Satoshi Nishiyama and Hiroki Horiuchi

KDDI R&D Laboratories Inc., 2-1-15 Ohara, Kamifukuoka-shi, Saitama 356-8502, Japan

Received 30 October 2002; revised 20 February 2003; accepted 28 February 2003. ; Available online 9 May 2003.

Abstract

This paper describes an algorithm to reduce the computational complexity of winner determination for combinatorial ascending auction where bidding agents can place a bid for a combination of items at an arbitrary timing via the Internet. At e-marketplaces, where many services can be dynamically searched and used, an auction is a key technology for realizing market-based negotiations among `software agents'. Although some algorithms for reducing complexity have been proposed, they are only suitable for one-shot auctions where bidders submit bids only once simultaneously. Thus, we reduce computational burdens by using the previous valuation of bids for doing the next valuation. We then verify the effectiveness through evaluation.

Author Keywords: Combinatorial auctions; E-marketplace; Computational complexity

*Corresponding author.

www.ABA-RD.org
"Agents for Business Automation" Ó Research & Development