Bidtree ordering in IDA* Combinatorial auction winner-determination with side constraints


Collins J., Demir G., Gini M.

Workshop on Agent-Mediated Electronic Commerce, AAMAS 2002, Bologna, Italy, 16 July 2002, vol.2531, pp.17-33 identifier

  • Publication Type: Conference Paper / Full Text
  • Volume: 2531
  • Doi Number: 10.1007/3-540-36378-5_2
  • City: Bologna
  • Country: Italy
  • Page Numbers: pp.17-33
  • Dokuz Eylül University Affiliated: No

Abstract

© Springer-Verlag Berlin Heidelberg 2002.We extend Sandholm’s bidtree-based IDA* algorithm for combinatorial auction winner determination to deal with negotiation over tasks with precedence constraints. We evaluate its performance, and show that the order of items in the bidtree has a major impact on performance. Specifically, performance is enhanced if the items with the largest numbers of bids are at the top of the bidtree. This is due to the fact that the effective branching factor in the search tree is controlled by the number of bids returned from a query to the bidtree, which in turn is strongly related to its construction.