An efficient approximate algorithm for winner determination in combinatorial auctions

Yuko Sakurai, Makoto Yokoo, Koji Kamei

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)


This paper presents an approximate algorithm for the winner determination problem in combinatorial auctions, which is based on limited discrepancy search (LDS). Internet auctions have become an integral part of Electronic Commerce and can incorporate large-scale, complicated types of auctions including combinatorial auctions, where multiple items are sold simultaneously and bidders can express complementarity among these items. Although we can increase participants' utilities by using combinatorial auctions, determining the optimal winners is a complicated constraint optimization problem that is shown to be NP-complete. We introduce the idea of LDS to an existing algorithm based on A*. The merit of LDS is that it can avoid time-consuming re-computation of heuristic function h(·), since LDS is less sensitive to the quality of h(·). It can also limit the search efforts only to promising regions. Experiments using various problem settings show that, compared with the existing optimal algorithm, LDS can find near-optimal solutions (better than 95%) very quickly (around 1% of the running time).

Original languageEnglish
Pages (from-to)445-453
Number of pages9
JournalTransactions of the Japanese Society for Artificial Intelligence
Issue number5
Publication statusPublished - 2001
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Artificial Intelligence


Dive into the research topics of 'An efficient approximate algorithm for winner determination in combinatorial auctions'. Together they form a unique fingerprint.

Cite this