Abstract


Sven Koenig, Craig Tovey, Xiaoming Zheng and Ilgaz Sungur, Sequential Bundle-Bid Single-Sale Auction Algorithms for Decentralized Control, In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), pages 1359-1365, 2007

Abstract: We study auction-like algorithms for the distributed allocation of tasks to cooperating agents. To reduce the team cost of sequential single-item auction algorithms, we generalize them to assign more than one additional task during each round, which increases their similarity to combinatorial auction algorithms. We show that, for a given number of additional tasks tobe assigned during each round, every agent needs to submit only a constant number of bids per round and the runtime of winner determination is linear in the number of agents. The communication and winner determination costs do not depend on the number of tasks and thus scale to a large number of tasks for small bundle sizes. We then demonstrate empirically that the team cost of sequential bundle-bid single-sale (= single-item) auction algorithms can be substantially smaller than that without bundles for multi-agent routing problems with capacity constraints.

Download the paper in pdf.