Fast winner determination for agent coordination with SBB auctions

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Fast winner determination for agent coordination with SBB auctions

Full text

Pdf (155 KB)

Source

International Conference on Autonomous Agents archive
Proceedings of The 8th International Conference on Autonomous Agents and Multiagent Systems - Volume 2 table of contents

Budapest, Hungary

SESSION: Interactions table of contents

Pages 1197-1198

Year of Publication: 2009

ISBN:978-0-9817381-7-8

Authors

Kenny Daniel	University of Southern California, Los Angeles, CA
Sven Koenig	University of Southern California, Los Angeles, CA

Sponsors

: The Foundation for Intelligent Physical Agents
Microsoft Research : Microsoft Research
: Whitestein Technologies
: European Office of Aerospace Research and Development, Air Force Office of Scientific Research, United States Air Force Research Laboratory
: Drexel University
: Wiley -- Blackwell Ltd

Publisher

International Foundation for Autonomous Agents and Multiagent Systems Richland, SC

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 7, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

ABSTRACT

The runtime of winner determination for each round of a sequential bundle-bid auction (= SBB auction) has recently been shown to be linear in the number of submitted bids, which makes SBB auctions appealing for solving cooperative task-assignment problems. In this paper, we introduce the Shrewd (= SHrewd Resource Efficient Winner Determination) algorithm, whose runtime is linear in the number of submitted bids but typically much smaller than the runtime of the existing winner-determination algorithm for SBB auctions, making them feasible for larger bundle sizes.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	M. Dias, R. Zlot, N. Kalra, and A. Stentz. Market-based multirobot coordination: A survey and analysis. Proceedings of the IEEE, 94:1257--1270, 2006.
	2	S. Koenig, C. Tovey, X. Zheng, and I. Sungur. Sequential bundle-bid single-sale auction algorithms for decentralized control. In Proceedings of the International Joint Conference on Artificial Intelligence, pages 1359--1365, 2007.
	3	M. Lagoudakis, V. Markakis, D. Kempe, P. Keskinocak, S. Koenig, A. Kleywegt, C. Tovey, A. Meyerson, and S. Jain. Auction-based multi-robot routing. In Proceedings of the International Conference on Robotics: Science and Systems, 2005.
	4	C. Tovey, M. Lagoudakis, S. Jain, and S. Koenig. The generation of bidding rules for auction-based robot coordination. In L. Parker, F. Schneider, and A. Schultz, editors, Multi-Robot Systems: From Swarms to Intelligent Automata, pages 3--14. Springer, 2005.