The Eager Bidder Problem: A Fundamental Problem of DAI and Selected Solutions

摘要

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.