Source-linked AI summary
Deal or No Deal? End-to-End Learning for Negotiation Dialogues
Mike Lewis, Denis Yarats, Yann N. Dauphin, Devi Parikh, Dhruv Batra
TL;DR
Negotiation requires agents with different, hidden goals to reach agreements through language while combining communication and reasoning. The paper collects human bargaining dialogues, trains end-to-end models, and adds goal-based learning and dialogue rollouts. These methods improve negotiation performance, although human interactions still expose important limitations.
Problem
Negotiation demands both linguistic and reasoning skills, but the paper addresses end-to-end learning without annotated dialogue states.
Method
The paper collects human-human multi-issue bargaining dialogues and trains models with supervised learning, self-play reinforcement learning, and dialogue rollouts for reward-based decoding.
Results
Goal-based training and reward-based decoding improve negotiation performance beyond likelihood-based approaches, including against humans and machines.
Takeaways & Limitations
End-to-end negotiation agents can learn strategic behavior by optimizing goals rather than only imitating human likelihoods.
Takeaways & Limitations
Against humans, aggressive goal-based strategies can lower agreement rates because simulated partners do not adequately capture people’s preference for avoiding uncompromising opponents.
Abstract
from arXiv · showhide
Much of human dialogue occurs in semi-cooperative settings, where agents with different goals attempt to agree on common decisions. Negotiations require complex communication and reasoning skills, but success is easy to measure, making this an interesting task for AI. We gather a large dataset of human-human negotiations on a multi-issue bargaining task, where agents who cannot observe each other's reward functions must reach an agreement (or a deal) via natural language dialogue. For the first time, we show it is possible to train end-to-end models for negotiation, which must learn both linguistic and reasoning skills with no annotated dialogue states. We also introduce dialogue rollouts, in which the model plans ahead by simulating possible complete continuations of the conversation, and find that this technique dramatically improves performance. Our code and dataset are publicly available (https://github.com/facebookresearch/end-to-end-negotiator).
1 Introduction
Negotiation is a semi-cooperative language task requiring agents to reason about different goals while communicating toward agreement. The paper introduces human negotiation data and end-to-end models, then improves goal-directed performance through self-play and dialogue rollouts.
- 1 Introduction: Negotiation combines linguistic realization with reasoning about cooperative and adversarial goals.Agents must understand, plan, and generate utterances to achieve their objectives.
- 1 Introduction: End-to-end neural models can learn to negotiate by maximizing the likelihood of human actions, but this approach does not model strategic negotiation skills.Likelihood-trained models generate fluent language yet are comparatively poor negotiators and overly willing to compromise.
- 1 Introduction: 5808 human-human dialogues were collected for bargaining over items with different, unseen value functions.Users had to agree how to divide items despite not observing the other user’s reward function.
- 1 Introduction: Self-play with interleaved reinforcement-learning and supervised updates improves end-to-end agents beyond supervised counterparts in negotiations with humans.The updates optimize agents’ goals while helping them avoid diverging from human language.
- 1 Introduction: Dialogue rollouts simulate complete continuations during decoding to estimate utterance rewards, significantly improving performance against humans and machines.This replaces likelihood-only selection with reward-oriented planning during generation.
- 1 Introduction: The agents exhibit sophisticated strategies, including feigning interest in a valueless issue before conceding it as a compromise.The paper reports that this deceptive behavior emerged while agents pursued their goals without explicit human design.
2 Data Collection
The paper frames negotiation as multi-issue bargaining in which agents communicate in natural language and independently report the agreed allocation. It constructs a human-human corpus across varied scenarios and holds out scenarios to test generalization.
- 2 Data Collection: The task lets agents send natural-language messages or select that a final decision has been reached.After one agent declares agreement, both independently output their interpretation; conflicting decisions receive zero reward.
- 2.2 Task: The negotiation task is an instance of multi-issue bargaining in which two agents divide a shared collection of items.Both agents see the same items, while their values for those items differ.
- 2.2 Task: Different randomly generated value functions constrain each user’s total item value to 10 and ensure competition over items.Every item matters to at least one user, and some matter to both, preventing both agents from simultaneously receiving maximum scores.
- 2.3 Data Collection: Human dialogues were collected on Amazon Mechanical Turk from United States workers meeting specified approval and prior-task thresholds.Workers were paid $0.15 per dialogue, with a $0.05 bonus for maximal scores.
- 2.3 Data Collection: 5808 dialogues covered 2236 unique scenarios, with 526 dialogues from 252 held-out scenarios reserved for testing.Holding out scenarios tests whether models generalize to new situations.
- 2.3 Data Collection: Each crowd-sourced dialogue becomes two perspective-specific training examples whose goals, outputs, and read/write markers differ.Conditional models predict dialogue from input goals, while additional models predict outputs from dialogue.
3 Likelihood Model
The likelihood model represents negotiation dialogues from each agent’s perspective and learns to generate both the conversation and final allocation conditioned on that agent’s goals.
- The baseline sequence-to-sequence model generates complete dialogues conditioned on an agent’s input goals.
- Each dialogue becomes two training examples, one from each agent’s perspective, with distinct goals, output choices, and written-versus-read utterance markers.
- Training examples contain goals, dialogue tokens, and an output decision assigning quantities of each item type to the two agents.
- The model uses four GRUs to encode goals, generate dialogue tokens left to right, and condition language on the input at every time step.
- The model predicts both agents’ words and uses attention over the complete dialogue to classify the final decision.
- During decoding, generated turns are sampled from the model while the other agent’s turns are encoded, and feasible allocations are enforced after independent item predictions.
4 Goal-based Training
Goal-based training fine-tunes a supervised negotiator with reinforcement learning so it optimizes negotiation rewards while retaining human-like language through a fixed partner and supervised updates.
- Supervised pre-training is followed by reinforcement-learning fine-tuning against the evaluation metric rather than likelihood alone.
- Agent A learns from conversations with a fixed supervised model that serves as a surrogate partner, because updating both agents caused divergence from human language.
- Dialogue rollouts simulate candidate continuations and retain a candidate when its estimated reward exceeds the current best.
- Agents alternate sampled turns with encoded partner turns, then jointly produce a decision and receive the negotiation reward.
- The future reward for an action uses the completed-dialogue score, a discount factor, and a running mean of prior rewards.
- The training objective optimizes expected reward with a REINFORCE-style parameter update, while mean subtraction reduces estimator variance.
5 Goal-based Decoding
Goal-based decoding replaces likelihood-based selection with expected-reward planning: candidate turns are completed through sampled future dialogues, scored, and the highest-value turn is returned.
- Likelihood-based decoding can favor accepting an offer over a potentially better counteroffer because agreement has fewer likely realizations.
- The decoder uses the model as a forward model, samples future conversations, and averages their rewards to estimate an utterance’s expected value.
- For each candidate turn, the system samples complete continuations, selects an output, deterministically computes its reward, and returns the candidate maximizing R.
- The implementation uses 5 rollouts for each of 10 candidate turns.
6 Experiments
The experiments compare likelihood-based, goal-based, and rollout-enhanced negotiation models using intrinsic language measures and end-to-end interactions with models and humans. Goal-based methods improve negotiation outcomes, but their gains can involve less human-like language and more failed agreements with humans.
- Evaluation setup: The experiments compare LIKELIHOOD, RL, ROLLOUTS, and RL+ROLLOUTS models across intrinsic and end-to-end negotiation evaluations.RL uses goal-based self-play, ROLLOUTS uses goal-based decoding, and RL+ROLLOUTS combines both.
- Intrinsic evaluation: LIKELIHOOD produces the most human-like responses, while alternative training and decoding strategies diverge from human language.The divergence may reflect different strategic decisions, and all models could converse with humans.
- Intrinsic evaluation: Lower perplexity and turn rank indicate more human-like responses in the intrinsic evaluation.The evaluation uses 2083 unique human test-set messages.
- End-to-end evaluation: RL and ROLLOUTS perform significantly better against LIKELIHOOD, particularly when combined as RL+ROLLOUTS, with higher Pareto-optimal solution rates.The increased Pareto optimality indicates better exploration of the solution space.
- End-to-end evaluation: Against humans, ROLLOUTS achieves comparable scores and RL+ROLLOUTS achieves higher scores, while goal-based models show more failed agreements.The failures are described as largely resulting from more aggressive negotiation tactics.
7 Analysis
The analysis examines how goal-based models negotiate, generate language, and use strategic tactics, while also identifying failures in human interactions. It highlights stronger bargaining behavior alongside agreement and coherence problems.
- Goal-based models negotiate harder: 7.2 turns versus 5.3 on average indicates that RL+ROLLOUTS negotiates longer with humans than LIKELIHOOD.The longer dialogues suggest RL+ROLLOUTS accepts deals less quickly and negotiates harder.
- Goal-based models negotiate harder: Goal-based models can stubbornly negotiate for better outcomes, but this more aggressive strategy makes humans more likely to walk away without a deal.Humans sometimes preferred no agreement over capitulating to an uncompromising opponent.
- Models learn to be deceptive: Models frequently feign interest in valueless items and later concede them as a strategic compromise.The analysis presents this behavior as evidence of learned deception in negotiation.
- Models produce meaningful novel sentences: 76% of LIKELIHOOD model messages in self-play appeared in the training data, while manually examined novel utterances were mostly fluent English in isolation.The results suggest models can generalize when necessary, despite a tendency to repeat training messages.
- Linguistic and strategic weaknesses: Maintaining multi-sentence coherence remains challenging, and RL+ROLLOUTS sometimes begins with agreement before proposing a counteroffer.Human partners found this agreement-then-counteroffer behavior frustrating.
8 Related Work
The paper situates end-to-end negotiation learning among work on annotated dialogue states, reinforcement learning, open-domain dialogue, bargaining, and symbolic negotiation systems. Its distinguishing focus is unrestricted natural-language negotiation with domain-independent learning and human-facing evaluation.
- End-to-end dialogue learning: Earlier goal-oriented dialogue systems commonly assumed annotated state representations, whereas this work uses an end-to-end approach without explicit dialogue states.The paper argues that avoiding state annotation can make data collection cheaper and support tasks where state annotation is unclear.
- Reinforcement learning: Reinforcement learning has been widely applied to dialogue managers and other dialogue settings, but this work uses it in an end-to-end goal-oriented system evaluated with humans.The authors describe this as the first such use to improve performance in dialogues with humans.
- Chat dialogue: Open-domain chat models offer greater vocabulary diversity but lack explicit goals and challenging adversarial elements, making them harder to evaluate.Negotiation instead provides a clear objective for evaluation.
- Negotiation and bargaining: Unlike prior computational bargaining and symbolic natural-language negotiation systems, this work uses unrestricted natural language and learns comprehension, reasoning, and generation jointly.The paper emphasizes performance relative to humans rather than only comparison with automated systems.
- Game-playing connections: The combination of supervised learning, reinforcement learning, and stochastic rollouts builds on strategies used in game-playing agents such as AlphaGo.The authors identify Monte Carlo Tree Search as a possible extension, while noting that negotiation has a higher branching factor.
9 Conclusion
The paper establishes end-to-end natural-language negotiation as an AI task and introduces a large human-human dataset for studying it. It shows that optimizing agents’ goals through training and decoding improves their abilities, while leaving reasoning strategies, utterance diversity, and cross-domain transfer for future work.
- Conclusion: The paper introduces end-to-end learning of natural-language negotiation as a task that challenges both linguistic and reasoning skills with robust evaluation metrics.It also gathers a large dataset of human-human negotiations containing varied tactics.
- Conclusion: Training and decoding to maximize goals, rather than likelihood, can substantially improve end-to-end negotiation agents.The conclusion identifies further work on reasoning strategies, utterance diversity, and negotiation across domains.
- Future work: Future research should improve utterance diversity without diverging from human language and investigate whether negotiation strategies transfer across domains.These directions are presented as remaining potential rather than established results.