The LOGIC Negotiation Model Carles Sierra Institut d"Investigacio en Intel.ligencia Artificial Spanish Scientific Research Council, UAB 08193 Bellaterra, Catalonia, Spain sierra@iiia.csic.es John Debenham Faculty of Information Technology University of Technology, Sydney NSW, Australia debenham@it.uts.edu.au ABSTRACT Successful negotiators prepare by determining their position along five dimensions: Legitimacy, Options, Goals, Independence, and Commitment, (LOGIC). We introduce a negotiation model based on these dimensions and on two primitive concepts: intimacy (degree of closeness) and balance (degree of fairness). The intimacy is a pair of matrices that evaluate both an agent"s contribution to the relationship and its opponent"s contribution each from an information view and from a utilitarian view across the five LOGIC dimensions. The balance is the difference between these matrices. A relationship strategy maintains a target intimacy for each relationship that an agent would like the relationship to move towards in future. The negotiation strategy maintains a set of Options that are in-line with the current intimacy level, and then tactics wrap the Options in argumentation with the aim of attaining a successful deal and manipulating the successive negotiation balances towards the target intimacy. Categories and Subject Descriptors I.2.11 [Artificial Intelligence]: Distributed Artificial Intelligence-Multiagent systems General Terms Theory 1. INTRODUCTION In this paper we propose a new negotiation model to deal with long term relationships that are founded on successive negotiation encounters. The model is grounded on results from business and psychological studies [1, 16, 9], and acknowledges that negotiation is an information exchange process as well as a utility exchange process [15, 14]. We believe that if agents are to succeed in real application domains they have to reconcile both views: informational and gametheoretical. Our aim is to model trading scenarios where agents represent their human principals, and thus we want their behaviour to be comprehensible by humans and to respect usual human negotiation procedures, whilst being consistent with, and somehow extending, game theoretical and information theoretical results. In this sense, agents are not just utility maximisers, but aim at building long lasting relationships with progressing levels of intimacy that determine what balance in information and resource sharing is acceptable to them. These two concepts, intimacy and balance are key in the model, and enable us to understand competitive and co-operative game theory as two particular theories of agent relationships (i.e. at different intimacy levels). These two theories are too specific and distinct to describe how a (business) relationship might grow because interactions have some aspects of these two extremes on a continuum in which, for example, agents reveal increasing amounts of private information as their intimacy grows. We don"t follow the "Co-Opetition" aproach [4] where co-operation and competition depend on the issue under negotiation, but instead we belief that the willingness to co-operate/compete affect all aspects in the negotiation process. Negotiation strategies can naturally be seen as procedures that select tactics used to attain a successful deal and to reach a target intimacy level. It is common in human settings to use tactics that compensate for unbalances in one dimension of a negotiation with unbalances in another dimension. In this sense, humans aim at a general sense of fairness in an interaction. In Section 2 we outline the aspects of human negotiation modelling that we cover in this work. Then, in Section 3 we introduce the negotiation language. Section 4 explains in outline the architecture and the concepts of intimacy and balance, and how they influence the negotiation. Section 5 contains a description of the different metrics used in the agent model including intimacy. Finally, Section 6 outlines how strategies and tactics use the LOGIC framework, intimacy and balance. 2. HUMAN NEGOTIATION Before a negotiation starts human negotiators prepare the dialogic exchanges that can be made along the five LOGIC dimensions [7]: • Legitimacy. What information is relevant to the negotiation process? What are the persuasive arguments about the fairness of the options? 1030 978-81-904262-7-5 (RPS) c 2007 IFAAMAS • Options. What are the possible agreements we can accept? • Goals. What are the underlying things we need or care about? What are our goals? • Independence. What will we do if the negotiation fails? What alternatives have we got? • Commitment. What outstanding commitments do we have? Negotiation dialogues, in this context, exchange dialogical moves, i.e. messages, with the intention of getting information about the opponent or giving away information about us along these five dimensions: request for information, propose options, inform about interests, issue promises, appeal to standards . . . A key part of any negotiation process is to build a model of our opponent(s) along these dimensions. All utterances agents make during a negotiation give away information about their current LOGIC model, that is, about their legitimacy, options, goals, independence, and commitments. Also, several utterances can have a utilitarian interpretation in the sense that an agent can associate a preferential gain to them. For instance, an offer may inform our negotiation opponent about our willingness to sign a contract in the terms expressed in the offer, and at the same time the opponent can compute what is its associated expected utilitarian gain. These two views: informationbased and utility-based, are central in the model proposed in this paper. 2.1 Intimacy and Balance in relationships There is evidence from psychological studies that humans seek a balance in their negotiation relationships. The classical view [1] is that people perceive resource allocations as being distributively fair (i.e. well balanced) if they are proportional to inputs or contributions (i.e. equitable). However, more recent studies [16, 17] show that humans follow a richer set of norms of distributive justice depending on their intimacy level: equity, equality, and need. Equity being the allocation proportional to the effort (e.g. the profit of a company goes to the stock holders proportional to their investment), equality being the allocation in equal amounts (e.g. two friends eat the same amount of a cake cooked by one of them), and need being the allocation proportional to the need for the resource (e.g. in case of food scarcity, a mother gives all food to her baby). For instance, if we are in a purely economic setting (low intimacy) we might request equity for the Options dimension but could accept equality in the Goals dimension. The perception of a relation being in balance (i.e. fair) depends strongly on the nature of the social relationships between individuals (i.e. the intimacy level). In purely economical relationships (e.g., business), equity is perceived as more fair; in relations where joint action or fostering of social relationships are the goal (e.g. friends), equality is perceived as more fair; and in situations where personal development or personal welfare are the goal (e.g. family), allocations are usually based on need. We believe that the perception of balance in dialogues (in negotiation or otherwise) is grounded on social relationships, and that every dimension of an interaction between humans can be correlated to the social closeness, or intimacy, between the parties involved. According to the previous studies, the more intimacy across the five LOGIC dimensions the more the need norm is used, and the less intimacy the more the equity norm is used. This might be part of our social evolution. There is ample evidence that when human societies evolved from a hunter-gatherer structure1 to a shelterbased one2 the probability of survival increased when food was scarce. In this context, we can clearly see that, for instance, families exchange not only goods but also information and knowledge based on need, and that few families would consider their relationships as being unbalanced, and thus unfair, when there is a strong asymmetry in the exchanges (a mother explaining everything to her children, or buying toys, does not expect reciprocity). In the case of partners there is some evidence [3] that the allocations of goods and burdens (i.e. positive and negative utilities) are perceived as fair, or in balance, based on equity for burdens and equality for goods. See Table 1 for some examples of desired balances along the LOGIC dimensions. The perceived balance in a negotiation dialogue allows negotiators to infer information about their opponent, about its LOGIC stance, and to compare their relationships with all negotiators. For instance, if we perceive that every time we request information it is provided, and that no significant questions are returned, or no complaints about not receiving information are given, then that probably means that our opponent perceives our social relationship to be very close. Alternatively, we can detect what issues are causing a burden to our opponent by observing an imbalance in the information or utilitarian senses on that issue. 3. COMMUNICATION MODEL 3.1 Ontology In order to define a language to structure agent dialogues we need an ontology that includes a (minimum) repertoire of elements: a set of concepts (e.g. quantity, quality, material) organised in a is-a hierarchy (e.g. platypus is a mammal, Australian-dollar is a currency), and a set of relations over these concepts (e.g. price(beer,AUD)).3 We model ontologies following an algebraic approach [8] as: An ontology is a tuple O = (C, R, ≤, σ) where: 1. C is a finite set of concept symbols (including basic data types); 2. R is a finite set of relation symbols; 3. ≤ is a reflexive, transitive and anti-symmetric relation on C (a partial order) 4. σ : R → C+ is the function assigning to each relation symbol its arity 1 In its purest form, individuals in these societies collect food and consume it when and where it is found. This is a pure equity sharing of the resources, the gain is proportional to the effort. 2 In these societies there are family units, around a shelter, that represent the basic food sharing structure. Usually, food is accumulated at the shelter for future use. Then the food intake depends more on the need of the members. 3 Usually, a set of axioms defined over the concepts and relations is also required. We will omit this here. The Sixth Intl. Joint Conf. on Autonomous Agents and Multi-Agent Systems (AAMAS 07) 1031 Element A new trading partner my butcher my boss my partner my children Legitimacy equity equity equity equality need Options equity equity equity mixeda need Goals equity need equity need need Independence equity equity equality need need Commitment equity equity equity mixed need a equity on burden, equality on good Table 1: Some desired balances (sense of fairness) examples depending on the relationship. where ≤ is the traditional is-a hierarchy. To simplify computations in the computing of probability distributions we assume that there is a number of disjoint is-a trees covering different ontological spaces (e.g. a tree for types of fabric, a tree for shapes of clothing, and so on). R contains relations between the concepts in the hierarchy, this is needed to define ‘objects" (e.g. deals) that are defined as a tuple of issues. The semantic distance between concepts within an ontology depends on how far away they are in the structure defined by the ≤ relation. Semantic distance plays a fundamental role in strategies for information-based agency. How signed contracts, Commit(·), about objects in a particular semantic region, and their execution, Done(·), affect our decision making process about signing future contracts in nearby semantic regions is crucial to modelling the common sense that human beings apply in managing trading relationships. A measure [10] bases the semantic similarity between two concepts on the path length induced by ≤ (more distance in the ≤ graph means less semantic similarity), and the depth of the subsumer concept (common ancestor) in the shortest path between the two concepts (the deeper in the hierarchy, the closer the meaning of the concepts). Semantic similarity is then defined as: Sim(c, c ) = e−κ1l · eκ2h − e−κ2h eκ2h + e−κ2h where l is the length (i.e. number of hops) of the shortest path between the concepts, h is the depth of the deepest concept subsuming both concepts, and κ1 and κ2 are parameters scaling the contributions of the shortest path length and the depth respectively. 3.2 Language The shape of the language that α uses to represent the information received and the content of its dialogues depends on two fundamental notions. First, when agents interact within an overarching institution they explicitly or implicitly accept the norms that will constrain their behaviour, and accept the established sanctions and penalties whenever norms are violated. Second, the dialogues in which α engages are built around two fundamental actions: (i) passing information, and (ii) exchanging proposals and contracts. A contract δ = (a, b) between agents α and β is a pair where a and b represent the actions that agents α and β are responsible for respectively. Contracts signed by agents and information passed by agents, are similar to norms in the sense that they oblige agents to behave in a particular way, so as to satisfy the conditions of the contract, or to make the world consistent with the information passed. Contracts and Information can thus be thought of as normative statements that restrict an agent"s behaviour. Norms, contracts, and information have an obvious temporal dimension. Thus, an agent has to abide by a norm while it is inside an institution, a contract has a validity period, and a piece of information is true only during an interval in time. The set of norms affecting the behaviour of an agent defines the context that the agent has to take into account. α"s communication language has two fundamental primitives: Commit(α, β, ϕ) to represent, in ϕ, the world that α aims at bringing about and that β has the right to verify, complain about or claim compensation for any deviations from, and Done(μ) to represent the event that a certain action μ4 has taken place. In this way, norms, contracts, and information chunks will be represented as instances of Commit(·) where α and β can be individual agents or institutions. C is: μ ::= illoc(α, β, ϕ, t) | μ; μ | Let context In μ End ϕ ::= term | Done(μ) | Commit(α, β, ϕ) | ϕ ∧ ϕ | ϕ ∨ ϕ | ¬ϕ | ∀v.ϕv | ∃v.ϕv context ::= ϕ | id = ϕ | prolog clause | context; context where ϕv is a formula with free variable v, illoc is any appropriate set of illocutionary particles, ‘;" means sequencing, and context represents either previous agreements, previous illocutions, the ontological working context, that is a projection of the ontological trees that represent the focus of the conversation, or code that aligns the ontological differences between the speakers needed to interpret an action a. Representing an ontology as a set predicates in Prolog is simple. The set term contains instances of the ontology concepts and relations.5 For example, we can represent the following offer: If you spend a total of more than e100 in my shop during October then I will give you a 10% discount on all goods in November, as: Offer( α, β,spent(β, α, October, X) ∧ X ≥ e100 → ∀ y. Done(Inform(ξ, α, pay(β, α, y), November)) → Commit(α, β, discount(y,10%))) ξ is an institution agent that reports the payment. 4 Without loss of generality we will assume that all actions are dialogical. 5 We assume the convention that C(c) means that c is an instance of concept C and r(c1, . . . , cn) implicitly determines that ci is an instance of the concept in the i-th position of the relation r. 1032 The Sixth Intl. Joint Conf. on Autonomous Agents and Multi-Agent Systems (AAMAS 07) Figure 1: The LOGIC agent architecture 4. AGENT ARCHITECTURE A multiagent system {α, β1, . . . , βn, ξ, θ1, . . . , θt}, contains an agent α that interacts with other argumentation agents, βi, information providing agents, θj, and an institutional agent, ξ, that represents the institution where we assume the interactions happen [2]. The institutional agent reports promptly and honestly on what actually occurs after an agent signs a contract, or makes some other form of commitment. In Section 4.1 this enables us to measure the difference between an utterance and a subsequent observation. The communication language C introduced in Section 3.2 enables us both to structure the dialogues and to structure the processing of the information gathered by agents. Agents have a probabilistic first-order internal language L used to represent a world model, Mt . A generic information-based architecture is described in detail in [15]. The LOGIC agent architecture is shown in Figure 1. Agent α acts in response to a need that is expressed in terms of the ontology. A need may be exogenous such as a need to trade profitably and may be triggered by another agent offering to trade, or endogenous such as α deciding that it owns more wine than it requires. Needs trigger α"s goal/plan proactive reasoning, while other messages are dealt with by α"s reactive reasoning.6 Each plan prepares for the negotiation by assembling the contents of a ‘LOGIC briefcase" that the agent ‘carries" into the negotiation7 . The relationship strategy determines which agent to negotiate with for a given need; it uses risk management analysis to preserve a strategic set of trading relationships for each mission-critical need - this is not detailed here. For each trading relationship this strategy generates a relationship target that is expressed in the LOGIC framework as a desired level of intimacy to be achieved in the long term. Each negotiation consists of a dialogue, Ψt , between two agents with agent α contributing utterance μ and the part6 Each of α"s plans and reactions contain constructors for an initial world model Mt . Mt is then maintained from percepts received using update functions that transform percepts into constraints on Mt - for details, see [14, 15]. 7 Empirical evidence shows that in human negotiation, better outcomes are achieved by skewing the opening Options in favour of the proposer. We are unaware of any empirical investigation of this hypothesis for autonomous agents in real trading scenarios. ner β contributing μ using the language described in Section 3.2. Each dialogue, Ψt , is evaluated using the LOGIC framework in terms of the value of Ψt to both α and β - see Section 5.2. The negotiation strategy then determines the current set of Options {δi}, and then the tactics, guided by the negotiation target, decide which, if any, of these Options to put forward and wraps them in argumentation dialogue - see Section 6. We now describe two of the distributions in Mt that support offer exchange. Pt (acc(α, β, χ, δ)) estimates the probability that α should accept proposal δ in satisfaction of her need χ, where δ = (a, b) is a pair of commitments, a for α and b for β. α will accept δ if: Pt (acc(α, β, χ, δ)) > c, for level of certainty c. This estimate is compounded from subjective and objective views of acceptability. The subjective estimate takes account of: the extent to which the enactment of δ will satisfy α"s need χ, how much δ is ‘worth" to α, and the extent to which α believes that she will be in a position to execute her commitment a [14, 15]. Sα(β, a) is a random variable denoting α"s estimate of β"s subjective valuation of a over some finite, numerical evaluation space. The objective estimate captures whether δ is acceptable on the open market, and variable Uα(b) denotes α"s open-market valuation of the enactment of commitment b, again taken over some finite numerical valuation space. We also consider needs, the variable Tα(β, a) denotes α"s estimate of the strength of β"s motivating need for the enactment of commitment a over a valuation space. Then for δ = (a, b): Pt (acc(α, β, χ, δ)) = Pt „ Tα(β, a) Tα(α, b) «h × „ Sα(α, b) Sα(β, a) «g × Uα(b) Uα(a) ≥ s ! (1) where g ∈ [0, 1] is α"s greed, h ∈ [0, 1] is α"s degree of altruism, and s ≈ 1 is derived from the stance8 described in Section 6. The parameters g and h are independent. We can imagine a relationship that begins with g = 1 and h = 0. Then as the agents share increasing amounts of their information about their open market valuations g gradually reduces to 0, and then as they share increasing amounts of information about their needs h increases to 1. The basis for the acceptance criterion has thus developed from equity to equality, and then to need. Pt (acc(β, α, δ)) estimates the probability that β would accept δ, by observing β"s responses. For example, if β sends the message Offer(δ1) then α derives the constraint: {Pt (acc(β, α, δ1)) = 1} on the distribution Pt (β, α, δ), and if this is a counter offer to a former offer of α"s, δ0, then: {Pt (acc(β, α, δ0)) = 0}. In the not-atypical special case of multi-issue bargaining where the agents" preferences over the individual issues only are known and are complementary to each other"s, maximum entropy reasoning can be applied to estimate the probability that any multi-issue δ will be acceptable to β by enumerating the possible worlds that represent β"s limit of acceptability [6]. 4.1 Updating the World Model Mt α"s world model consists of probability distributions that represent its uncertainty in the world state. α is interested 8 If α chooses to inflate her opening Options then this is achieved in Section 6 by increasing the value of s. If s 1 then a deal may not be possible. This illustrates the wellknown inefficiency of bilateral bargaining established analytically by Myerson and Satterthwaite in 1983. The Sixth Intl. Joint Conf. on Autonomous Agents and Multi-Agent Systems (AAMAS 07) 1033 in the degree to which an utterance accurately describes what will subsequently be observed. All observations about the world are received as utterances from an all-truthful institution agent ξ. For example, if β communicates the goal I am hungry and the subsequent negotiation terminates with β purchasing a book from α (by ξ advising α that a certain amount of money has been credited to α"s account) then α may conclude that the goal that β chose to satisfy was something other than hunger. So, α"s world model contains probability distributions that represent its uncertain expectations of what will be observed on the basis of utterances received. We represent the relationship between utterance, ϕ, and subsequent observation, ϕ , by Pt (ϕ |ϕ) ∈ Mt , where ϕ and ϕ may be ontological categories in the interest of computational feasibility. For example, if ϕ is I will deliver a bucket of fish to you tomorrow then the distribution P(ϕ |ϕ) need not be over all possible things that β might do, but could be over ontological categories that summarise β"s possible actions. In the absence of in-coming utterances, the conditional probabilities, Pt (ϕ |ϕ), should tend to ignorance as represented by a decay limit distribution D(ϕ |ϕ). α may have background knowledge concerning D(ϕ |ϕ) as t → ∞, otherwise α may assume that it has maximum entropy whilst being consistent with the data. In general, given a distribution, Pt (Xi), and a decay limit distribution D(Xi), Pt (Xi) decays by: Pt+1 (Xi) = Δi(D(Xi), Pt (Xi)) (2) where Δi is the decay function for the Xi satisfying the property that limt→∞ Pt (Xi) = D(Xi). For example, Δi could be linear: Pt+1 (Xi) = (1 − νi) × D(Xi) + νi × Pt (Xi), where νi < 1 is the decay rate for the i"th distribution. Either the decay function or the decay limit distribution could also be a function of time: Δt i and Dt (Xi). Suppose that α receives an utterance μ = illoc(α, β, ϕ, t) from agent β at time t. Suppose that α attaches an epistemic belief Rt (α, β, μ) to μ - this probability takes account of α"s level of personal caution. We model the update of Pt (ϕ |ϕ) in two cases, one for observations given ϕ, second for observations given φ in the semantic neighbourhood of ϕ. 4.2 Update of Pt (ϕ |ϕ) given ϕ First, if ϕk is observed then α may set Pt+1 (ϕk|ϕ) to some value d where {ϕ1, ϕ2, . . . , ϕm} is the set of all possible observations. We estimate the complete posterior distribution Pt+1 (ϕ |ϕ) by applying the principle of minimum relative entropy9 as follows. Let p(μ) be the distribution: 9 Given a probability distribution q, the minimum relative entropy distribution p = (p1, . . . , pI ) subject to a set of J linear constraints g = {gj(p) = aj · p − cj = 0}, j = 1, . . . , J (that must include the constraint P i pi − 1 = 0) is: p = arg minr P j rj log rj qj . This may be calculated by introducing Lagrange multipliers λ: L(p, λ) = P j pj log pj qj + λ · g. Minimising L, { ∂L ∂λj = gj(p) = 0}, j = 1, . . . , J is the set of given constraints g, and a solution to ∂L ∂pi = 0, i = 1, . . . , I leads eventually to p. Entropy-based inference is a form of Bayesian inference that is convenient when the data is sparse [5] and encapsulates common-sense reasoning [12]. arg minx P j xj log xj Pt(ϕ |ϕ)j that satisfies the constraint p(μ)k = d. Then let q(μ) be the distribution: q(μ) = Rt (α, β, μ) × p(μ) + (1 − Rt (α, β, μ)) × Pt (ϕ |ϕ) and then let: r(μ) = ( q(μ) if q(μ) is more interesting than Pt (ϕ |ϕ) Pt (ϕ |ϕ) otherwise A general measure of whether q(μ) is more interesting than Pt (ϕ |ϕ) is: K(q(μ) D(ϕ |ϕ)) > K(Pt (ϕ |ϕ) D(ϕ |ϕ)), where K(x y) = P j xj ln xj yj is the Kullback-Leibler distance between two probability distributions x and y [11]. Finally incorporating Eqn. 2 we obtain the method for updating a distribution Pt (ϕ |ϕ) on receipt of a message μ: Pt+1 (ϕ |ϕ) = Δi(D(ϕ |ϕ), r(μ)) (3) This procedure deals with integrity decay, and with two probabilities: first, the probability z in the utterance μ, and second the belief Rt (α, β, μ) that α attached to μ. 4.3 Update of Pt (φ |φ) given ϕ The sim method: Given as above μ = illoc(α, β, ϕ, t) and the observation ϕk we define the vector t by ti = Pt (φi|φ) + (1− | Sim(ϕk, ϕ) − Sim(φi, φ) |) · Sim(ϕk, φ) with {φ1, φ2, . . . , φp} the set of all possible observations in the context of φ and i = 1, . . . , p. t is not a probability distribution. The multiplying factor Sim(ϕ , φ) limits the variation of probability to those formulae whose ontological context is not too far away from the observation. The posterior Pt+1 (φ |φ) is obtained with Equation 3 with r(μ) defined to be the normalisation of t. The valuation method: For a given φk, wexp (φk) =Pm j=1 Pt (φj|φk) · w(φj) is α"s expectation of the value of what will be observed given that β has stated that φk will be observed, for some measure w. Now suppose that, as before, α observes ϕk after agent β has stated ϕ. α revises the prior estimate of the expected valuation wexp (φk) in the light of the observation ϕk to: (wrev (φk) | (ϕk|ϕ)) = g(wexp (φk), Sim(φk, ϕ), w(φk), w(ϕ), wi(ϕk)) for some function g - the idea being, for example, that if the execution, ϕk, of the commitment, ϕ, to supply cheese was devalued then α"s expectation of the value of a commitment, φ, to supply wine should decrease. We estimate the posterior by applying the principle of minimum relative entropy as for Equation 3, where the distribution p(μ) = p(φ |φ) satisfies the constraint: p X j=1 p(ϕ ,ϕ)j · wi(φj) = g(wexp (φk), Sim(φk, ϕ), w(φk), w(ϕ), wi(ϕk)) 5. SUMMARY MEASURES A dialogue, Ψt , between agents α and β is a sequence of inter-related utterances in context. A relationship, Ψ∗t , is a sequence of dialogues. We first measure the confidence that an agent has for another by observing, for each utterance, the difference between what is said (the utterance) and what 1034 The Sixth Intl. Joint Conf. on Autonomous Agents and Multi-Agent Systems (AAMAS 07) subsequently occurs (the observation). Second we evaluate each dialogue as it progresses in terms of the LOGIC framework - this evaluation employs the confidence measures. Finally we define the intimacy of a relationship as an aggregation of the value of its component dialogues. 5.1 Confidence Confidence measures generalise what are commonly called trust, reliability and reputation measures into a single computational framework that spans the LOGIC categories. In Section 5.2 confidence measures are applied to valuing fulfilment of promises in the Legitimacy category - we formerly called this honour [14], to the execution of commitments - we formerly called this trust [13], and to valuing dialogues in the Goals category - we formerly called this reliability [14]. Ideal observations. Consider a distribution of observations that represent α"s ideal in the sense that it is the best that α could reasonably expect to observe. This distribution will be a function of α"s context with β denoted by e, and is Pt I (ϕ |ϕ, e). Here we measure the relative entropy between this ideal distribution, Pt I (ϕ |ϕ, e), and the distribution of expected observations, Pt (ϕ |ϕ). That is: C(α, β, ϕ) = 1 − X ϕ Pt I (ϕ |ϕ, e) log Pt I (ϕ |ϕ, e) Pt(ϕ |ϕ) (4) where the 1 is an arbitrarily chosen constant being the maximum value that this measure may have. This equation measures confidence for a single statement ϕ. It makes sense to aggregate these values over a class of statements, say over those ϕ that are in the ontological context o, that is ϕ ≤ o: C(α, β, o) = 1 − P ϕ:ϕ≤o Pt β(ϕ) [1 − C(α, β, ϕ)] P ϕ:ϕ≤o Pt β(ϕ) where Pt β(ϕ) is a probability distribution over the space of statements that the next statement β will make to α is ϕ. Similarly, for an overall estimate of β"s confidence in α: C(α, β) = 1 − X ϕ Pt β(ϕ) [1 − C(α, β, ϕ)] Preferred observations. The previous measure requires that an ideal distribution, Pt I (ϕ |ϕ, e), has to be specified for each ϕ. Here we measure the extent to which the observation ϕ is preferable to the original statement ϕ. Given a predicate Prefer(c1, c2, e) meaning that α prefers c1 to c2 in environment e. Then if ϕ ≤ o: C(α, β, ϕ) = X ϕ Pt (Prefer(ϕ , ϕ, o))Pt (ϕ |ϕ) and: C(α, β, o) = P ϕ:ϕ≤o Pt β(ϕ)C(α, β, ϕ) P ϕ:ϕ≤o Pt β(ϕ) Certainty in observation. Here we measure the consistency in expected acceptable observations, or the lack of expected uncertainty in those possible observations that are better than the original statement. If ϕ ≤ o let: Φ+(ϕ, o, κ) =˘ ϕ | Pt (Prefer(ϕ , ϕ, o)) > κ ¯ for some constant κ, and: C(α, β, ϕ) = 1 + 1 B∗ · X ϕ ∈Φ+(ϕ,o,κ) Pt +(ϕ |ϕ) log Pt +(ϕ |ϕ) where Pt +(ϕ |ϕ) is the normalisation of Pt (ϕ |ϕ) for ϕ ∈ Φ+(ϕ, o, κ), B∗ = ( 1 if |Φ+(ϕ, o, κ)| = 1 log |Φ+(ϕ, o, κ)| otherwise As above we aggregate this measure for observations in a particular context o, and measure confidence as before. Computational Note. The various measures given above involve extensive calculations. For example, Eqn. 4 containsP ϕ that sums over all possible observations ϕ . We obtain a more computationally friendly measure by appealing to the structure of the ontology described in Section 3.2, and the right-hand side of Eqn. 4 may be approximated to: 1 − X ϕ :Sim(ϕ ,ϕ)≥η Pt η,I (ϕ |ϕ, e) log Pt η,I (ϕ |ϕ, e) Pt η(ϕ |ϕ) where Pt η,I (ϕ |ϕ, e) is the normalisation of Pt I (ϕ |ϕ, e) for Sim(ϕ , ϕ) ≥ η, and similarly for Pt η(ϕ |ϕ). The extent of this calculation is controlled by the parameter η. An even tighter restriction may be obtained with: Sim(ϕ , ϕ) ≥ η and ϕ ≤ ψ for some ψ. 5.2 Valuing negotiation dialogues Suppose that a negotiation commences at time s, and by time t a string of utterances, Φt = μ1, . . . , μn has been exchanged between agent α and agent β. This negotiation dialogue is evaluated by α in the context of α"s world model at time s, Ms , and the environment e that includes utterances that may have been received from other agents in the system including the information sources {θi}. Let Ψt = (Φt , Ms , e), then α estimates the value of this dialogue to itself in the context of Ms and e as a 2 × 5 array Vα(Ψt ) where: Vx(Ψt ) = „ IL x (Ψt ) IO x (Ψt ) IG x (Ψt ) II x(Ψt ) IC x (Ψt ) UL x (Ψt ) UO x (Ψt ) UG x (Ψt ) UI x(Ψt ) UC x (Ψt ) « where the I(·) and U(·) functions are information-based and utility-based measures respectively as we now describe. α estimates the value of this dialogue to β as Vβ(Ψt ) by assuming that β"s reasoning apparatus mirrors its own. In general terms, the information-based valuations measure the reduction in uncertainty, or information gain, that the dialogue gives to each agent, they are expressed in terms of decrease in entropy that can always be calculated. The utility-based valuations measure utility gain are expressed in terms of some suitable utility evaluation function U(·) that can be difficult to define. This is one reason why the utilitarian approach has no natural extension to the management of argumentation that is achieved here by our informationbased approach. For example, if α receives the utterance Today is Tuesday then this may be translated into a constraint on a single distribution, and the resulting decrease in entropy is the information gain. Attaching a utilitarian measure to this utterance may not be so simple. We use the term 2 × 5 array loosely to describe Vα in that the elements of the array are lists of measures that will be determined by the agent"s requirements. Table 2 shows a sample measure for each of the ten categories, in it the dialogue commences at time s and terminates at time t. In that Table, U(·) is a suitable utility evaluation function, needs(β, χ) means agent β needs the need χ, cho(β, χ, γ) means agent β satisfies need χ by choosing to negotiate The Sixth Intl. Joint Conf. on Autonomous Agents and Multi-Agent Systems (AAMAS 07) 1035 with agent γ, N is the set of needs chosen from the ontology at some suitable level of abstraction, Tt is the set of offers on the table at time t, com(β, γ, b) means agent β has an outstanding commitment with agent γ to execute the commitment b where b is defined in the ontology at some suitable level of abstraction, B is the number of such commitments, and there are n + 1 agents in the system. 5.3 Intimacy and Balance The balance in a negotiation dialogue, Ψt , is defined as: Bαβ(Ψt ) = Vα(Ψt ) Vβ(Ψt ) for an element-by-element difference operator that respects the structure of V (Ψt ). The intimacy between agents α and β, I∗t αβ, is the pattern of the two 2 × 5 arrays V ∗t α and V ∗t β that are computed by an update function as each negotiation round terminates, I∗t αβ = ` V ∗t α , V ∗t β ´ . If Ψt terminates at time t: V ∗t+1 x = ν × Vx(Ψt ) + (1 − ν) × V ∗t x (5) where ν is the learning rate, and x = α, β. Additionally, V ∗t x continually decays by: V ∗t+1 x = τ × V ∗t x + (1 − τ) × Dx, where x = α, β; τ is the decay rate, and Dx is a 2 × 5 array being the decay limit distribution for the value to agent x of the intimacy of the relationship in the absence of any interaction. Dx is the reputation of agent x. The relationship balance between agents α and β is: B∗t αβ = V ∗t α V ∗t β . In particular, the intimacy determines values for the parameters g and h in Equation 1. As a simple example, if both IO α (Ψ∗t ) and IO β (Ψ∗t ) increase then g decreases, and as the remaining eight information-based LOGIC components increase, h increases. The notion of balance may be applied to pairs of utterances by treating them as degenerate dialogues. In simple multi-issue bargaining the equitable information revelation strategy generalises the tit-for-tat strategy in single-issue bargaining, and extends to a tit-for-tat argumentation strategy by applying the same principle across the LOGIC framework. 6. STRATEGIES AND TACTICS Each negotiation has to achieve two goals. First it may be intended to achieve some contractual outcome. Second it will aim to contribute to the growth, or decline, of the relationship intimacy. We now describe in greater detail the contents of the Negotiation box in Figure 1. The negotiation literature consistently advises that an agent"s behaviour should not be predictable even in close, intimate relationships. The required variation of behaviour is normally described as varying the negotiation stance that informally varies from friendly guy to tough guy. The stance is shown in Figure 1, it injects bounded random noise into the process, where the bound tightens as intimacy increases. The stance, St αβ, is a 2 × 5 matrix of randomly chosen multipliers, each ≈ 1, that perturbs α"s actions. The value in the (x, y) position in the matrix, where x = I, U and y = L, O, G, I, C, is chosen at random from [ 1 l(I∗t αβ ,x,y) , l(I∗t αβ, x, y)] where l(I∗t αβ, x, y) is the bound, and I∗t αβ is the intimacy. The negotiation strategy is concerned with maintaining a working set of Options. If the set of options is empty then α will quit the negotiation. α perturbs the acceptance machinery (see Section 4) by deriving s from the St αβ matrix such as the value at the (I, O) position. In line with the comment in Footnote 7, in the early stages of the negotiation α may decide to inflate her opening Options. This is achieved by increasing the value of s in Equation 1. The following strategy uses the machinery described in Section 4. Fix h, g, s and c, set the Options to the empty set, let Dt s = {δ | Pt (acc(α, β, χ, δ) > c}, then: • repeat the following as many times as desired: add δ = arg maxx{Pt (acc(β, α, x)) | x ∈ Dt s} to Options, remove {y ∈ Dt s | Sim(y, δ) < k} for some k from Dt s By using Pt (acc(β, α, δ)) this strategy reacts to β"s history of Propose and Reject utterances. Negotiation tactics are concerned with selecting some Options and wrapping them in argumentation. Prior interactions with agent β will have produced an intimacy pattern expressed in the form of ` V ∗t α , V ∗t β ´ . Suppose that the relationship target is (T∗t α , T∗t β ). Following from Equation 5, α will want to achieve a negotiation target, Nβ(Ψt ) such that: ν · Nβ(Ψt ) + (1 − ν) · V ∗t β is a bit on the T∗t β side of V ∗t β : Nβ(Ψt ) = ν − κ ν V ∗t β ⊕ κ ν T∗t β (6) for small κ ∈ [0, ν] that represents α"s desired rate of development for her relationship with β. Nβ(Ψt ) is a 2 × 5 matrix containing variations in the LOGIC dimensions that α would like to reveal to β during Ψt (e.g. I"ll pass a bit more information on options than usual, I"ll be stronger in concessions on options, etc.). It is reasonable to expect β to progress towards her target at the same rate and Nα(Ψt ) is calculated by replacing β by α in Equation 6. Nα(Ψt ) is what α hopes to receive from β during Ψt . This gives a negotiation balance target of: Nα(Ψt ) Nβ(Ψt ) that can be used as the foundation for reactive tactics by striving to maintain this balance across the LOGIC dimensions. A cautious tactic could use the balance to bound the response μ to each utterance μ from β by the constraint: Vα(μ ) Vβ(μ) ≈ St αβ ⊗ (Nα(Ψt ) Nβ(Ψt )), where ⊗ is element-by-element matrix multiplication, and St αβ is the stance. A less neurotic tactic could attempt to achieve the target negotiation balance over the anticipated complete dialogue. If a balance bound requires negative information revelation in one LOGIC category then α will contribute nothing to it, and will leave this to the natural decay to the reputation D as described above. 7. DISCUSSION In this paper we have introduced a novel approach to negotiation that uses information and game-theoretical measures grounded on business and psychological studies. It introduces the concepts of intimacy and balance as key elements in understanding what is a negotiation strategy and tactic. Negotiation is understood as a dialogue that affect five basic dimensions: Legitimacy, Options, Goals, Independence, and Commitment. Each dialogical move produces a change in a 2×5 matrix that evaluates the dialogue along five information-based measures and five utility-based measures. The current Balance and intimacy levels and the desired, or target, levels are used by the tactics to determine what to say next. We are currently exploring the use of this model as an extension of a currently widespread eProcurement software commercialised by iSOCO, a spin-off company of the laboratory of one of the authors. 1036 The Sixth Intl. Joint Conf. on Autonomous Agents and Multi-Agent Systems (AAMAS 07) IL α(Ψt ) = X ϕ∈Ψt Ct (α, β, ϕ) − Cs (α, β, ϕ) UL α (Ψt ) = X ϕ∈Ψt X ϕ Pt β(ϕ |ϕ) × Uα(ϕ ) IO α (Ψt ) = P δ∈T t Hs (acc(β, α, δ)) − P δ∈T t Ht (acc(β, α, δ)) |Tt| UO α (Ψt ) = X δ∈T t Pt (acc(β, α, δ)) × X δ Pt (δ |δ)Uα(δ ) IG α (Ψt ) = P χ∈N Hs (needs(β, χ)) − Ht (needs(β, χ)) |N| UG α (Ψt ) = X χ∈N Pt (needs(β, χ)) × Et (Uα(needs(β, χ))) II α(Ψt ) = Po i=1 P χ∈N Hs (cho(β, χ, βi)) − Ht (cho(β, χ, βi)) n × |N| UI α(Ψt ) = oX i=1 X χ∈N Ut (cho(β, χ, βi)) − Us (cho(β, χ, βi)) IC α (Ψt ) = Po i=1 P δ∈B Hs (com(β, βi, b)) − Ht (com(β, βi, b)) n × |B| UC α (Ψt ) = oX i=1 X δ∈B Ut (com(β, βi, b)) − Us (com(β, βi, b)) Table 2: Sample measures for each category in Vα(Ψt ). (Similarly for Vβ(Ψt ).) Acknowledgements Carles Sierra is partially supported by the OpenKnowledge European STREP project and by the Spanish IEA Project. 8. REFERENCES [1] Adams, J. S. Inequity in social exchange. In Advances in experimental social psychology, L. Berkowitz, Ed., vol. 2. New York: Academic Press, 1965. [2] Arcos, J. L., Esteva, M., Noriega, P., Rodr´ıguez, J. A., and Sierra, C. Environment engineering for multiagent systems. Journal on Engineering Applications of Artificial Intelligence 18 (2005). [3] Bazerman, M. H., Loewenstein, G. F., and White, S. B. Reversal of preference in allocation decisions: judging an alternative versus choosing among alternatives. Administration Science Quarterly, 37 (1992), 220-240. [4] Brandenburger, A., and Nalebuff, B. Co-Opetition : A Revolution Mindset That Combines Competition and Cooperation. Doubleday, New York, 1996. [5] Cheeseman, P., and Stutz, J. Bayesian Inference and Maximum Entropy Methods in Science and Engineering. American Institute of Physics, Melville, NY, USA, 2004, ch. On The Relationship between Bayesian and Maximum Entropy Inference, pp. 445461. [6] Debenham, J. Bargaining with information. In Proceedings Third International Conference on Autonomous Agents and Multi Agent Systems AAMAS-2004 (July 2004), N. Jennings, C. Sierra, L. Sonenberg, and M. Tambe, Eds., ACM Press, New York, pp. 664 - 671. [7] Fischer, R., Ury, W., and Patton, B. Getting to Yes: Negotiating agreements without giving in. Penguin Books, 1995. [8] Kalfoglou, Y., and Schorlemmer, M. IF-Map: An ontology-mapping method based on information-flow theory. In Journal on Data Semantics I, S. Spaccapietra, S. March, and K. Aberer, Eds., vol. 2800 of Lecture Notes in Computer Science. Springer-Verlag: Heidelberg, Germany, 2003, pp. 98-127. [9] Lewicki, R. J., Saunders, D. M., and Minton, J. W. Essentials of Negotiation. McGraw Hill, 2001. [10] Li, Y., Bandar, Z. A., and McLean, D. An approach for measuring semantic similarity between words using multiple information sources. IEEE Transactions on Knowledge and Data Engineering 15, 4 (July / August 2003), 871 - 882. [11] MacKay, D. Information Theory, Inference and Learning Algorithms. Cambridge University Press, 2003. [12] Paris, J. Common sense and maximum entropy. Synthese 117, 1 (1999), 75 - 93. [13] Sierra, C., and Debenham, J. An information-based model for trust. In Proceedings Fourth International Conference on Autonomous Agents and Multi Agent Systems AAMAS-2005 (Utrecht, The Netherlands, July 2005), F. Dignum, V. Dignum, S. Koenig, S. Kraus, M. Singh, and M. Wooldridge, Eds., ACM Press, New York, pp. 497 - 504. [14] Sierra, C., and Debenham, J. Trust and honour in information-based agency. In Proceedings Fifth International Conference on Autonomous Agents and Multi Agent Systems AAMAS-2006 (Hakodate, Japan, May 2006), P. Stone and G. Weiss, Eds., ACM Press, New York, pp. 1225 - 1232. [15] Sierra, C., and Debenham, J. Information-based agency. In Proceedings of Twentieth International Joint Conference on Artificial Intelligence IJCAI-07 (Hyderabad, India, January 2007), pp. 1513-1518. [16] Sondak, H., Neale, M. A., and Pinkley, R. The negotiated allocations of benefits and burdens: The impact of outcome valence, contribution, and relationship. Organizational Behaviour and Human Decision Processes, 3 (December 1995), 249-260. [17] Valley, K. L., Neale, M. A., and Mannix, E. A. Friends, lovers, colleagues, strangers: The effects of relationships on the process and outcome of negotiations. In Research in Negotiation in Organizations, R. Bies, R. Lewicki, and B. Sheppard, Eds., vol. 5. JAI Press, 1995, pp. 65-94. The Sixth Intl. Joint Conf. on Autonomous Agents and Multi-Agent Systems (AAMAS 07) 1037
utterance utilitarian interpretation ontology multiagent system logic agent architecture negotiation strategy acceptance criterion negotiation
successive negotiation encounter long term relationship set predicate view of acceptability acceptability view component dialogue confidence measure