Negotiation Using Logic Programming with Consistency Restoring Rules

1 Introduction

An intelligent agent situated in the real world often has to negotiate with others to achieve his/her objectives. Consider a typical negotiation between a seller and a buyer:

• Seller: Would you like to have this PC for $1000?
• Buyer: Done.

• Buyer: Can I get it for $900?
• Seller: Only if you pay by cash.

This simple negotiation shows that a negotiation between agents often involves reasoning with incomplete information and preferences. Here, the seller prefers to sell his/her PC for $1000 but he/she could accept $900 if the buyer pays by cash. The seller, at the beginning of the negotiation, does not have the information about the method of payment of the buyer. He/she would learn about this information during the negotiation. Furthermore, due to his/her preference, it is natural to expect that the seller would discuss the method of payment only if the buyer requests for a discount.

The above discussion implies that any formalism for reasoning about negotiation needs to have the capability to deal with preferences and incomplete information. Surprisingly, there have been only a few attempts to formalize negotiation using logic programming despite the fact that logic programming is known as a knowledge representation language suitable for reasoning with incomplete information and preferences (e.g., [Baral, 2003; Gelfond and Leone, 2002]). These

∗Partially supported by NSF grants IIS-0812267, MII-0220590, CREST-0420407, and a JSPS award.

Chiaki Sakama

Computer and Communication Sciences Wakayama University Wakayama 640-8510, Japan sakama@sys.wakayama-u.ac.jp

attempts use logic programming under the answer set semantics but rely on techniques in belief revision to compute deals between agents (e.g., [Chen et al., 2006]).

The example also shows that agents might change their goals during the negotiation. This is also a key issue in formalizing negotiation, which seems to prefer argumentationbased negotiation [Rahwan et al., 2003]. Recent proposals on formalizing negotiation (see, e.g., [Amgoud et al., 2006; Kakas and Moraitis, 2006; Rahwan et al., 2003]) seem to be in-line with this conclusion. This raises a question on the suitability of logic programming in formalizing negotiation. Our goal in this paper is to address this question.

In this paper, we use logic programming with consistency restoring rules (or CR-Prolog) [Balduccini and Gelfond, 2003] to formalize negotiation. We represent the knowledge (for negotiation) of each agent as a CR-Prolog program extended with a set of assumptions and a set of ordered goals and use answer sets as a means to define proposals and their acceptability as well as a negotiation and related notions. We will begin with a short review of CR-Prolog. After that, we define the notion of a negotiation knowledge base, proposal, and discuss our proposal classification. We then present our formalization of negotiation based on these notions and discuss how it can be extended to accommodate agents' changes in goals. Finally, we relate our work to others and discuss future work.

2 LP with Consistency Restoring Rules

A logic program Π is a set of normal rules of the form

where 0 ≤ m ≤ n, 0 ≤ k, each ai or cj is a literal of a propositional language 1 and not represents negation-asfailure. A negation as failure literal (or naf-literal) is of the form not a where a is a literal. For a rule of the form (1), the left and right hand sides of the rule are called the head and the body, respectively. Both the head and the body can be empty. When the head is empty, the rule is called a constraint. When the body is empty, the rule is called a fact.

For a rule r of the form (1), H(r) and B(r) denote the left and right hand side of ←, respectively; head(r) denotes the set {c1, . . . , ck}; and pos(r) and neg(r) denote {a1, . . . , am} and {am+1, . . . , an}, respectively.

1 Rules with variables are viewed as a shorthand for the set of its ground instances.

Consider a set of ground literals X. X is consistent if there exists no atom a such that both a and ¬a belong to X. The body of a rule r of the form (1) is satisfied by X if neg(r) ∩ X = ∅ and pos(r) ⊆ X. A rule of the form (1) with nonempty head is satisfied by X if either its body is not satisfied by X or head(r) ∩ X ̸= ∅. A constraint is satisfied by X if its body is not satisfied by X.

For a consistent set of ground literals S and a program Π, the reduct of Π w.r.t. S, denoted by ΠS , is the program obtained from the set of all ground instances of Π by deleting (i) each rule that has a naf-literal not a in its body with a ∈ S, and (ii) all naf-literals in the bodies of the remaining rules.

S is an answer set (or a stable model) of Π [Gelfond and Lifschitz, 1991] if it satisfies the following conditions: (i) If Π does not contain any naf-literal (i.e. m = n in every rule of Π) then S is a minimal consistent set of literals that satisfies all the rules in Π; and (ii) If Π does contain some naf-literal (m < n in some rule of Π), then S is an answer set of Π if S is the answer set of ΠS . (Note that ΠS does not contain nafliterals, its answer set is defined in the first item.) A program Π is said to be consistent if it has a consistent answer set. Otherwise, it is inconsistent.

CR-Prolog introduces an additional type of rules, called consistency restoring rules (or cr-rules), of the form

where r is the name of the rule and ci's and aj's are literals as in the rule (1). Observe that a cr-rule can be viewed as a normal rule (of the form (1)) by dropping its name and replacing the connective +←with←.

A CR-program P is given by a pair (P r , P c ) where P r is a set of rules of the form (1) and P c is a set of rules of the form (2). Let C be a subset of P c . By P r ∪ C we denote the program consisting of rules in P r and the cr-rules in C viewed as normal rules.

Answer sets of P are defined as follows. If P r is consistent, then any answer set of P r is an answer set of P. Otherwise, an answer set of P is an answer set of P r ∪C where C is a minimal subset of P c such that P r ∪ {H(r) ← B(r) | H(r) +←B(r) ∈ C} is consistent.

and P c = {r1 : p +← not r. r2 : q +← not r.} P r is inconsistent. P has two answer sets {p, s} and {q, s}, which are obtained by adding {r1} or {r2} to P r correspondingly.

Although adding {r1, r2} to P r also creates a consistent program, its answer set {p, q, s} is not considered as an answer set of P since the set {r1, r2} is not a minimal subset of P c with this property. ✷

When multiple rules can be used in restoring the consistency of a program, a preference relation in the form of prefer(r1, r2) can be added to the program to force the application of more preferred cr-rules in restoring the consistency of the program. It is assumed that prefer is a transitive and anti-symmetric relation among cr-rules of a program.

The semantics of CR-programs ensures that if prefer(r1, r2) is specified then the rule r2 should be used in restoring the consistency of the program only if no solution containing r1 is possible and the two rules are never used at the same time [Balduccini, 2007]. A CR-program (P r , P c ) is said to be consistent if it has at least one answer set. For example, if we add prefer(r1, r2) to P r then P = (P r , P c ) from the previous example will have only one answer set {p, s}.

3 Negotiation Knowledge Bases, Proposals, and Proposal Classification

For a set of literals L, Goal(L) denotes the set of constraint {← not l | l ∈ L}, {L +←} denotes the set of cr-rules {rl : l +←| l ∈ L}, and lit(L) the set {l, ¬l | l ∈ L or ¬l ∈ L}. A negotiation knowledge base is defined as follows.

Definition 1 (Negotiation KB). A negotiation knowledge base K (or n-KB, for short) is a tuple 〈P r , P c , H, N ≺〉 where

• (P r , P c ) is a CR-program,
• N ≺ is a set of negotiated literals associated with a strict partial order ≺ on its elements, and
• H is a set of literals (called assumptions) such that H∩ head(P r ) = ∅ and {H +←} ⊆ P c .

The n-KB is consistent if (P r , P c ) is consistent.

Intuitively, the program (P r , P c ) serves as a means for the agent to negotiate about a predefined objective 2 where P r consists of normal rules defining the domain-specific knowledge of the agent and P c consists of cr-rules defining possible negotiation strategies. N ≺ contains literals expressing the desired properties of outcome for which the n-KB is developed. ≺ represents a preference order of the agent with respect to the negotiated literals; a≺b means that b is preferred to a. The set of assumptions H represents information that the agent might not have at the beginning of the negotiation and some of this information might be known to him/her during the negotiation. Since the CR-program (P r , P c ) serves as a means for the agent to generate (counter)-supporting arguments, hypotheses, etc. in his/her negotiation, we will often require that (P r , P c ) is consistent, i.e., the n-KB is consistent.

We will now present two typical n-KBs, one of the seller and one of the buyer, that we will use as running examples. Intuitively, the seller agent will have a KB for him/her to negotiate a sale while a buyer agent will have a KB for him/her to negotiate a purchase. The buyer will want to get the best (lowest) price for the purchase that he/she is negotiating for while the seller would prefer to obtain the best (highest) price for the sale. For simplicity, we assume that the two knowledge bases discuss the same product.

Example 2 (Seller n-KB). A seller agent S uses the following n-KB in negotiating with his customers about the possible prices (of a certain product) that he can offer. KS = 〈P r S , P c S , HS , N ≺ S 〉 where 3

2 For generality, this objective can be specified as a parameter of the knowledge base. This makes the notations a little more complicated. To focus on the main points, we opt out of this option.

3 Arithmetic predicates are written in infix notation.

• P r S consists of the following rules:

whole sale customer ← registered. student customer ← student. senior customer ← age ≥ 65. sale ← sale price. ← not sale. prefer(r1, ri) ← (for i > 1) prefer(ri, r5) ← (for i ∈ {2, 3, 4})

where sale price ∈ {high pr, low pr, lowest pr} and the set of facts {made in L, maker A, ¬maker C, ¬maker B}. Here, P r S defines various types of customers, the predicate sale, and the preferences among the cr-rules of the KB. It also states some facts about the product at hand (e.g., it is made in location L and is a product of maker A).

• HS is a set of assumptions representing information that the seller needs to verify about his clients during the negotiation. It is the set of literals that can be built from the atoms 4
• N ≺ S is the set of atoms that the agent should be negotiated about and is defined by N ≺ S = {high pr, low pr, lowest pr} with ≺= {lowest pr ≺ low pr ≺ high pr}. It says that the seller prefers the high pr over low pr and lowest pr.
• P c S consists of {HS +←} and

{ registered, student, age ≥ 65, good credit, quantity ≥ 100, pay cash }

r1 : high pr +←

r2 : low pr

+← senior customer

r3 : low pr

+← student customer,

r4 : low pr good credit.

+← student customer, pay cash.

r5 : lowest pr +← whole sale customer,

quantity ≥ 100.

P c S specifies different pricing scenarios. Intuitively, r1 says that any customer who agrees to buy the product with high pr is welcome! A senior citizen is entitled to a discount (low pr) and the same holds for a student with good credit history. Whole sale customers are entitled to the biggest discount if they buy at least 100 units.

It is easy to see that (P r S , P c S ) is consistent, i.e., KS is a meaningful n-KB.

Finally, it is worth noting that the semantics of CR-Prolog ensures that no answer set of (P r S , P c S ) would contain two possible prices, i.e., guaranteeing that the choice of a price is unique for the seller. ✷

An n-KB of a buyer may look as follows.

Example 3 (Buyer n-KB). Let B be a buyer agent with the n-KB KB = 〈P rB , P cB , HB, N ≺ B 〉 where

• HB is the set of literals constructed from atoms in {maker A,maker B,maker C,made in L}.
• P rB consists of the set of facts {age = 25, student, pay cash, ¬good credit, quantity = 1} and the following

4 For a set of atoms X, {a, ¬a | a ∈ X} is the set of literals that can be built fromX.

rules

purchase ← purchase price. ← not purchase. prefer(ri, r1) ← (i > 1) prefer(r4, ri) ← (i ∈ {2, 3})

where purchase price∈{high pr, low pr, lowest pr}.

• P cB is the union of {HB +←} and the following rules:
• N ≺ B ={high pr, low pr, lowest pr} with ≺= {high pr ≺ low pr ≺ lowest pr}.

r1 : high pr

+← make A, not made in L

r2 : low pr +← make A,made in L

r3 : low pr

+← maker B

r4 : lowest pr +← maker C

The n-KB of the buyer agent is different from that of the seller. It represents information about the buyer (e.g., a student, age 25) and his/her goal (e.g., quantity = 1). Naturally, the buyer has a different priority in its negotiated atoms: he/she prefers to pay the lowest price.

Again, we can check that (P rB , P cB ) is consistent, and hence, KB is a consistent n-KB. ✷

We will now define various notions that will allow us to formalize a negotiation protocol between two agents. We start with the notion of a proposal. Intuitively, the notion of a proposal must be able to capture utterances like the following:

• (Seller) I would like to sell you this product with the high pr.
• (Buyer) I can afford the high pr if it is made by maker A and it is not manufactured in L (i.e., not made in L).
• (Seller) We do have the product of maker A and it is not manufactured in L (made in L) but you need to be a student and pay in cash to get low pr.

· etc.

Each utterance usually contains some properties of the goal and the conditions for their acceptance. We therefore define a proposal as follows.

Definition 2 (Proposal). Let K = 〈P r , P c ,H,N ≺〉 be an n-KB of an agent, say A, and G be a set of goals G ⊆ N ≺. Let M be an answer set of (P r ∪Goal(G), P c ), S = M ∩H, and R ⊆ M \ H.

We call 〈G, S〉 a proposal for G by A (w.r.t. K and M) and 〈G, S, R〉 an extended proposal for G by A (w.r.t. K and M). α(K, G) denotes the set of all possible proposals for G by A w.r.t. K.

Intuitively, a proposal 〈G, S〉 states that the goal of A is to negotiate for G and the reason that A proposes the goal G is that he/she has a supporting argument for it, in which he/she assumes S to be true. An extended proposal provides further information supporting the goal G. We refer to G and S as goal and support of 〈G, S〉. In the following, a proposal (an extended proposal) for G by A w.r.t. K and M is often shortened to a proposal (an extended proposal) for G by A when K is clear from the context and the presence of M is unimportant for our discussion.

Observe that the semantics of a CR-program requires that the set of cr-rules to be used in the construction of its answer sets is minimal. The next proposition is obvious.

Proposition 1. If 〈G, S〉 is a proposal w.r.t. K then there exists no other proposal 〈G, S′ 〉 w.r.t. K such that S′ ⊊ S.

Example 4. For S (Exp. 2), 〈{high pr}, ∅〉 and 〈{low pr}, {age≥65}〉 are two possible proposals. For B (Exp. 3), two possible proposals are: 〈{lowest pr}, {maker C}〉 and 〈{low pr}, {maker B}〉.

Given an agent A and a proposal γ = 〈G, S〉 from another agent, say B, we can see one of the following cases:

• A accepts γ: This means that γ could be a proposal of A. In doing so, A must consider whether he/she can achieve his/her goal by accepting γ and whether the assumptions in S is consistent with his/her knowledge and assumptions.
• A rejects γ: This means that there is no possible way that A can view γ as his/her proposal.
• A sees some alternative proposals for the goal of γ, yet γ is not suitable for A, i.e., A considers γ a negotiatable proposal.

This leads us to the following definition.

Definition 3 (Acceptable/Rejectable/Negotiatable Proposal). Let K = 〈P r , P c ,H,N〉 be an n-KB and γ = 〈G, S〉 be a proposal from another agent. Let Q = (P r ∪ Goal(G), P c ).

• γ is acceptable w.r.t. K if Q has an answer set M such that M ∩ H = S ∩ H and M ∪ S is consistent.
• γ is rejectable if Q is inconsistent.
• γ is negotiatable, otherwise.

Intuitively, Q encodes the set of possible proposals for G by the agent with the n-KBK. Thus, if Q is inconsistent then the proposal is rejectable. γ is acceptable if Q has an answer set M (representing a proposal for G w.r.t. K) such that M is consistent with S and M ∩ H = S ∩ H. The first condition is needed since a negotiated item is acceptable to both parties only if their supports are consistent. The second condition implies that both proposals need to use the same set of shared assumptions as well. This is necessary mainly because of the requirement used in the definition of an answer set of CRprograms. The third item of the definition is clear: a proposal is negotiatable if it is neither acceptable nor rejectable.

Let K be an n-KB and Γa(K), Γn(K), and Γr(K) be the set of proposals that are acceptable, negotiatable, and rejectable w.r.t. K, respectively. It is easy to see

Proposition 2. Let K be an arbitrary n-KB. Then, Γa(K), Γu(K), and Γr(K) are pairwise disjoint. Furthermore, γ ∈ Γa(K) ∪ Γu(K) ∪ Γr(K) for every proposal γ.

We illustrate the above definitions in the next example.

Example 5. Consider KS from Example 2. We have that

• 〈{high pr}, ∅〉 is acceptable w.r.t. KS since (P r S ∪ Goal({high pr}), P c S ) has an answer set M, M ∩ HS = ∅.
• 〈{low pr}, ∅〉 is a negotiatable proposal w.r.t. KS. There are three answer sets of (P r S ∪Goal({low pr}), P c S ): M1 contains the set of assumptions {age ≥ 65}, M2 contains {student, good credit}, and M3 contains {student, pay cash}. None of these answer sets satisfies the conditions in the first Item of Definition 3.
• 〈{lowest pr}, {quantity = 1}〉 is a rejectable proposal w.r.t KS. The only answer set of (P r S ∪

Goal({lowest pr}), P c S ) contains quantity≥100 which contradicts with quantity=1. ✷

4 Negotiation Using n-KBs: Keeping the Goal

We will now present a model of negotiation between two parties A and B who use n-KBs KA and KB respectively in their negotiation. We assume that (i) KA and KB, the n-KBs of A and B, respectively, share the same language; (ii) Agents are willing to accept new assumptions during their negotiations as long as they do not cause inconsistency in their n-KBs. (iii) Agents do not provide wrong assumptions as explanation for not accepting a proposal, i.e., they are honest.

One of the most important questions that an agent has during a negotiation is what can he/she do about a current proposal, say 〈G, S〉 directed to him/her by another agent. Naturally, the agent can either accepts, rejects, or responds by putting forward a new proposal. In doing so, Definition 3 should be used. However, Definition 3 does not provide an answer for the third case, when the agent needs to respond by a new proposal. In the next definition, we address this issue. As we expect that agents will negotiate in more than one rounds and in each round, an agent, besides his/her proposal, could indicate some facts, say R, that cannot be accepted by him/her. As such, a response will be defined given an extended proposal. For a set of literals R and the n-KB K = 〈P r , P c ,H,N ≺〉, by K ⊖ R we denote the n-KB 〈P r , P c , H\lit(R), N ≺〉, which is obtained from K by eliminating the literals constructible from R from the set of assumptions of K. Observe that any proposal w.r.t. K ⊖ R cannot contain an assumption belonging to lit(R).

Definition 4 (Response). Let KA=〈P r , P c ,H,N ≺〉 be an n-KB of an agent A and ωB=〈G, S, R〉 be an extended proposal by B w.r.t. its n-KB KB. A response to ωB by A w.r.t. KA is an extended proposal by A and is defined as follows.

• If 〈G, S〉 is acceptable w.r.t. KA⊖R, then the response is 〈⊤, ∅, ∅〉, representing accept.
• If 〈G, S〉 is rejectable w.r.t. KA⊖R, then the response is 〈⊥, ∅, ∅〉, representing reject.
• If 〈G, S〉 is negotiatable w.r.t. KA ⊖ R, then a response is an extended proposal 〈G, S′ , F〉 by A w.r.t. KA ⊖ R for which there exists an answer set M of (P r ∪ Goal(G), P c \ lit(R)) such that
• S′ = M ∩ H.
• {¬l | ¬l ∈M, l ∈ S} ⊆ F ⊆ {¬l | l ∈ S \H}.

We say that the response is constructive if it is either 〈⊤, ∅, ∅〉, 〈⊥, ∅, ∅〉, or satisfying that F = ∅ implies that S ⊆ M.

By β(KA, 〈G, S,R〉) we denote the set of all responses to 〈G, S, R〉 from A w.r.t. KA.

We assume that R contains literals that should not be considered by A. Therefore, the response is computed w.r.t. the n-KBKA⊖R. Under this assumption, the first two items are straightforward but the last item deserves some explanations. Clearly, a response should be an extended proposal by A w.r.t. KA⊖R. Furthermore, it should contain information that supports A's new proposal and contradicts with the assumptions made by B. This leads to the construction of 〈G, S′ , F〉 with the proposed properties.

Example 6. Consider ω1B = 〈{low pr}, {maker B}, ∅〉. This is an acceptable proposal w.r.t. KB and is a negotiatable proposal w.r.t. KS. The seller has three possible responses:

ω1S =〈{low pr}, {age ≥ 65}, {¬maker B}〉 ω2S =〈{low pr}, {student, good credit}, {¬maker B}〉 ω3S =〈{low pr}, {student, pay cash}, {¬maker B}〉

The three responses correspond to the answer sets M1, M2, and M3 in Example 5. Observe that ¬maker B is a fact in KS and maker B is an assumption in ω1B . ✷

We will now define the notion of a negotiation.

Definition 5 (Negotiation). Let A and B be two agents and KA and KB be their n-KBs respectively. A negotiation between A and B for G, starting with A, is a possible infinite sequence of extended proposals ω1, . . . , ωn, . . . where ωi = 〈Gi, Si, Fi〉 and

• ω1 = 〈G, S, ∅〉 and 〈G, S〉 ∈ α(KA, G).
• ωi+1 ∈ β(Ki-1, ωi) for every i > 1 where
• K1 = KA and K2k+1 = K2k-1 ⊖ F2k for k > 0; and
• K0 = KB and K2k+2 = K2k ⊖ F2k+1 for k ≥ 0.

A negotiation ends at i if ωi is either 〈⊤, ∅, ∅〉 or 〈⊥, ∅, ∅〉.

A negotiation is a series of responses between two agents, who, in alternation, takes into consideration the other's response and puts forward a new response, which is either accept (〈⊤, ∅, ∅〉), reject (〈⊥, ∅, ∅〉), or a new proposal with explanations why the last proposal (of the other agent) were not acceptable to him/her.

Definition 6 (Un/Successful Negotiation). A negotiation is successful (resp. unsuccessful) if it is finite and ends with (K, 〈⊤, ∅, ∅〉). (resp. (K, 〈⊥, ∅, ∅〉)). A negotiation is constructive if it contains only constructive responses.

Some negotiations between the buyer B (Example 3) and the seller S (Example 2) are given next.

Example 7. The following is an unsuccessful negotiation.

S : 〈{lowest pr}, {registered, quantity ≥ 100}, ∅〉 B : 〈{lowest pr}, {maker C}, {quantity = 1}〉 S : 〈⊥, ∅, ∅〉

This corresponds to the following:

• (Seller): I can offer you the lowest price if you register and buy at least 100 units.
• (Buyer): How about if it is frommaker C, but anyway I would only buy one unit.
• (Seller): Sorry, I could not offer it at this time. ✷

Example 8. The following is a successful negotiation.

B1 : 〈{low pr}, {maker B}, ∅〉

S1 : 〈{low pr}, {age ≥ 65}, {¬maker B}〉 B2 : 〈{low pr}, {maker A,made in L}, {age = 25}〉 S2 : 〈{low pr}, {student, good credit}, ∅〉 B3 : 〈{low pr}, {maker A,made in L}, {¬good credit}〉 S3 : 〈{low pr}, {student, pay cash}, ∅〉 B4 : 〈⊤, ∅, ∅〉

S1 responds to B1 and indicates that he/she cannot assume maker B (as ¬maker B is a fact in KS). The seller wants to offer low pr to the buyer but assumes that age ≥ 65. This assumption does not work well for the buyer as age = 25 is true in KB. Hence, the buyer puts forwards another proposal (B2). This time, the assumptions made by the buyer are not conflict with KS but the seller requires a new set of assumptions (S2). The negotiation continues until the buyer accepts the offer and agrees to pay by cash. ✷

We will show next that if the agents are constructive in their negotiation then their negotiation will eventually terminate. Proof relies on the fact that agents accumulate assumptions and the n-KBs are finite and is omitted to save space.

Theorem 1. Every constructive negotiation is finite.

A negotiation represents one possible way for two agents to reach an agreement (or disagreement). In the course of reaching an agreement, two agents might have different alternatives. The notion of a negotiation tree, to be defined next, will account for all possible negotiations for a goal between two agents. We will make use of the well-known notation of a tree. By the level of a node in a tree we mean the number of links lying on the path connecting the root to the node. Also, for a response ω = 〈G, S, F〉, we use ω.G, ω.S, and ω.F to denote G, S, and F respectively.

Definition 7 (Negotiation Tree). Let A and B be two agents with the n-KB KA and KB respectively. A negotiation tree between A and B for G, starting with A, is a labeled tree TA,B,G where

• the root of TA,B,G is G;
• every child of G has the label of the form (KA, 〈G, S, ∅〉) where 〈G, S〉 ∈ α(KA, G);
• if η = (KA, ω) is a node at level 1, then every child of η has the label of the form (KB, ω′ ) where ω′ ∈ β(KB , ω);
• if η = (K, ω) is a node at level i, i ≥ 2, whose parent has the label (K′ , ω′ ), then every child of η has the label of the form (K′ ⊖ ω.F, ω′′ ) where ω′′ ∈ β(K′ , ω); and
• (K, 〈⊤, ∅, ∅〉) and (K, 〈⊥, ∅, ∅〉) do not have children.

We classify negotiation tree as follows.

Definition 8 (Classification of Negotiation Tree). A negotiation tree is finite if it has finite number of nodes; it is successful if it has a leaf whose label is of the form (K, 〈⊤, ∅, ∅〉); and it is unsuccessful if all of its leaves have a label of the form (K, 〈⊥, ∅, ∅〉).

The notion of constructive negotiation is extended to negotiation tree as follows.

Definition 9 (Constructive Negotiation Tree). A negotiation tree is constructive if for every node η = (K, ω) at the level i ≥ 2, whose parent has the label (K′ , ω′ ), the set {ω′ | (K, ω′ ) is a child of η} consists of all and only constructive responses to 〈ω.G, ω.S〉 w.r.t. K′ ⊖ ω.F .

We can prove the following theorem.

Theorem 2. Every constructive negotiation tree is finite.

Algorithm 1 allows us to predict whether or not a successful negotiation for a goal G between A and B exists. Using Theorems 1-2, we can show that Algorithm 1 always terminates. This algorithm can be used in developing for a negotiation protocol in the style presented in [Kakas and Moraitis, 2006]. We omit this here due to space limitation.

5 Negotiation for the Best Possible Result

A negotiation tree details possible negotiations between two agents who maintain their goal during the negotiation. In reality, agents might change their goals during the negotiation. As it turns out, this can be easily accommodated in our framework. To do so, we only need to introduce the notion of a relaxation (or strengthening) of a goal.

Definition 10 (Relaxation/Strengthening). Let K = 〈P r , P c ,H,N ≺〉 be an n-KB and G and G′ be two set of literals G,G′ ⊆ N ≺. We say that G′ is a relaxation of G (or G is a strengthening of G′ ) if either G′ ⊊ G or G′ ̸= G and for every l ∈ G′ \G there exists some l′ ∈ G such that l ≺ l′ .

A goal change is either a relaxation or a strengthening of the goal. With the introduction of a goal change, Definitions 4, 5, 7, and Algorithm 1 can be modified to allow for responses that take into consideration a new goal. Space limitation prevents us from giving the full details of this development but they are rather straightforward. The key idea is to consider a change in a goal (i) as the starting of a new negotiation (as in Definition 5); and (ii) only necessary if the preceding negotiation leads to a rejection by either agent. Theorems 1, 2, and the termination of the modified algorithm can be proved accordingly.

6 Discussion and Conclusion

We formalize negotiation using CR-Prolog and define the basic concepts of negotiation using answer sets. The main features of our formalism are that it (a) includes support (as explanation) in a proposal/response; (b) can deal with incomplete information, preference, and changes in goal; (c) computes proposals/responses (and their support) on a case-bycase basis. Proposals/responses can be computed using available implementation of CR-Prolog. We provide an algorithm for predicting the result of a negotiation between two agents for a given goal. One of our immediate future goals is to develop a system for negotiated agents which rely on the available implementation of CR-Prolog.

Logic programming is used in [Chen et al., 2006]. In their framework, two agents exchange answer sets to produce a common belief set. Their goal is coordinating belief sets of two agents, and it has no mechanism of constructing new proposals. We use CR-Prolog and specify a way for computing new proposals as part of the response to a given proposal.

Our work is similar to the work in [Sadri et al., 2002; Sakama and Inoue, 2007] where abductive logic programming (ALP) is used to model negotiation. In our framework, the assumptions can be used in conjunction with predefined strategies, represented in the consistency restoring rules, to generate proposals whereas ALP uses only assumptions. The system in [Sakama, 2008] uses induction to construct proposals but does not consider preferences while ours does not use induction and considers preferences.

Finally, our work is similar in the spirit of approaches to argumentation-based negotiation (ABN) [Amgoud et al., 2006; Kakas and Moraitis, 2006; Rahwan et al., 2003] in that it considers explanations as a part of a proposal/response. The main difference between our work and ABN lies in our use of CR-Prolog, a non-monotonic logic, and ABN's logic is monotonic. Our framework does not compute explanations for accepting/rejecting a proposal in advance as in [Amgoud et al., 2006] and allows negotiators to nonmonotonically changing their belief by incoming information.

Algorithm 1 Negotiation(KA, KB, G)

Ensure: Accept/Reject Initialize NQ := [ ] {Negotiation Queue} for each 〈G, S〉 ∈ α(KA, G) do InsertFrontQueue(NQ, (KA, 〈G, S, ∅〉, KB)) end for while NQ is not empty do (K1, ω,K2) := Extract(NQ) {get 1st element} Compute Z = β(K2, ω) if 〈⊤, ∅, ∅〉 ∈ Z return Accept end if if 〈⊥, ∅, ∅〉 ̸∈ Z then for each ω ∈ Z do InsertFrontQueue(NQ, (K2, ω,K1 ⊖ ω.F)) (Deepth First) end for end if end while return Reject