VeNAS: Versatile Negotiating Agent Strategy via Deep Reinforcement Learning (Student Abstract)

Toki Takahashi, Ryota Higa, Katsuhide Fujita, Shinji NakadaiAAAI 2022 · DOI

Abstract

Automated negotiation requires agents to reach agreements on multiple issues to maximize utility. Traditional modular approaches rely on hand-crafted heuristics for bidding and acceptance, which often lack flexibility. This paper introduces VeNAS, an end-to-end negotiating agent that utilizes Deep Reinforcement Learning (DRL) to learn a comprehensive strategy. Evaluated on the GENIUS platform, VeNAS demonstrates superior performance in small-to-medium domains and remains competitive with past competition champions in complex scenarios.

Introduction

Bilateral multi-issue negotiation is a cornerstone of multi-agent systems, where agents must balance their own preferences against the need to reach a consensus. Historically, agents have been built using a modular architecture: one module for opponent modeling, another for bidding strategy, and a third for acceptance logic. While effective in specific contexts, these heuristic-based modules are often brittle when faced with unfamiliar opponents or shifting environments.

VeNAS (Versatile Negotiating Agent Strategy) moves away from this modularity. By treating the negotiation process as a unified learning problem, the agent develops a strategy that encompasses both bidding and acceptance decisions within a single neural network policy.

Methods

The authors frame the negotiation as a Markov Decision Process (MDP), employing Double Deep Q-Learning (DDQN) to optimize the agent's policy.

The VeNAS architecture integrates bid vectorization and a deep neural network to map negotiation states to actions (Accept or Offer).

The agent's state space includes the history of exchanged bids, its own utility function, and the remaining time. The action space is comprehensive, allowing the agent to either select a specific bid to offer or accept the opponent's current proposal. As shown in the architecture diagram, a "Bid Vectorization" layer processes raw data before it enters the hidden layers of the network. The reward function is tied directly to the utility of the final agreement, with a penalty applied for failing to reach a deal before the deadline.

Experimental Setup

VeNAS was benchmarked using the GENIUS (General Negotiation Support System) platform across five domains of varying complexity:

  • Laptop (Small, Low Opposition)
  • ItexvsCypress (Medium, High Opposition)
  • IS_BT_Acquisition (Medium, Low Opposition)
  • Grocery (Large, Low Opposition)
  • Thompson (Large, High Opposition)

The agent faced nine distinct opponents, ranging from simple heuristic strategies like Boulware and TitForTat to sophisticated past ANAC champions such as Atlas3 and HardHeaded.

Key Results and Insights

The experimental results highlight the versatility of the DRL approach. In smaller domains like "Laptop," VeNAS achieved near-perfect utility scores, outperforming traditional baselines.

Performance comparison of VeNAS (VeN.) against baselines (Bas.) and DRBOA (DRB.) across various negotiation domains and opponent strategies.

As shown in the table above, VeNAS (VeN.) consistently matches or exceeds the performance of the baseline (Bas.) and the RL-based DRBOA (DRB.) in several categories. Notably, VeNAS reached a utility of 1.000 against most standard opponents in the Laptop and ItexvsCypress domains.

Key Insights: * End-to-End Learning: By including "Accept" as an action, the agent naturally learns the optimal timing for agreement without needing a separate acceptance module. * Robustness: VeNAS adapts to different bargaining styles—from conceders to hard-headed opponents—without requiring an explicit opponent model. * Scalability Challenges: While powerful, the agent faces a "curse of dimensionality." In larger domains (e.g., Thompson), the explosion of the action space makes it harder to find optimal strategies compared to agents with fixed-size state representations like DRBOA.

Conclusion

VeNAS demonstrates that a single DRL model can effectively replace complex, hand-crafted negotiation modules. While it excels in small and medium domains, its performance in large-scale domains is currently limited by the size of the action space. Future research will focus on state and action space reduction techniques, such as abstract bid representations, to enhance the agent's scalability and performance in high-opposition environments.

Summary updated

BibTeX
@inproceedings{takahashi2022venas,
  author = {Toki Takahashi and Ryota Higa and Katsuhide Fujita and Shinji Nakadai},
  title = {{VeNAS: Versatile Negotiating Agent Strategy via Deep Reinforcement Learning (Student Abstract)}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.1609/aaai.v36i11.21669},
}
Figure