Introduction
Automated negotiation is a cornerstone of multi-agent systems, where agents must reach agreements on multiple issues such as price, delivery time, and warranty. While deep reinforcement learning (RL) has shown promise in creating versatile negotiating agents, it faces a major hurdle: scalability. Previous state-of-the-art models, like VeNAS (Versatile Negotiating Agent Strategy), rely on architectures that struggle as the "outcome space"—the total number of possible deal combinations—grows. In large domains, the number of possible actions becomes so vast that standard RL agents fail to learn effective strategies. This research introduces the Multi-Issue Policy Network (MiPN), a deep RL architecture that factorizes negotiation strategies into issue-specific policies to overcome these limitations.
Methodology
The core innovation of the Multi-Issue Policy Network (MiPN) lies in its policy factorization. Instead of treating a multi-issue bid as a single, massive action, MiPN decomposes the policy into independent components. It utilizes one policy function to decide whether to accept an offer and separate policy functions for each individual issue in the negotiation.
As illustrated in the architecture above, the model consists of:
- Input Layer: Vectorizes the history of bids and the current time (state).
- Hidden Layers: Features a feature extractor and an end-to-end policy network.
- Output Layer: Produces vectorized bids for offers, acceptance signals, and value estimations.
The agent is trained using Proximal Policy Optimization (PPO). Because the policy is factorized, the policy gradient loss can be calculated independently for each issue, which is the key to its scalability in domains with tens of thousands of possible outcomes.
Experimental Setup
The agents were evaluated using the GENIUS (Generic Environment for Negotiation Programs) simulator under the Alternating Offers Protocol (AOP). The researchers tested the model across four distinct domains with varying sizes and levels of opposition:
- Grocery: $10^3$ outcomes, Low opposition.
- Thompson: $10^3$ outcomes, High opposition.
- Car: $10^4$ outcomes, Low opposition.
- EnergySmall_A: $10^4$ outcomes, High opposition.
MiPN was compared against a Baseline (average of nine heuristic agents) and VeNAS (the previous RL-based benchmark).
Key Results
The experimental results highlight that MiPN significantly outperforms previous models as domain complexity increases. While Q-learning-based approaches like VeNAS degrade in larger spaces, MiPN maintains high utility scores across diverse scenarios.
As shown in the table, MiPN consistently achieved higher utility than the baseline heuristic agents and VeNAS in most test cases. For instance, in the "Car" domain against a "Boulware" opponent, MiPN achieved a utility of 0.974, while VeNAS only managed 0.570. In many scenarios, MiPN reached a utility of 1.000, particularly in the Grocery and Car domains. The agent also demonstrated robustness, adapting its strategy against various opponent types, including time-dependent and behavior-dependent agents.
Discussion and Conclusion
The "divide and conquer" strategy employed by MiPN allows it to avoid the exponential complexity of the total outcome space. By calculating policy gradients for each issue independently, the agent learns to identify which issues are most important to its own utility function. This enables effective adaptive concession—making concessions on low-priority issues to reach high-utility agreements that the opponent is likely to accept.
Future work will focus on improving the generalization of MiPN to entirely new domains, developing more explicit opponent modeling to predict hidden utility functions, and extending this factorized approach to multi-party negotiation scenarios.
Summary updated