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 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.
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