Sequential Bundle-Bid Single-Sale Auction Algorithms for Decentralized Control

Koenig, Sven; Tovey, Craig A.; Zheng, Xiaoming; Sungur, Ilgaz

Sequential Bundle-Bid Single-Sale Auction Algorithms for Decentralized Control

Sven Koenig, Craig A. Tovey, Xiaoming Zheng, Ilgaz Sungur

Download BibTeX Cite

Proceedings of the Twentieth International Joint Conference on Artificial Intelligence. Pages 1359-1364.

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 to be 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.

Sven Koenig, Craig A. Tovey, Xiaoming Zheng, and Ilgaz Sungur. 2007. Sequential Bundle-Bid Single-Sale Auction Algorithms for Decentralized Control. In Proceedings of the Twentieth International Joint Conference on Artificial Intelligence, IJCAI-07. IJCAI, 1359–1364. https://ijcai.org/proceedings/2007/219

@inproceedings{ijcai2007p219,
  title     = {Sequential Bundle-Bid Single-Sale Auction Algorithms for Decentralized Control},
  author    = {Koenig, Sven and Tovey, Craig A. and Zheng, Xiaoming and Sungur, Ilgaz},
  booktitle = {Proceedings of the Twentieth International Joint Conference on
               Artificial Intelligence, {IJCAI-07}},
  publisher = {International Joint Conferences on Artificial Intelligence},
  editor    = {Ramon López de Mántaras},
  pages     = {1359--1364},
  year      = {2007},
  url       = {https://ijcai.org/proceedings/2007/219},
}

TY  - CPAPER
TI  - Sequential Bundle-Bid Single-Sale Auction Algorithms for Decentralized Control
AU  - Koenig, Sven
AU  - Tovey, Craig A.
AU  - Zheng, Xiaoming
AU  - Sungur, Ilgaz
T2  - Proceedings of the Twentieth International Joint Conference on Artificial Intelligence, IJCAI-07
PB  - International Joint Conferences on Artificial Intelligence
PY  - 2007
SP  - 1359
EP  - 1364
UR  - https://ijcai.org/proceedings/2007/219
ER  -