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

John Collins, Güleser Demir, Maria L Gini

Research output: Chapter in Book/Report/Conference proceedingConference contribution

13 Scopus citations


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.

Original languageEnglish (US)
Title of host publicationAgent-Mediated Electronic Commerce IV
Subtitle of host publicationDesigning Mechanisms and Systems - AAMAS 2002 Workshop on Agent-Mediated Electronic Commerce, Revised Papers
EditorsJulian Padget, Onn Shehory, David Parkes, Norman Sadeh, William E. Walsh
PublisherSpringer Verlag
Number of pages17
ISBN (Print)9783540003274
StatePublished - 2002
EventWorkshop on Agent-Mediated Electronic Commerce, AAMAS 2002 - Bologna, Italy
Duration: Jul 16 2002Jul 16 2002

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


OtherWorkshop on Agent-Mediated Electronic Commerce, AAMAS 2002

Bibliographical note

Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2002.


Dive into the research topics of 'Bidtree ordering in IDA* Combinatorial auction winner-determination with side constraints'. Together they form a unique fingerprint.

Cite this