Abstract
Automated negotiation protocols typically assume static and independent agent preferences. However, real-world scenarios often involve interdependent issues and preferences that evolve over the course of a negotiation. This paper introduces a novel mediation mechanism utilizing a Genetic Algorithm (GA) to navigate these complex, dynamic utility spaces. By evolving a population of potential contracts and leveraging Pareto dominance, the mediator can track the optimal trade-offs (the Pareto front) without requiring agents to disclose their private utility functions. Experimental evaluations show that this GA-based approach maintains high social welfare and adaptability compared to traditional hill-climbing baselines, though challenges remain in scaling to large numbers of agents.
Introduction
In traditional automated negotiation, researchers often simplify the problem by assuming linear utility functions and static preferences. In reality, issues are frequently interdependent—where the value of one choice depends on another—and preferences can shift due to external factors or the negotiation process itself. Finding a Pareto optimal agreement in such a "moving target" landscape is a significant challenge. Most existing protocols are prone to getting trapped in local optima or failing to adapt when the underlying "ground truth" of agent desires changes.
Proposed Mediation Mechanism
The authors propose a mediator-led protocol based on a Genetic Algorithm (GA). This framework maps the negotiation components to biological concepts:
- Chromosome: A complete potential contract.
- Genetic Locus: A specific issue under negotiation.
- Gene: The value assigned to a particular issue.
The protocol operates in a continuous loop:
- Distribution: The mediator broadcasts a population of chromosomes (contracts) to all agents.
- Local Ranking: Agents evaluate these contracts using their private, non-linear utility functions and return a ranked list of the top 50%.
- Pareto Selection: The mediator identifies Pareto-dominant points from the rankings. This preserves agent privacy as the mediator only sees relative preferences, not absolute utility values.
- Evolution: The mediator applies crossover and mutation operators to the dominant points to generate a new generation of contracts.
- Iteration: The process repeats, allowing the contract population to "follow" the Pareto front as it moves through the utility space.
Experimental Setup
The mechanism was evaluated in simulated environments with the following parameters:
- Scale: Scenarios involving 2 and 20 agents.
- Issues: Negotiations over 5 issues, each with values in the range [0, 9].
- Complexity: Non-linear utility was modeled using 30 unary, 30 binary, and 30 trinary constraints.
- Dynamics: To simulate shifting preferences, utility values were modified at a rate of 0.8x or 1.1x per iteration.
Key Insights and Ideas
A core innovation of this approach is Dominant Inheritance, which allows the algorithm to retain Pareto-optimal trade-offs across generations. This memory is crucial for exploring the utility space while maintaining high-quality candidates.
As shown in the conceptual landscape above, the GA approach is better suited for "tracking" the front. While a standard optimization might seek a static peak, the GA's population-based search allows it to adapt as the utility landscape shifts or biases are introduced. This privacy-preserving optimization ensures that agents do not have to reveal sensitive internal constraints.
Key Results
The GA-based mediator was compared against a Hill-Climbing (HC) baseline. The results highlight the GA's superior exploration capabilities.
- Adaptability: The GA consistently found points closer to the Pareto front, whereas HC often became stuck in local optima.
- Social Welfare: The GA maintained higher aggregate utility across agents, even in dynamic environments.
- Scalability Challenges: While the system performed exceptionally well with 2 agents, the gap between the GA and the theoretical optimum widened as the number of agents increased to 20. This suggests that the utility space becomes increasingly "jagged" and difficult to navigate with more participants.
Conclusion and Future Work
The proposed GA-based mediation mechanism effectively addresses the challenges of interdependent and dynamic preferences in automated negotiation. By focusing on Pareto dominance and population evolution, it provides a robust way to track optimal agreements while maintaining agent privacy. Future research will explore improving scalability for large-scale multi-agent systems, developing more advanced mediator strategies for fairness, and investigating the impact of strategic agent behavior on the negotiation outcome.
Summary updated