A Fairness-Driven Method for Learning Human-Compatible Negotiation Strategies (2024)

Abstract: Despite recent advancements in AI and NLP, negotiation remains a difficult domain for AI agents. Traditional game theoretic approaches that have worked well for two-player zero-sum games struggle in the context of negotiation due to their inability to learn human-compatible strategies. On the other hand, approaches that only use human data tend to be domain-specific and lack the theoretical guarantees provided by strategies grounded in game theory. Motivated by the notion of fairness as a criterion for optimality in general sum games, we propose a negotiation framework called FDHC which incorporates fairness into both the reward design and search to learn human-compatible negotiation strategies. Our method includes a novel, RL+search technique called LGM-Zero which leverages a pre-trained language model to retrieve human-compatible offers from large action spaces. Our results show that our method is able to achieve more egalitarian negotiation outcomes and improve negotiation quality.

## introduction recent advancements in ai and nlp have led researchers to develop techniques to build autonomous agents which can achieve human-level performance in bargaining games such as deal-orno-deal @xcite . these techniques can be separated into two broad categories: game theoretic approaches and data driven approaches. game theoretic approaches to negotiation attempt to build negotiation agents without observing any human data. this class of algorithms is typically applied to two-player zero-sum games which do not require agents to learn human-compatible strategies in order to be successful @xcite @xcite . however, other classes of games such as negotiation require cooperation with humans in order to be successful @xcite . as a result, traditional game theoretic methods have failed to achieve quality performance in the realm of negotiation @xcite . data driven approaches to negotiation learn a human-like strategy directly using data on a specific negotiation domain @xcite @xcite . unfortunately, collecting human data is expensive and the strategies in the data may not effectively generalize to other negotiation domains. furthermore, these methods lack the desirable properties that game theoretic methods offer such as controllability. we propose an approach which bridges game theoretic and data driven approaches called fairness-driven human-compatible (fdhc) bargaining. this method is designed to target egalitarian outcomes, specifically the egalitarian bargaining solution (ebs), which we use as a formal notion of fairness @xcite . we target fair outcomes as prior work has shown that fairness is a key component of human strategies and has also served as a useful notion of optimality in general-sum repeated games @xcite @xcite . our fairness-targeting strategy is learned with a novel llm-guided monte carlo tree search with zero domain specific training data (lgm-zero). lgm-zero leverages the reasoning capabilities of llm models @xcite to extract human-like negotiation offers from large action spaces without the need to collect additional human data. a value model trained via self-play then selects the best offer that the llm proposes. the llm and value model are used to guide a monte carlo tree search (mcts) towards the desired outcome given by fdhc (figure 1 ). we say that an action/strategy is "humancompatible" if a human would take a similar action or apply a similar strategy if placed in the same scenario. for example, in a situation where participants are negotiating over an item worth thousands of dollars, it would not be human-compatible for our model to offer a price down to the granularity of individual cents. since humans tend not to do that when negotiating over items worth such large amounts. however such an offer would be perfectly valid from a game theoretic standpoint. we use the terms human-like and human-compatible interchangeably. we implement our method on a common negotiation exercise used in business classes where two students bargain over a used car. we train a model to play as the seller in this scenario. both the buyer and seller are given private reservation prices for the car that they cannot go beyond during the negotiation. for example, suppose the buyer can't buy the car for above @xmath010k. the goal of our method is to reach an agreement at the ebs solution for the game, which in this case corresponds to the midpoint between the two reservation prices ($10,500 in the example). while we implement our method for this specific exercise, our approach generalizes to any negotiation setting that can be modeled as a nash bargaining game. this encompasses any game involving surplus division, including multi-party and multi-issue negotiations. our final model uses a modular design where negotiation acts are selected according to the fdhc framework. strategies are then realized in natural language using a llm such as gpt-3.5 or @xcite . our contributions can be summarized as follows: lgm-zero which utilizes a llm and value network to extract human-compatible offers from large action spaces. ## background the nash bargaining game is a game in which two or more players must divide a surplus between themselves. in the used car example given previously, the surplus would be the difference between the buyer and seller's reservation prices. we use the term extensive form nash bargaining game to refer to a game in which players can propose divisions of the surplus over the course of a series of time steps. a nash equilibrium is a game state in which no player can benefit from a unilateral change in strategy. bargaining theory makes use of axioms which are rules that describe properties that a bargaining outcome satisfies @xcite . we make use of the following axioms when analysing the theoretical properties of our method. the axiom of symmetry says that if the players in the bargaining game are indistinguishable based on the description of the game, then they should all receive the same payoff. a weak pareto optimal solution is one where any change to the outcome will make at least one party no better off. strong monotonicity states that any increase in the amount of surplus being bargained over should benefit all players involved in the negotiation. formal definitions can be found in appendix a. surplus division is the process of dividing some commodity (often money) among a group of people. a utility function measures the welfare or satisfaction of a negotiator as a function of the amount of surplus they receive. a disagreement payoff is the amount of utility a negotiator receives if the negotiators do not reach an agreement. a reservation price is the minimum amount a seller is willing to sell an item for. the converse holds from the buyer's perspective. this term is specific to single-issue negotiation. action space refers to the set of all valid actions available to an agent as it interacts with an environment. in the context of negotiation, this is the set of actions available to participants in a negotiation. a value network is neural network that takes in a game state and outputs a scalar representing the quality of the state. ## related work prior work in the field of negotiation has typically been centered on leveraging human data to learn negotiation strategies. these methods involve collecting human-human dialogues for negotiation exercises such as craigslist bargaining @xcite or deal-or-no-deal @xcite . this data can then be used to perform supervised learning or offline reinforcement learning on a negotiation model @xcite . more recent work has focused on examining and enhancing the negotiation capabilities of llms @xcite @xcite . these methods use prompting to create negotiation agents and rely on the zeroshot/few-shot capabilities of llms to negotiate. data driven methods for negotiation are able to learn human-like negotiation strategies as they directly leverage human data. however they are often overly tailored to one particular domain and have a difficult time generalizing to other scenarios. furthermore, data driven strategies lack theoretical guarantees such as convergence to a nash equilibrium is which is a desirable attribute for any negotiation strategy. methods grounded in game theory are able to provide the theoretical guarantees that data driven methods lack. as a result they are much more controllable and adapt better to different domains as no additional data collection is needed for training. however, training with no human involvement often results in strategies which are incompatible with human play @xcite . this has limited work in the area primarily to two-player zero-sum games such as chess where human-compatibility is not needed to ensure robust play @xcite . these methods are designed to ensure convergence to a nash equilibrium, which does not necessarily result in a human-compatible strategy (section 5). the little work that has attempted to apply game theoretic methods to the negotiation domain tends to ignore the dialogue aspect of negotiation, considering it to be "cheap talk" @xcite . while the strategic aspect of negotiation can be modeled independently of dialogue, dialogue style has been shown to have a measurable effect on negotiation outcomes @xcite . our method is designed to provide theoretical guarantees similar to game theoretic methods while maintaining human-compatibility of data-driven methods by leveraging the reasoning capabilities of llms. ## method in this section, we describe the fdhc framework which prioritizes egalitarian outcomes. we also describe lgm-zero, which uses a value model trained with self-play and language model as a policy network. finally, we outline how we implement our setup for single-issue distributive bargaining. ## theoretical analysis in this section we analyse the theoretical properties of the fdhc framework. our analysis assumes that, when needed, we can manipulate our llm policy so that one of the offers it outputs is equivalent to the ebs. we can ensure that our framework will result in a nash equilibrium under fairly mild assumptions. we need to assume that the bargaining game is conducted during a finite number of time steps and that the number of steps is known to both players. this gives us the result in theorem 1. theorem 1. let t n denote the fdhc's final turn in the negotiation, let α denote the outcome proposed at t n-1 , and let ebs(x) denote the ebs value for some outcome x. setting fdhc's estimate of @xmath1, ebs(d)) at t n will result in a nash equilibrium outcome. the proof for this result is straightforward and is presented in appendix b. what this theorem says is that we can adjust our surplus estimate so that at its final turn, fdhc will either concede all of the surplus to its opponent(s) or accept the opponents' offer, so long as the offer is larger than its disagreement payoff. this strategy will ensure that the negotiation ends in a deal that splits the entire surplus if one is feasible. since any deal which splits the whole surplus results in a nash equilibrium (appendix b), our method will give a nash equilibrium outcome. this result also demonstrates that convergence to a nash equilibrium alone is not enough to ensure a robust negotiation agent. however, this does give our agent a baseline level of quality as it means that we are guaranteed to reach a deal if one is feasible. this is in contrast to data-driven methods which provide no such guarantees and have been empirically shown to give inefficient negotiation outcomes @xcite . we consider a negotiation agent to be robust if it can perform well against a variety of strategies. under stronger assumptions, we can guarantee that fdhc will converge to the ebs in expectation. first, we need to assume that both fdhc and the other negotiators have a method to obtain an unbiased estimate of the true surplus value. we also need to make some assumptions about the bargaining outcome induced by our opponents, specifically we make use of the bargaining axioms given in section 2. theorem 2. let f (s, d) denote the bargaining outcome targeted by fdhc's opponents. if f (s, d) satisfies the axioms of symmetry, weak pareto optimality, and strong monotonicity then the expected outcome of the nash bargaining game will be e(s, d). our proof of this theorem follows @xcite and is presented in appendix b. ## experiments we test the effectiveness of our method using both automatic and human evaluations. our results show that our method is able to generate fairer outcomes than existing negotiation baselines. our human evaluation also shows that our method improves perceived negotiation quality while maintaining the same level of human-like negotiation as gpt-4. ## conclusion and future work we presented a novel framework for building human-compatible negotiation agents called fdhc. our framework uses fairness as a notion of optimality along with a novel rl+search method called lgm-zero to learn a human-like negotiation strategy. our automatic and human evaluations show that our method is able to achieve more egalitarian outcomes compared to several baselines. our human evaluation also shows that our method is able to improve negotiation quality over the gpt-4 baseline while being similarly human-like despite using gpt-3.5 as its base model. an interesting direction of future work is to explore the use of alternate solutions to the nash bargaining game. these include solutions such as the nash bargaining solution @xcite or the kalai-smorodinsky bargaining solution @xcite . while our framework is designed to maximize convergence to the ebs, we can easily adjust it to target any feasible outcome.