Automated Negotiation with Gaussian Process-based Utility Models

1 Introduction

Automated (agent-based) negotiation formalizes a wide range of interactions in multi-agent systems, covering topics such as HF trading [McGroarty et al., 2018], cloud computing [Sim, 2011], pervasive computing [Ramchurn et al., 2004], smart grids [Ketter et al., 2018], supply chain management [Wang et al., 2009]. In such systems, agents can successfully substitute humans in making complex decisions, provided that they have good knowledge of the user's goals [Kraus et al., 1995].

In many situations agents do not have access to all information required for taking optimal decisions. For instance, if negotiation takes place over multiple issues then quantifying the desirability of various outcomes requires the consideration of trade-offs. The combinatorial explosion in the number of potential outcomes makes it intractable (too costly) for a user to determine and communicate all dependencies beforehand, while many of them could be also irrelevant since, for instance, they could be highly unattractive for the other negotiating party (which, in the sequel, will be called opponent).

∗An abridged version of this work was presented at AAMAS '19.

An important challenge in automated negotiation is designing agents which can efficiently strike a balance between negotiation and (user's) preference elicitation [Baarslag et al., 2017]. (PO)MDP models have been employed for both negotiation [Paruchuri et al., 2009] and preference elicitation [Boutilier, 2002; Chajewska et al., 2000], while preference elicitation models were further adapted to negotiation processes in which agents may elicit utility values by submitting queries to the user [Baarslag and Gerding, 2015; Mohammad and Nakadai, 2018]. In this paper, which extends the framework presented in [Leahu et al., 2019], we adopt a similar modeling paradigm, but have agents learn from comparative queries; thus not asking the user to quantify the desirability of a specific outcome, but to compare a pair of alternatives. Preference quantification is rarely available in practice - and even then may be inconsistent over time - [Kingsley and Brown, 2006], which motivates our choice of ordinal utility models, i.e. based on pair-wise comparisons.

A key ingredient in our modeling paradigm is defining suitable utility models, quantifying the preferences of both the user and the opponent for every possible negotiation outcome by means of (random) utility functions, with the randomness illustrating the underlying uncertainty. That is, in the absence of (full) knowledge of the user/opponent's preferences, the agent maintains quantitative beliefs over them, which are being updated, as new data emerges, through interactions with the user/opponent. Therefore, it is highly desirable that a utility model should be general (to account for a wide range of scenarios) and flexible (to allow easy integration of new data).

In this paper we propose a stochastic utility model, where the underlying randomness is formalized by a Gaussian Process (GP), which is integrated into a MDP negotiation framework. The use of GP's in Machine Learning has gained much popularity [Rasmussen and Williams, 2006] since GP's allow for a rather general treatment of random functions, compared to other models (e.g. linear with random slope coefficient). Moreover, the Laplace approximation of the Bayesian posterior distribution makes GP-based models flexible, as new data can be easily integrated by means of GP parameter updates. While the use of the GP's in formalizing uncertain preferences is well established [Chu and Ghahramani, 2005a; Chu and Ghahramani, 2005b], standard utility models (based on uncertain beliefs) for negotiating agents are still lacking. Filling this gap is one of the main contributions of this paper.

This paper furthers the state-of-the-art in the following directions: First, it extends the GP-based preference learning model [Chu and Ghahramani, 2005b] by allowing ties between alternatives; this is in contrast with the standard model which assumes that the user can always indicate a clear preference between any pair of alternatives. Secondly, we adapt the model to online learning, by deriving explicit sequential update rules which facilitate integration of new data in real time. Ultimately, we introduce a stochastic, inverse-rank utility model, mapping preferences into utility values in a natural way. The resulting utility mapping is a monotone transformation of a GP-like preference function (thus obeys essentially the same update rules), but unlike the preference function (which introduces subjective beliefs which can not be validated by user interactions) is data measurable, i.e. the randomness is completely (up to approximation errors) removed when full information on user preferences becomes available; this distinguishes our model from alternative GP-based utility models in preference elicitation [Bonilla et al., 2010].

We further integrate our utility model into a two-objective (belief) MDP model which combines negotiation actions with preference elicitation, resulting in a fairly general mathematical framework for automated negotiation with uncertain knowledge. Namely, a negotiating agent employs utility models (called henceforth user, resp. opponent model) for both parties involved in the negotiation process and performs successive interactions with the user (by means of comparative queries, incurring certain elicitation costs) and the opponent (deal offers), updating the two utility models accordingly; see Figure 1. While the user utility can be readily used to define rewards, the use of the opponent utility in formalizing its behavior requires, in general, further modeling assumptions.

To illustrate the use of our utility model, we consider a negotiating agent which, before taking any negotiation action (i.e. accepting or making a new offer), explores the user's preferences in order to reduce uncertainty around the utility values corresponding to the outcomes relevant for the negotiation. For a better insight into the decision mechanism, we choose a small-scale example for our numerical experiments.

Since our focus is on preference elicitation (rather than on negotiation), we shall assume that the agent employs a onestep look ahead negotiation strategy, thus aiming to maximize his immediate (one-step) expected reward. Our setup is somewhat similar to the ultimatum game [Zhong et al., 2002], which can be seen as the one-shot, final-offer version of the classic alternating offers protocol [Baarslag et al., 2015]. However, in our setting, the agents can have mutually non-exclusive objectives since arbitrary utilities over the outcome space are possible (e.g. single-peaked preferences), allowing for integrative negotiation scenarios where win-win agreements are possible [Kowalczyk and Bui, 2000].

2 ProblemFormulation

An agent conducts a negotiation on some user's behalf, in a sequential way, based on an offer/counter-offer protocol. Negotiation ends when either party accepts the other party's offer, resulting in some outcome-dependent rewards for each party. The space of all possible outcomes of the negotiation is denoted by X and is assumed that, initially, an agreementoffer y ∈ X (e.g. an outside option) is available to the agent.

In the absence of complete information, the agent maintains a belief µ formalizing the user's utility and a belief η governing the opponent's behavior. A first challenge for the agent is to decide whether to accept y, make an offer x ̸= y, or elicit some additional information (i.e. making a sequence of queries) from the user, in order to obtain a more accurate µ-belief, before taking any decision. Once the agent decides to negotiate (i.e. to make an offer x ̸= y), it can be either that the offer gets accepted, with some acceptance probability (calculated based on the current η-belief), yielding a suitable reward (the expected value of which is calculated based on the current µ-belief), or the offer is further negotiated by the opponent, resulting in a new agreement-offer z and a suitable updated opponent belief. Alternatively, at any time, the agent may submit a user-query to update its (user) belief. In this context, the problem we tackle is devising a judicious rule for deciding whether to elicit more information (and, if yes, which information) before continuing negotiation.

In the above paradigm, negotiation actions alternate with preference elicitation actions (queries). By an elicitation policy we mean a sequence π = (q1, . . . , qn), with n ≥ 0, of queries made during an elicitation cycle, i.e. between two successive negotiation actions. To each query, a 'bother' cost γ(q), in the form of a discount factor, is associated. Since our focus is on learning preferences (rather than elaborating optimal negotiation strategies, which requires a complex opponent behavior modeling and assumptions), we aim to derive efficient elicitation policies maximizing the immediate expected reward R(x|y, µ, η) obtained by the agent by making offer x in state (y, µ, η) (to be understood as 'accept y' if x = y). To be more specific, we define

where U denotes the user's utility function under belief µ and P denotes the opponent's acceptance probability under belief η. We further define the maximal immediate expected reward

Finally, defining the state-value function

where γ[π] := γ(q1) · . . . · γ(qn) denotes the cost of the policy π = (q1, . . . , qn) and [µ|π] denotes the random belief obtained by updating µ w.r.t. the (predicted) outcomes of π, an optimal elicitation policy is any maximizer in (3). An optimal elicitation cycle ends when a state (y, µ, η), satisfying

is reached and an offer maximizing (1) is made; note the the above equality can be regarded as a stopping condition.

3 Stochastic UtilityModels

A utility belief on X is a Gaussian probability law µ on RX, specified by a mean and a covariance function, µ : X -→ R resp. k : X2 -→ R. A sample from µ is a random function G : X -→ R, which will be called a Gaussian Process (GP). Utility beliefs are used to define utility models (random utility functions) which are updated based on pairwise comparisons.

3.1 Utility Belief Update

In instance preference learning [Chu and Ghahramani, 2005b], data is available in the form

• (+) u ≺ v, meaning that "v is (strictly) preferred to u";

(∼) u ∼ v, meaning "no preference between u and v",

• (-) u ≻ v, meaning that "u is (strictly) preferred to v";

for some arbitrary pair q := (u, v) ∈ X2 , with u ̸= v.

For a pair (u, v), the likelihood P{u ≺ v|G} is given by

Given a utility belief µ (specified by parameters µ and k) and some outcome ϵ = u ▷◁ v, where ▷◁ ∈ {≺,∼,≻}, of the pair-wise comparison (u, v), we denote by [µ|ϵ] the updated belief, which we define as the Laplace approximation of the Bayesian posterior of µ, conditioned on ϵ. To derive the mean/covariation functions ¯µϵ, resp. ¯kϵ of the updated belief [µ|ϵ], we use an adaptation of the standard method [Chu and Ghahramani, 2005b] to our setup, i.e. we adjust the likelihood function to include ties between alternatives. We do so by introducing a new (precision) parameter δ ≥ 0 and interpreting the outcome u ∼ v as |G(v) - G(u)| ≤ δ.

where Φ denotes the standard Gaussian c.d.f. and ς is a model parameter accounting for the uncertainty in the user answer; note that, for δ = 0 one recovers the standard model in [Chu and Ghahramani, 2005b]. Letting further

Mq := µ(v) -µ(u), Vq := k(v, v) -2k(u, v) +k(u, u), the predictive distribution of the query outcomes is given by

Let f(b) := logΦ((b - δ)/ς), for b ∈ R, and β(M, V ), for M ∈ R, V ≥ 0, denote the unique solution of

Then the updated belief [µ|ϵ] is specified by

respectively

where Bϵ ∈ R and Cϵ > 0 are defined as follows:

• for ϵ = (∼) we have
• for ϵ = (±) we have Bϵ = ±f ′ (β(±Mq, Vq)) , Cϵ = -f ′′ (β(±Mq, Vq)) ;

This concludes the belief update rules.

3.2 Ranking-based UtilityModels

A utility model with underlying utility belief formalized by a GP G, is a random (utility) function U : X -→ R satisfying U(x) ≤ U(z) if and only if G(x) ≤ G(z). The monotonicity assumption ensures that ordinal data can be properly integrated in the belief update process; see Section 3.1.

In this paper, we propose the inverse-rank utility model

that is, U(x) denotes the (random) number of negotiation outcomes whose G-value does not exceed that of x. U(x) is an integer between 1 and ℵ := #X, representing the ranking of G(x) within the increasing sequence of G-values, i.e.

Next to its intuitive domain interpretation (utility as number of outcomes that are not preferred), the inverse-rank utility model (8) has two attractive formal properties, which set it apart from alternative models, e.g. U = G or U = exp(G). First, the utility values remain in some fixed interval. Secondly, our model is data-measurable, in the sense that is built from observable variables only; put differently, a full knowledge of user's preferences makes the model deterministic.

Furthermore, under the utility belief µ = (µ, k), the expected utility of some particular outcome x will be given by

note, however, that the expected utility values are not integers anymore, but still remain in the (continuous) range [0, ℵ].

In the context of negotiation, assume that the agent has an offer x on the table, which is accepted with probability P(x), or negotiated (hoping for a better deal) with remaining probability. Provided that the agent has no insight into the future negotiation process, a future agreement can be regarded as a uniform sample from the negotiation space; thus the chance of not improving the current deal x is U(x)/ℵ, which provides a natural model for the acceptance probability P(x) (if interpreted as the probability of not getting a better deal).

4 Belief MDP with Stochastic UtilityModels

In the context of Section 2, let µ = (µ, k), η = (η, ℓ) denote user's, resp. opponent's, utility beliefs; we denote by G, resp. H, the corresponding GP-samples. In particular, for a specific agreement x ∈ X, the user's utility is given by

and the corresponding opponent's acceptance probability by

where ≈ means equality up to some multiplicative constant.

Assuming stochastic independence between the user's and the opponent's utility beliefs, µ and η, it follows that

where, in accordance with (9), it holds that

respectively

The above formulas express the numerical elements required in (1), (2), (3) by means of the agent's current beliefs.

To describe the MDP dynamics, we first note that the MDP states can be classified into transient and terminal states, with rewards being obtained only upon reaching a terminal state. Furthermore, given a transient state (y, µ, η), the set of available actions consists of all possible user queries, formalized as pairs q = (u, v), and negotiation actions (offers) x ∈ X (recall that y means 'accept'). Making a query q = (u, v) results in an outcome ϵ, which can be either (+) u ≺ v, (-) u ≻ v or (∼) u ∼ v, having predictive distribution specified by (4). The agent moves in the new transient state (y, [µ|ϵ], η), where [µ|ϵ] is specified by (6)-(7). On the other hand, the agent can either accept y, expecting the reward U(y), or make the offer x ̸= y expecting one of the following scenarios:

• (ii) x is negotiated by the opponent, resulting in the agent receiving a (counter-) offer z ̸= x.
• (i) x is accepted by the opponent, with probability P(x), resulting in a reward U(x);

Acceptance (by either agent or opponent) results in terminal states, where belief updates are not necessary. On the other hand, should the opponent decide to negotiate the agent's offer - case (ii) - the agent moves into the new (transient) state (z, µ, [η|x ≺ z]), inferring that z is preferred (by the opponent) to x. The belief MDP dynamics are illustrated in Figure 2, which is the particularization of Figure 1.

Remark: The probability of receiving some counter-offer z depends on the opponent's reasoning and requires further modeling assumptions for the agent. However, for the problem formulated in Section 2, this probability (of the opponent making a specific counter-offer) is not relevant, as the agent does not optimize his actions w.r.t. future opponent offers; it is only the acceptance probability of x which matters.

Algorithm 1 decides between elicitation and negotiation

Input: [(y, µ, η); L]

Parameter: query cost-function γ

Output: myopic action "Action"

• 1: ϱ ←R(y, µ, η); // reward based on current belief
• 3: for {any relevant query q /∈ L} do
• 2: Act ← argmaxxR(x|y, µ, η);
• 4: if {ϱ < Q(y, µ, η; q)} then
• 6: Act ← q; // make q a candidate for the next query
• 5: ϱ ← Q(y, µ, η; q);
• 7: end if
• 8: end for
• 9: return Act

5 The Myopic Elicitation Strategy

We devise an algorithm that determines an optimal elicitation cycle w.r.t. a myopic look ahead strategy. Namely, the queries are decided in a sequential manner, by evaluating at each step whether to negotiate (accept y or make an offer) or make a new query, which, by reducing the utility uncertainty around the points of interest, could possibly increase the immediate expected reward obtained by future negotiation actions.

Formally, our algorithm evaluates

for all queries q := (u, v) and outcomes ϵ = u ▷◁ v of q, where the expectation is calculated w.r.t. the predictive distribution (4) of the random preference ▷◁ =≺,∼,≻, based on the current µ-belief. Furthermore, it decides as follows:

• if the stopping condition

is fulfilled, then the elicitation cycle ends with the offer

• else, a query q∗ := argmaxq Q(y, µ, η; q) is made.

Algorithm 1 illustrates the myopic (one-step ahead) exploration of all relevant (in some sense to be specified) queries and decides whether extra elicitation is profitable; if yes, it also returns an optimal query. To reduce the complexity of the exploration process, the agent maintains a list L of pairwise preferences based on the information elicited so far, i.e. preferences either confirmed directly by the user (as answers to queries) or inferred from known preferences by transitivity (assuming user's preference consistency). The queries which do not have a certain answer based on the ordinal data in L are called relevant and the list is being updated after each answered query, to ensure that the search space for new relevant queries decreases after each user interaction.

By iterating the decision rule formalized by Algorithm 1 until condition (11) is fulfilled, one obtains a myopic elicitation cycle; see Algorithm 2. Note that, restricting the maximization to relevant queries (only) ensures convergence.

Remark: Our algorithm performs only a one-step ahead search, corresponding to maximizing in (3) w.r.t. policies (interpreted as sequences of queries) of length n = 1. Possibly more accurate solutions can be obtained by extending the optimization range to multiple-step search.

Algorithm 2 generates a myopic elicitation cycle Input: [(y, µ, η); L] Parameter: query cost-function γ Output: the next negotiation action 1: Act ←Query. 2: while {Act = Query} do 3: if {Action[(y, µ, η); L] ̸=Offer} then 4: q ← Action[(y, µ, η); L] 5: make query q and obtain outcome ϵ 6: µ ← [µ|ϵ]; // update belief µ cf. (6) and (7) 7: L← [L; ϵ]; // update the list L 8: else 9: Act ←Offer; 10: end if 11: end while 12: return x∗ (y, µ, η) given by (12);

6 Experimental Setup

To illustrate our approach, we perform an experimental comparison of the myopic elicitation strategy formalized by Algorithm 1 against a 'randomized' elicitation strategy, in which the agent randomly generates a sequence of relevant queries and then makes the optimal negotiation offer (12), based on the resulting updated belief (given the corresponding query outcomes). We shall achieve that by simulating 'parallel' negotiation processes, in which the two elicitation strategies are confronted with the same opponent behavior.

To implement our experimental setup, we assume the existence of 'ground truth' utility functions φ and ψ, quantifying the preferences for the agent, resp. opponent, and perform simulations, based on the following assumptions:

• the answer to a query (u, v) is generated in accordance with the utility φ, by comparing φ(u) with φ(v);
• upon receiving an offer x, the opponent either accepts it, with a probability proportional to ψ(x), or negotiates the offer, by making a random counter-offer z, satisfying ψ(x) < ψ(z), with probability proportional to ψ(z), i.e.

Remark: The functions φ and ψ satisfy the equation

where ≺ denotes the opponent's preference ordering.

that is, both can be recovered from a full set of ordinal data.

For the 'random' strategy, we use a parameter p ∈ (0, 1) formalizing the probability of making a new query. The agent generates an elicitation cycle, as follows: at each step decides with probability p to make a new (relevant) query and with probability (1-p) to stop elicitation and take the best negotiation action (12) based on the current belief; should it decide to elicit more information, it will randomly select a new query from the remaining relevant ones.

Remark: While myopic elicitation (described in Section 5) is, essentially, an 'exploitation' strategy, random elicitation can be regarded as a fully 'exploration' strategy.

Finally, we assume that all queries are equally costly, with each query inducing a discount γ ∈ (0, 1] on the final reward and we compare the two strategies with respect to the 'true' expected reward (discounted by the total elicitation costs); that is, for each of the two scenarios we calculate the expected discounted (true) utility E[γ ν φ(ω)] obtained by the agent, where ω denotes the negotiation outcome, ν denotes the total number of queries made during the negotiation process and the expectation accounts for the random opponent actions (and for the randomly generated elicitation cycles).

7 Tables and Numerical Results

For our experiments, we choose a negotiation space consisting of 10 items/options, labeled 0, 1, . . . , 9 and use the ordinal utility functions φ (for the user) and ψ (for the opponent) displayed in Table 1. The agent starts the negotiation, having the outside option y = 0 and 'flat' utility beliefs over both utility functions, i.e. GP's with µ, η = 0. In addition, we assume a distance-based correlation structure k(x, z) = κ(|x - z|), with κ(0) = 0.5, κ(1) = 0.3, κ(2) = 0.2, κ(3) = 0.1 and κ = 0 otherwise; that is, closer items are stronger (positively) correlated. Such a model is appropriate for negotiations over items which can be organized in a spectrum, e.g. colors.

Our numerical experiments are summarized in Table 2, illustrating the dependence, w.r.t. the query cost-factor γ, of the (expected) discounted utility "Util" and the number of queries "Que", for both the myopic and random elicitation approaches, based on averages over 100 (myopic), respectively 400 (random), simulations of the negotiation process.

We note that the myopic approach clearly outperforms the random one in terms of discounted expected utility, scoring higher for any cost-factor γ. A graphical head-to-head comparison of the two strategies is provided in Figure 4.

Remark: The number of simulation runs based on which the metrics of interest are calculated does only influence the accuracy (variance) of the estimates in Table 2; thus the different numbers of simulation runs for the two approaches do not induce any bias in the above head-to-head comparison.

In the myopic approach, both the expected discounted utility and the query number are increasing in the cost-factor γ, as expected, reaching the maximal values of 7.66, resp. 10.03, in the cost-free scenario γ = 1; see Figure 3. The intuition is that, as the elicitation cost decreases (γ increases), the agent will elicit (on average) more information at the same costs, learning more accurately the user's preferences, which will result in better negotiation outcomes. On the other hand, in the random approach, the discounted utility is still monotone, but the number of queries is (roughly) constant since, in this case, the elicitation strategy does not account for the costfactor γ (but only on p), whereas the discount (still) does.

Finally, note that, with complete knowledge of both user's and opponent's utilities, the myopic action for the agent is to make offer 6, maximizing R(x|0) = φ(x)ψ(x)/10. Since ψ(6) = 9, the opponent will accept it (with probability 0.9) or will propose item 5, since ψ(5) = 10. The myopic action for the agent is again 6 (which brings an immediate expected reward R(6|5) = 7.2 > 6 = φ(5) and the agent, resp. the opponent, will keep repeating offers 6, resp. 5, until the opponent accepts item 6; this will happen quite fast, after an expected number of 1/9 iterations. Therefore, under complete knowledge of φ and ψ, following the myopic negotiation strategy, the agent obtains (with probability 1) an agreement over item 6, having the utility value φ(6) = 8, which is an upper bound on what it can achieve using the myopic negotiation strategy. The outcome 6 coincides, in this case, with the maximizer of the 'combined' utility φ · ψ, which has the following interpretation: it is the outcome which maximizes the number of pairs of negotiation outcomes which are simultaneously not better for the user and opponent, respectively.

Remark: The gap between the cost-free expected utility 7.66 (obtained for γ = 1) and the upper limit 8 is motivated by the lack of information about the opponent's preferences. Indeed, although the agent can make an unlimited number of cost-free queries, presumably learning the exact user utility function, the lack of information on the opponent's utility function could end up in having sub-optimal offers accepted by the opponent, thus resulting in a lower (expected) utility.

8 Conclusion and Future Research Directions

In this paper, we consider an agent negotiating on behalf of a user, using a GP-based adaptive model to formalize the uncertain information on both the user and the opponent's preferences. We formulate a myopically optimal elicitation algorithm that computes the best query to pose to the user in order to achieve a good negotiation outcome while minimizing elicitation costs. Through numerical experiments we find that our myopic elicitation strategy performs clearly better than a baseline strategy which randomly decides to pose queries.

Our algorithm performs a one-step look-ahead search to decide on the next negotiation action. Going beyond the myopic approach would require a more demanding optimization process, but also a more complex modeling paradigm, which, in order to account for the opponent's future actions, requires more than an acceptance probability (predictive) model.

While, for illustrative purposes, our numerical experiments are performed on a one-dimensional negotiation space with merely 10 items, our approach carries over to far more complex negotiation spaces. In terms of complexity, computation of (expected) utility is quadratic and is required after each belief update. For a more efficient approach, the computation can be formalized as a matrix-vector multiplication, for which parallelization methods offer attractive alternatives. Furthermore, our GP-based utility model can be adapted to multiissue negotiation spaces, where monotonicity properties and various types of dependency between the issues and attributes (which typically reduce computational complexity) can be included through appropriate tuning of the covariance function.

Given our elicitation model of preference judgments, the queries are homogeneous (in type and cost structure). However, our model admits generalizations to different types of queries, with type and/or timing dependent costs.

Based on the above considerations, we are confident that the modelling paradigm proposed in this paper opens up a wide range of promising avenues for extending our approach to more complex (automated) negotiation frameworks characterized by (user) preference uncertainty.

Acknowledgments

This research has received funding from the ERA-Net Smart Energy Systems' focus initiative Smart Grids Plus, within the European Union's Horizon 2020 research and innovation programme, under grant No. 646039, and through the Veni research programme of the Dutch Organisation for Scientific Research (NWO), under the project No. 639.021.751.