Michael Schillo
ABSTRACT
The contract net protocol is a widely used protocol in DAI, as it proved to be a flexible and low communication interaction protocol for task assignment. It is however not clear in which manner agents participating in a contract net should allocate their resources if a large number of contract net protocols is performed concurrently. If the agent allocates too many resources too early, e.g. when making a bid, it may not get any bid accepted and resources have been allocated while other negotiations have come to an end and it is no longer able to make bids for them. If it allocates resources too late, e.g. after being awarded the contract, it may have made bids for more tasks than its resources allow for, possibly all being accepted and resulting in commitments that cannot be kept. We call this dilemma the Eager Bidder Problem. Apart from resource allocation this problem is of further importance as it constitutes the "dual" problem to engaging in multiple simultaneous first-price sealed-bid auctions.We present an ad hoc solution and two more complex strategies for solving this problem. Furthermore, we introduce a new method based on a statistical approach. We describe these mechanisms and how they deal with the concept of commitment at different levels. We conclude with criteria for the decision which of these mechanisms is best selected for a given problem domain.
- H. Bürkert, K. Fischer, and G. Vierke. Holonic transport scheduling with TELETRUCK. Applied Artificial Intelligence, 14(7):697--726, 2000Google Scholar
Cross Ref
- C. Excelente-Toledo, C. Bourne, and N. Jennings. Reasoning about commitments and penalties for coordination between autonomous agents. In Proceedings of the Fifth International Conference on Autonomus Agents, pages 131--138. ACM, 2001 Google ScholarDigital Library
- FIPA. (Foundation for Intelligent Agents), http://www.fipa.org/repository/ips.htmlGoogle Scholar
- FIPA-OS. http://fipa-os.sourceforge.net/Google Scholar
- K. Fischer, J. P. Müller, and M. Pischel. A model for cooperative transportation scheduling. In Proceedings of the 1st International Conference on Multiagent Systems (ICMAS'95), pages 109--116, San Francisco, June 1995Google ScholarDigital Library
- L. Garrido and K. Sycara. Multiagent meeting scheduling: Preliminary experimental results. In Proceedings of the 2nd International Conference on Multiagent Systems (ICMAS'96), 1996Google Scholar
- JADE. http://www.sharon.cselt.it/projects/jade/Google Scholar
- N. R. Jennings. Commitments and conventions: The foundation of coordination in multi-agent systems. The Knowledge Engineering Review, 8(3):223--250, 1993Google ScholarCross Ref
- V. Parunak. Manufacturing experience with the contract net. In M. Huhns, editor, Distributed Artificial Intelligence, pages 285--310. Pitman, London, 1995Google Scholar
- C. Preist and A. Byde and C. Bartolini. Economic Dynamics of Agents in Multiple Auctions. In Proceedings of the Fifth International Conference on Autonomous Agents (Agents'01), pages 545--551, 2001 Google ScholarDigital Library
- R. Rabelo, L. Camarinha-Matos, and H. Afsarmanesh. Multi-agent perspectives to agile scheduling. In R. Rabelo, L. Camarinha-Matos, and H. Afsarmanesh, editors, Intelligent Systems for Manufacturing, pages 51--66. Kluwer Academic Publishers, 1998 Google ScholarDigital Library
- J. Rosenschein and G. Zlotkin. Rules of Encounter. The MIT Press, Cambridge, Mass., 1994Google Scholar
- T. Sandholm. Negotation among Self-Interested Computationally Limited Agents. PhD thesis, University of Massachusetts at Amherst, Department of Computer Science, 1996 Google ScholarDigital Library
- T. Sandholm and V. Lesser. Advantages of a leveled commitment contracting protocol. In Proceedings of the 13th National Conference on Artificial Intelligence (AAAI-96), pages 126--133, 1996 Google ScholarDigital Library
- M. Schillo, K. Fischer, and T. Knabe. The contract net with confirmation protocol: A solution to a fundamental problem of DAI. Technical memo TM-01-01, DFKI, 2001Google Scholar
- S. Sen and E. Durfee. On the design of an adaptive meeting scheduler. In Proceedings of the 10th IEEE Conference on AI Applications, 1994Google ScholarCross Ref
- W. Shen and D. Norrie. An agent-based approach for dynamic manufacturing scheduling. In Proceedings of the 3rd International Conference on the Practical Applications of Agents and Multiagent Systems, 1998Google Scholar
- R. G. Smith. The contract net protocol: High level communication and control in a distributed problem solver. IEEE Transactions on Computers, Series C-29(12):1104--1113, 1980Google ScholarDigital Library
- W. Vickrey. Counter speculation, auctions, and competitive sealed tenders. Journal of Finance, 16(1):8--37, 1961Google ScholarCross Ref
- G. Wei&selig;, editor. Multiagent Systems. A Modern Approach to Distributed Artificial Intelligence. The MIT Press, Cambridge, MA, 1999Google Scholar
- ZEUS. http://www.btexact.com/projects/agents/Google Scholar
Index Terms
- The eager bidder problem: a fundamental problem of DAI and selected solutions
Recommendations
The dining bidder problem: à la russe et à la française
Item bidding auctions are a line of research which provides a simple and often efficient alternative to traditional combinatorial auction design - in particular, they were inspired by real world auction houses, like eBay and Sotheby's. We survey the ...
Iterative Combinatorial Auctions with Bidder-Determined Combinations
In combinatorial auctions, multiple distinct items are sold simultaneously and a bidder may place a single bid on a set (package) of distinct items. The determination of packages for bidding is a nontrivial task, and existing efficient formats require ...
Bidder's strategy under group-buying auction on the Internet
The group-buying auction is a new kind of dynamic pricing mechanism on the Internet. It is a variant of the sellers' price double auction, which makes the bidders as a group through Internet to get the volume discounts, i.e., the more bidders bid, the ...
Comments