Abstract
This paper presents negotiated search, a framework for coordinating distributed search among heterogeneous agents. Unlike traditional multi-agent systems that attempt to avoid conflict, negotiated search treats conflict as a valuable control signal. By interleaving local search with incremental requirement relaxation and feedback, the algorithm enables diverse agents with incompatible internal goals to reach mutually acceptable global solutions. The framework is demonstrated through the TEAM system and evaluated in mechanical design and contract negotiation domains.
Introduction
In the early 1990s, the development of multi-agent systems (MAS) faced a significant hurdle: the transition from monolithic, task-specific silos to reusable agents. Reusable agents are independent software components designed to be integrated into various systems without prior knowledge of their peers. However, this independence introduces inherent conflict. Because heterogeneous agents are developed by different parties, they often possess incompatible internal goals, evaluation criteria, and search spaces.
Lander and Lesser argue that in a world of diverse agents, conflict is inevitable. The challenge lies in how a group of these "black box" agents can coordinate their search to find a global solution that satisfies all participants. The authors propose that instead of avoiding conflict, systems should leverage it as a source of control information to guide the search process.
The Negotiated Search Framework
The authors propose the negotiated search algorithm, implemented within the TEAM framework. This process is not a linear progression but a state-based evolution of a "composite solution." The search involves four interleaved tasks: local search by individual agents, integration of local solutions into a shared composite, information exchange to refine the search space, and collective assessment of emerging solutions.
Central to this framework is a set of negotiated-search operators that agents instantiate based on their specific capabilities:
initiate-solution: Generates an initial base proposal.extend-solution: Adds components to an existing proposal while checking for compatibility.critique-solution: Evaluates a proposal's validity without modifying it.relax-solution-requirement: Acts as a "pressure valve" by incrementally lowering soft constraints when no solution is found.store/retrieve-information: Allows agents to learn from conflicts, pruning local search paths to avoid "dead ends" discovered by peers.
As illustrated in the state transition diagram (Figure 1), the algorithm navigates through various solution states—from partial to complete, and from unacceptable to acceptable. Conflict, represented by transitions to infeasible or unacceptable states, triggers feedback loops that inform subsequent search steps or requirement relaxations.
Evaluation and Key Insights
The algorithm was evaluated using two custom application systems: STEAM, a seven-agent system for mechanical design of steam condensers, and AGREE, a two-agent system for buy/sell contract negotiation.
Several key insights emerged from these evaluations:
- Conflict as Metadata: Rejections are treated as informative feedback rather than simple failures. This metadata helps agents prune their search spaces, preventing wasted computation on paths guaranteed to be rejected by others.
- Democratic Acceptability: A solution is only considered complete once all agents have critiqued it, ensuring mutual acceptability even if the result is not locally optimal for any single agent.
- Robustness of Relaxation: The distinction between hard and soft constraints allows the system to avoid deadlocks in over-constrained problems through incremental relaxation.
- Versatility: Negotiated search proved effective even when search operators were randomly distributed across agents, demonstrating its suitability for unpredictable, heterogeneous environments.
Conclusion and Limitations
Negotiated search provides a reliable baseline for distributed coordination where specialized, brittle algorithms might fail. However, the model currently assumes cooperative agents; it does not account for hostile environments where agents might misrepresent constraints for competitive advantage. Additionally, the approach incurs significant memory overhead for maintaining concurrent solution paths and communication costs for assimilating feedback. Future work suggests developing more sophisticated relaxation mechanisms that respond dynamically to the specific characteristics of the problem state.
Summary updated