Scalable Negotiating Agent Strategy via Multi-Issue Policy Network (Student Abstract)

Takumu Shimizu, Ryota Higa, Toki Takahashi, Katsuhide Fujita, Shinji NakadaiAAAI 2023 · DOI

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.

The architecture of the MiPN agent, showing the flow from environment state through the factorized policy network to action outputs.

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.

Utility performance of MiPN compared to Baseline (Bas.) and VeNAS (VeN.) across various domains and opponent strategies.

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

BibTeX
@inproceedings{shimizu2023scalable,
  author = {Takumu Shimizu and Ryota Higa and Toki Takahashi and Katsuhide Fujita and Shinji Nakadai},
  title = {{Scalable Negotiating Agent Strategy via Multi-Issue Policy Network (Student Abstract)}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.1609/aaai.v37i13.27023},
}
Figure