Dynamic Negotiation

Contents

We present an anytime algorithm for adapting a negotiation to a dynamically changing environment in which either new tasks can appear or the availability of resources can change during the negotiation. We use a particular negotiation algorithm, which we call Mediation, in which problem solutions are suggested by a mediator to a team of bidders. In Mediation, agents can bid in the context of a particular set of other tasks; both positive and negative task interactions can be taken into consideration. In addition, an agent’s bid need not be restricted to a single value but rather can span a range of values. Bids are also augmented with information that compactly captures important elements of an agent’s local state in the form of a description of potential positive and negative interactions with other commitments. We claim that agents involved in a negotiation can make better use of information from prior interactions when bids are more informative in the way described. We provide support for our claim through a set of experiments in a real-time sensor allocation problem.