A Logical Formulation for Negotiation among Dishonest Agents

1 Introduction

Negotiation has been an important research topic in multiagent systems and artificial intelligence, and several formalisms have been developed to model negotiations among agents (e.g., [Sadri et al., 2002; Kakas and Moraitis, 2006; Amgoud et al., 2007; Son and Sakama, 2009]). In real-life negotiation, it is a common practice for one to misstate their bargaining positions to gain his/her advantage over the other [Carson, 2010]. Such a bargaining tactic is effective when complete information is unavailable wrt the other party. Suppose a dialogue between a buyer b and a seller s.

• b1 : "I like a digital camera by the maker C. I want to get one that has good quality at a discount price."
• s1 : "The product A is made by C and has good quality. We provide a discounted price to students." (In reality, the seller does not know the quality of A.)
• b2 : "I am not a student."
• s2 : "The product B by the maker D is on bargain sale. It has good quality and is provided at a discount price for every customer paying in cash." (In reality, the seller knows that B is not of good quality.)
• b3 : "I do not want products by the maker D at the price."
• s3 : "If you join our mailing list, we can provide the product at the lowest price."
• b4 : "I'd like to join the list and buy it at the price." (In reality, the buyer does not want to join the list.)

∗ Partially supported by NSF grant IIS-0812267.

Tran Cao Son and Enrico Pontelli

Department of Computer Science New Mexico State University Las Cruces, NM 88003, USA {tson, epontell}@cs.nmsu.edu

In this negotiation, the seller has the goal of selling a product while the buyer wants to buy a product. Although fairly simple, the negotiation highlights several difficulties that need to be addressed in any framework for formalizing negotiation: (i) incomplete information: the seller does not know whether the buyer is a student or not at the beginning and comes to learn that the buyer is not a student only during the negotiation; (ii) dishonesty: the seller intentionally misstates the quality of the product A or B to achieve his goal, while the buyer intentionally agrees to join the mailing list only to get the deal which, he thought, is a good one; and (iii) preference and goal change: the buyer prefers a product made by the maker C but ends up buying a product made by the maker D.

There are some studies that can manage incomplete information of agents or preferences, however, few studies handle dishonesty that arises in negotiation. The goal of this paper is providing an abstraction of real-life negotiation where people may behave dishonestly. To represent incomplete information and preferences, we use abductive logic programming (ALP) [Kakas et al., 1998] and introduce the notion of abductive programs with disinformation (ALD-program). ALDprograms can represent disinformation and realize dishonest reasoning by agents. We formulate negotiation using negotiation knowledge bases represented by ALD-programs and explore various strategies used in negotiation. The proposed framework realizes the above mentioned issues in a single framework that makes our work significantly different from previously developed models of negotiation. Moreover, the use of logic programming enables to realize a platform for negotiation systems on top of the existing answer set solvers.

In the rest of this paper, we start by reviewing preferential reasoning in ALP and introduce the framework of ALDprograms in Section 2. The notions of negotiation knowledge bases and proposals are introduced in Section 3. Negotiations and strategies are formulated in Section 4. We relate our work to others and discuss future work in Section 5. Due to lack of space, we omit the proofs of propositions in this paper.

2 Dishonest Reasoning by Abductive Logic Programming

2.1 Abductive Programs with Preferences

A (logic) program consists of rules of the form:

where each ℓi (n ≥ m ≥ l ≥ 0) is a positive/negative literal of a propositional language. 1 The symbol ; represents disjunction and not is negation as failure. The left-hand side of the rule is the head, and the right-hand side is the body. Given a rule r of the above form, head(r) = {ℓ1, . . . , ℓl}. A rule with the empty head is a constraint, while a rule with the empty body is a fact. A fact ℓ ← is identified with a literal ℓ. The semantics of a program is given by the answer set semantics [Gelfond and Lifschitz, 1991]. 2

An abductive program is a pair 〈P, A〉 where P and A are (propositional) programs. Every element in A is called an abducible. An abducible a ∈ A is also called an abducible rule (resp. abducible fact) if a is a rule (resp. a fact). Without loss of generality, we assume that literals in the heads of rules of A do not occur in the heads of rules of P [Kakas et al., 1998]. Abducibles are hypothetical rules which are used to account for an observation together with the background knowledge P. A set S of literals is a belief set of 〈P,A〉 if S is a consistent answer set of P ∪ E for some E ⊆ A. An abductive program 〈P,A〉 is consistent if it has a belief set; otherwise, it is inconsistent. In what follows, we associate a name nr to each rule r and freely use the name to represent the rule. 3

When multiple sets of abducible rules can be used to generate belief sets, a preference relation among abducibles is introduced [Sakama and Inoue, 2000]. Given two abducibles n1, n2 ∈ A, P can include atoms of the form n1 < n2 meaning that n2 is preferred to n1. The relation < is a strict partial order that is transitive and asymmetric. The semantics of abductive programs with such preference relations is defined as follows. First, the relation < is extended to define preference among sets of abducible rules: for Q1,Q2 ⊆ A, Q1 is preferred to Q2 if either (i) Q1 ⊆ Q2 or (ii) there is n1 ∈ Q1\Q2 such that n2 < n1 for some n2 ∈ Q2 \ Q1 and n1 ̸< n3 for any n3 ∈ Q2 \Q1. In turn, this provides a means to compare belief sets of an abductive program 〈P,A〉; if S1 (resp. S2) is a belief set obtained from P ∪Q1 (resp. P ∪Q2), then S1 is preferred to S2 (written S2 ≪ S1) if Q1 is preferred to Q2. A belief set S of 〈P,A〉 is most preferred if there is no belief set S′ of 〈P,A〉 such that S ≪S′ .

Example 1 Consider the abductive program 〈P,A〉 where P = {← not p, not q, r ←, n2 < n1 }, A = {n1 : p ← r, n2 : q ← not p}. Then, 〈P,A〉 has two belief sets S1 = {p, r, n2 < n1} and S2 = {q, r, n2 < n1}, obtained by adding {n1} and {n2} to P, respectively. S1 is preferred to S2 and S1 is the most preferred belief set of 〈P,A〉.

2.2 Abductive Programs with Disinformation

Dishonest agents are those who use intentionally false or inaccurate information. In this paper, we consider the following two cases. First, an agent a, who believes a proposition ¬p, informs another agent b that p is true. Second, an agent a, who believes neither p nor ¬p, informs another agent b that p (or ¬p) is true. The first one is called a lie [Mahon, 2008], while the second one is called bullshit (shortly, BS) [Franfurt, 2005]. In both cases, information p brought to another agent b is false or inaccurate (in contrast to the reality as believed by the agent a). We call such p disinformation. In abductive programs, disinformation is defined as follows.

1 A rule with variables is viewed as the set of its ground instances.

2 For space limitations, we omit the definition of answer sets.

3 We omit the rule names when not needed in the discussion.

Definition 1 (Disinformation) Let 〈P,A〉 be an abductive program, and L and B be two sets of literals s.t.

• ∀l ∈ L, ¬l belongs to every belief set of 〈P,A〉;
• ∀l ∈ B, neither l nor ¬l belongs to any belief set of 〈P, A〉.

Then, D = (L, B) is called disinformation wrt 〈P, A〉. Literals in L represent lies, as their opposite facts are included in every belief set of 〈P,A〉. Literals in B represent BS, as none of them (or their negations) are present in any belief set. By the definition, L∩B = ∅. We next introduce a framework for realizing dishonest reasoning using abductive programs.

Definition 2 (ALD-program) Let 〈P,A〉 be an abductive program and D = (L,B) disinformation wrt 〈P,A〉. Let

where L¬ = {¬ℓ | ℓ ∈ L}. 4 An abductive program with disinformation (ALD-program) (wrt 〈P, A〉 and D) is defined as 〈PD, AD〉 = 〈(P \ I) ∪ Φ, A ∪ I ∪ L ∪ B〉.

Intuitively, I is a set of rules whose heads contain a literal that conflicts with lies in L. The set Φ specifies preferences over abducibles in three ways: (i) every rule in I is preferred to abducibles in A, (ii) every rule in A ∪ I is preferred to disinformation L∪B, and (iii) BS is preferred to lies. (i) represents that every rule from the background knowledge P is preferred to hypotheses in A. (ii) stands for ethics of rational agents; agents try to be honest as much as possible. Comparing lies and BS, lies are considered more sinful than BS, since lies are wrong beliefs while BS are ungrounded beliefs. (iii) represents this preference: an agent tries to keep lies as small as possible. In PD, I is removed from P because a program could become inconsistent when L is introduced to P, and the preference relations Φ are added to P. In AD, on the other hand, new abducibles are set as A plus I and disinformation L ∪ B. Observe that an ALD-program 〈PD,AD〉 with D = (∅, ∅) reduces to the original abductive program 〈P,A〉. Because 〈PD,AD〉 is also an abductive program, its belief sets and their preference relations are defined as before.

Proposition 1 Let 〈P,A〉 be an abductive program and D disinformation wrt 〈P,A〉. If S is a (most preferred) belief set of 〈P,A〉, then S∪Φ is a (most preferred) belief set of the ALD-program 〈PD, AD〉.

If 〈P,A〉 is consistent, then 〈PD,AD〉 is also consistent. On the other hand, an inconsistent abductive program could recover consistency using disinformation.

Example 2 Consider the abductive program 〈P,A〉 where P = { ← not q, q ← p, r, ¬p ←}, A = {r}, and disinformation D = ({p}, {q}) wrt 〈P, A〉. The ALD-program 〈PD,AD〉 then becomes PD = {← not q, q ← p, r, n2 < n1, n3 < n1, n4 < n1, n3 < n2, n4 < n2, n3 < n4 } and AD = {n1 : ¬p, n2 : r, n3 : p, n4 : q }. Here,

4 We assume ¬¬a = a to represent the atom a.

〈P, A〉 is inconsistent, while 〈PD, AD〉 has the most preferred belief set {q} ∪ Φ. Here, bullshit q is used in creating the belief set. Note that {p, q, r} ∪Φ is also a belief set but it is not a preferred one as it uses a lie p.

3 Knowledge Bases and Proposals

3.1 Negotiation Knowledge Bases

A knowledge base for negotiation is expected to serve as a means for an agent to create his/her proposals/responses in negotiation, and to decide whether he/she should accept/reject a proposal. To this end, it must encode an agent's beliefs, rules for negotiation with their preferences, possible assumptions about the other agent, and possible information that he/she could behave dishonestly. To model this, we introduce negotiation knowledge bases using ALD-programs.

Definition 3 (Negotiation KB) Given an abductive program 〈P,A〉 and disinformation D = (L,B) wrt 〈P,A〉, a negotiation knowledge base (NKB) is defined as a tuple K = (Π,H,N ≺) such that:

• Π = 〈PD, AD〉 is an ALD-program wrt 〈P, A〉 and D.
• H is a set of literals (called assumptions) s.t. H ⊆ A.
• N ≺ is a set of literals (called negotiation conditions) associated with a strict partial order ≺ on its elements.

An NKB K is consistent if Π is consistent.

Π represents an agent's domain-specific knowledge, goals and preferences with disinformation. H represents assumptions about the other agent that is unknown at the beginning of a negotiation. N ≺ specifies desired outcomes in a negotiation. p≺q means that q is preferred to p. 5 For simplicity, we often write N ≺ = {p ≺ q ≺ r} if p ≺ q and q ≺ r hold over the set N ≺ = {p, q, r}. Since an ALD-program serves as a means for an agent to generate arguments in negotiation, Π is assumed to be consistent.

We now present two NKBs, one for a seller and one for a buyer, describing the agents addressed in the introduction.

Example 3 Suppose a seller agent s, who has the abductive program 〈Ps, As〉 and disinformation Ds such that

• Ps = {sale ← prodA, price1, sale ← prodB, price2, ← not sale, makC ← prodA, makD ← prodB, ¬qualB ← prodB, bargain← prodB, prodA ←, prodB ←, ni < n1, n4 < nj, ← high, low, ← high, lowest, ← low, lowest } where price1 ∈ {high, low}, price2 ∈ {low, lowest, high}, i ∈ {2, 3, 4}, and j ∈ {2, 3}. As = {n1 : high, n2 : low ← student, n3 : low ← bargain, cash, n4 : lowest ←mailing, cash, n5 : student, n6 : cash, n7 : mailing }. Ds = (Ls, Bs) = ({qualB}, {qualA}).

Here, prod, qual and mak mean product, quality, and maker, respectively. Ps states features about products and sales conditions, together with preferences among abducibles. As specifies different pricing scenarios. (n1) Any customer buying a product with high is accepted. (n2) Students are entitled to low. (n3) low is also applied to bargain products and for every customer paying in cash. (n4) A special discount lowest is applied to a customer who subscribes to the shop's mailing list and purchases the product in cash. The seller intends to claim that both products A and B are of good quality, if needed. This is represented by Ds in which the seller would lie about qualB and bullshit about qualA.

5 We distinguish ≺ from < that is defined over abducibles.

The seller agent then constructs his/her NKB Ks = (Πs, Hs, N ≺ s ) as

• Πs = 〈P sD ,AsD 〉 with P sD = (Ps \ {n8}) ∪ {ni < n8 | i = 1, . . . , 7} ∪ {nh < nk | k = 1, . . . , 8, h = 9, 10} ∪ {n9 < n10} where n8 : ¬qualB ← prodB, n9 : qualB, n10 : qualA and AsD = As ∪ {n8} ∪ Ls ∪ Bs.
• Hs = {student, cash, mailing }.
• N ≺ s = { lowest ≺ low ≺ high }.

N ≺ s indicates that high is preferred to low and lowest. It is easy to see that Πs is consistent so Ks is consistent.

Example 4 Suppose a buyer agent b, who has the abductive program 〈Pb, Ab〉 and disinformation Db such that

• Pb = {purchase ← prodX, qualX, price3, ← high,
• ← not purchase, ¬student ←, cash ←,
• ← low, lowest, n2 < n1, n3 < n2, n3 < n1 }

where X ∈ {A, B} and price3 ∈ { low, lowest }.

• Ab = {n1 : lowest ←makC, n2 : lowest ←makD, n3 : low ←makC, n4 : qualA, n5 : qualB,

n6 : makC, n7 : makD, n8 : prodA, n9 : prodB }.

Db = (Lb, Bb) = (∅, {mailing}).

The buyer does not care about the mailing list of the seller but could pretend to join it if it works to his/her advantage. Using 〈Pb,Ab〉 and Db, the buyer agent constructs his/her NKB Kb = (Πb, Hb, N ≺ b ) as

• Πb = 〈P bD ,AbD 〉 with P bD = Pb ∪ {n10 < nk | k = 1, . . . , 9} where n10 : mailing and AbD = Ab ∪ Lb ∪ Bb.
• Hb = { n4, n5, n6, n7, n8, n9}.
• N ≺ b = { low ≺ lowest }.

It is easy to check that Kb is also consistent.

3.2 Proposals and Acceptability

In building a proposal, an agent has a goal and can make assumptions about the receiver of the proposal. The agent may also decide to reveal information about his/her state-of-belief, rendering some conditions on the feasibility of the proposal. Given a set S of literals, let Goal(S) = {← not ℓ | ℓ ∈ S }.

Definition 4 (Proposal) Let K = (Π,H,N ≺) be an NKB of an agent with Π = 〈PD,AD〉. For a set of literals G ⊆ N ≺, a tuple γ = (G, S,R) is a proposal wrt K if 〈PD ∪ Goal(G),AD〉 has a belief set M such that S = M ∩ H and R ⊆ M \ H. We refer to G, S, R, and M as the goal, assumptions, conditions, and support of γ, respectively. The proposal is honest if M ∩ (L ∪ B) = ∅; it is deceptive if M ∩ L ̸= ∅; and it is unreliable if M ∩ B ̸= ∅.

Intuitively, a proposal γ = (G, S,R) states that the goal of an agent is to negotiate for the objective G. The reason to put forward γ is that the agent has a support M for it. The agent indicates assumptions S that he/she has made about the receiver of γ. In addition, the agent also reveals additional information R supporting the goal G, which informs the receiver that the information in R should not be violated.

Example 5 In Example 3, ({high}, ∅, {prodA}) and ({low}, {student}, {prodB}) are two honest proposals by the seller. The former states that he/she can sell prodA for the price high. The latter states that he/she can sell prodB for the price low if the customer is a student. A deceptive proposal by the seller is ({low}, {student}, {prodB, qualB}), indicating that he/she can sell prodB having good quality for low provided that the buyer is a student. The proposal is deceptive because qualB is a lie. Similarly, ({high}, ∅, {prodA, qualA}) is an unreliable proposal wrt Ks.

Next we consider the acceptability of proposals.

Definition 5 (Acceptability) Let Ka = (Π,H,N ≺) be an NKB of an agent a with Π = 〈PD, AD〉, and γb = (G, S, R) a proposal by another agent b. Then,

• γb is acceptable wrt Ka if Q = 〈PD ∪Goal(G), AD〉 has a belief set M such that S ⊆ M and M ∩ H ⊆ R. We say that γb is acceptable without disinformation if M ∩ (L ∪ B) = ∅; γb is acceptable with disinformation, otherwise.
• γb is rejectable wrt Ka if Q is inconsistent.
• γb is negotiable wrt Ka, otherwise.

Intuitively, Q encodes the possibility of satisfying b's goal G in the ALD-program Π of the agent a. If Q is inconsistent, there is no way to accept γb. γb is acceptable if Q has a belief set M such that: (i) M is compatible with the assumptions S about the agent a (S ⊆ M); and (ii) if there are assumptions M ∩H made by the agent a about the proposer b, then these must be compatible with the information R revealed by the proposer (M ∩H ⊆ R). The first condition is needed, since a negotiated goal is acceptable to both parties only if their supports agree. The second condition implies that a proposal is based on the same set of shared assumptions. A proposal is negotiable if it is neither acceptable nor rejectable. Note that when an agent considers a proposal acceptable or negotiable, he/she may use disinformation included in his/her NKB.

Example 6 For Ks and Kb from Examples 3 and 4,

• ({high}, {prodA, qualA}, ∅) is acceptable with disinformation wrt Ks, since 〈P sD ∪Goal({high}), AsD 〉 has a belief set M containing high, prodA, and qualA. Any belief set that allows the seller to accept this proposal contains disinformation qualA.
• ({low}, {prodB,makD, qualB}, ∅) is a negotiable proposal wrt Ks, since 〈P sD ∪ Goal({low}), AsD 〉 has a belief set containing its assumptions but requires at least one of the sets {student} or {cash}.
• ({high}, ∅, {prodA,makC, qualA}) is a rejectable proposal wrt Kb because 〈P bD ∪ Goal({high}),AbD 〉 has no belief set containing high.

Let ΓAK , ΓNK , and ΓRK be the sets of proposals that are acceptable, negotiable, and rejectable wrt an NKB K.

Proposition 2 ΓAK , ΓNK , and ΓRK are pairwise disjoint. Furthermore, γ ∈ ΓAK ∪ ΓNK ∪ ΓRK for any proposal γ.

4 Negotiation Using NKBs

4.1 Negotiation

We will now present a model of negotiation between two agents a and b who respectively use NKBs Ka and Kb that share the same language. Each agent does not assume anything related to his/her condition, so the set H of assumptions in Ka is assumed to be disjoint from the one in Kb. In negotiation, an agent a puts forward a proposal γa = (G, S, R), and the opponent b will respond with a proposal with the same structure. At the moment, a response could be an arbitrary proposal, an acceptance or a rejection of the current proposal. (We will address more sophisticated responses in Def. 13.)

Definition 6 (Response) Let Ka = (Π,H,N ≺) be an NKB of an agent a, and γb = (G, S,R) a proposal by b wrt its NKB Kb. A response to γb by a is either (i) a proposal γa = (G′ , S′ ,R′ ); or (ii) (⊤, ∅, ∅), denoting acceptance of the proposal if γb is acceptable wrt Ka; or (iii) (⊥, ∅, ∅), denoting rejection of the proposal. The set of all responses (by a wrt Ka) to a proposal γb is denoted by Res(Ka, γb).

A negotiation is a series of responses between two agents, who, in alternation, take into consideration the other agent's response and put forward a new response; this can be either accept, reject, or a new proposal that may involve explanations of why the latest proposal (of the other agent) was not acceptable. A possibly infinite sequence of responses ω1, . . . , ωi, . . . is denoted by 〈ωi〉i>0.

Definition 7 (Negotiation) A negotiation between two agents a and b, starting with a, is a possibly infinite sequence of responses 〈ωi〉i>0 where ωi = (Gi, Si,Ri) and (i) ω2k+1 is a proposal wrt Ka (k ≥ 0); (ii) ω2k is a proposal wrt Kb (k ≥ 1); (iii) ωi+1 is a response to ωi for every i ≥ 1. A negotiation ends at i if ωi = (⊤, ∅, ∅) or ωi = (⊥, ∅, ∅). When Gi ̸= Gi+2, we say that a goal change has occurred for the agent who responded ωi.

Definition 8 (Un/Successful Negotiation) A negotiation is successful (resp. unsuccessful) if it is finite and ends with ωi = (⊤, ∅, ∅) (resp. ωi = (⊥, ∅, ∅)). We call ωi-1 the accepted (resp. rejected) proposal of the negotiation.

Example 7 The negotiation dialogue between the seller s and the buyer b in the introduction is realized using NKBs of Examples 3 and 4 as follows.

• b1 : ({low}, {prodA, qualA,makC}, ∅)
• s1 : ({low}, {student}, {prodA, qualA,makC})
• b2 : ({low}, {prodA, qualA,makC}, {¬student})
• s2 : ({low}, {cash}, {prodB,makD, qualB})
• b3 : ({lowest}, {prodB,makD, qualB}, {cash})
• s3 : ({lowest}, {cash,mailing}, {prodB,makD, qualB}) b4 : (⊤, ∅, ∅).

The seller bullshits in s1 and lies in s2. The buyer bullshits in b4. A goal change has occurred at b3 (for the buyer) and s3 (for the seller).

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. All possible negotiations between two agents are represented by a negotiation tree. In what follows, the level of a node in a tree means the number of links lying on the path connecting the root to this node.

Definition 9 (Negotiation Tree) A negotiation tree between two agents a and b, starting with a, is a labeled tree Ta,b where (i) each child of the root node has the label of the form (Ka, γa,Kb) where γa is a proposal wrt Ka; (ii) if ηi = (K, ω,K′ ) is a node at the level i ≥ 1, then every child of ηi has the label of the form (K′ , ω′ ,K) where ω′ ∈ Res(K′ , ω); and (iii) nodes labeled by (K, (⊤, ∅, ∅),K′ ) or (K, (⊥, ∅, ∅), K′ ) have no children.

Each path from a node η1 of Ta,b to a leaf is a negotiation between a and b. There is a possibility of reaching an agreement if Ta,b has a finite length of path having the leaf labeled by (K, (⊤, ∅, ∅),K′ ); otherwise, no agreement is reached.

4.2 Negotiation Strategies

The previous section provides basic definitions for modeling negotiation. In practice, agents commonly employ their own strategies in a negotiation. We next formalize this notion.

Definition 10 (Strategy) Given an agent a with the NKB Ka, a negotiation strategy for a is a function F that maps a proposal γb by another agent b and a negotiation 〈ωi〉, a finite sequence ω1, . . . , ωi, to a new proposal that satisfies (i) F(γb, 〈ωi〉) ∈ Res(Ka, γb) and (ii) the sequence 〈ωi〉, F(γb, 〈ωi〉) is a negotiation.

Agents are interested in different types of strategies. For example, strategies that guarantee the termination of a negotiation, strategies that do not use disinformation, strategies that guarantee the success of a negotiation, etc. We will discuss some of these next. For two negotiations 〈ωi〉 and 〈ωj〉, we write 〈ωi〉 ✁ 〈ωj〉 if 〈ωi〉 is a proper prefix of 〈ωj〉.

Definition 11 (Observant Strategy) A strategy F is observant if F(γ, 〈ωi〉) ̸= F(γ, 〈ωj〉) for every pair of negotiations 〈ωi〉 and 〈ωj〉 such that 〈ωi〉 ✁ 〈ωj〉.

The observant strategy says an agent does not repeat the same response to the same proposal in a negotiation. If at least one agent's strategy is observant, then the negotiation will terminate. This is because an agent does not have infinitely many responses and thus the negotiation will either fail/succeed.

Proposition 3 Let a and b be two agents with strategies Fa and Fb, respectively. If either Fa or Fb is observant, then every negotiation between a and b terminates.

In practice, an agent might prefer to be honest before he/she uses disinformation in achieving his/her goals. We address some strategies that differentiate between honesty and dishonesty. In particular, strategies, which guarantee that an agent lies or BS only if he/she has no alternative, can be built using the preference relation between belief sets, since such relation favors belief sets without disinformation.

Definition 12 (Deliberate Strategy) Given a proposal γb, let Σa(γb) = {M | a belief set M (of an agent a) supports some ω ∈ Res(Ka, γb)}. Then, a strategy F is deliberate if (i) F(γb, 〈ωi〉) is supported by a most preferred belief set in Σa(γb) whenever Σa(γb) ̸= ∅; (ii) F(γb, 〈ωi〉) = (⊥, ∅, ∅), otherwise. A deliberate strategy, which is also observant, is called a best-practice strategy.

A deliberate strategy does not guarantee termination of a negotiation. However, a best-practice strategy does. Furthermore, we can observe that an agent with a best-practice strategy may accept a less preferred outcome (under ≺) of a negotiation even though he/she might obtain a more preferred outcome had he/she used disinformation. Similarly, he/she may sometimes reject a proposal even though this might be negotiable and further negotiation might yield a preferred outcome, had he/she lied or bullshitted. This can be seen in Example 7: a deliberate seller will respond to b1 with s′1 = ({low}, {student}, {prodA,makC}) rather than s1, since he/she has a belief set without disinformation (qualA) that supports s′1 . The negotiation does not reach an agreement by b4 if s3 does not include a lie qualB.

One disadvantage of the observant strategy is that it requires an agent to memorize the full history of the negotiation. We next consider a possible way to avoid this. In negotiation, an agent, who would be willing to accept rather than reach no agreement at all, needs to consider (i) the assumptions that have been made by the opponent, and (ii) the information that the opponent reveals about him/herself. As for (i), the response should identify and make explicit those assumptions that are wrong about him/herself, as far as he/she will not lie/BS on those assumptions-e.g., if the seller assumes that the buyer is a student but the buyer is not, then the buyer should identify this and inform the seller, as far as if he/she does not disguise him/herself as a student. As for (ii), the response needs to conform to this information-e.g., if the seller says that he/she does not have the product A, then the the buyer should not assume that prodA is available, even though prodA is a viable assumption in his/her KB. These considerations lead to more sophisticated responses.

Definition 13 (Conscious Response) Let Ka = (Π, H, N ≺) be an NKB of an agent a, and γb = (G, S, R) a proposal by another agent b. A conscious response to γb by a is

• (i) γa = (G′ , S′ ,R′ ) wrt Ka with a support M such that G ⪯ G′ , R ∩ H ⊆ S′ , and S¬ ∩M ⊆ R′ , where S¬ = {¬ℓ | ℓ ∈ S}, if γb is not rejectable wrt Ka; or
• (ii) γa = (G′ , S′ ,R′ ) wrt Ka with a support M such that G ̸≺ G′ and S¬ ∩M ⊆ R′ , if γb is rejectable wrt Ka; or
• (iii) (⊤, ∅, ∅), denoting acceptance of the proposal, if γb is acceptable wrt Ka; or
• (iv) (⊥, ∅, ∅), denoting rejection of the proposal.

If the proposal γb is acceptable to an agent a, then he/she could accept it (case (iii)) or attempt to negotiate for some better options (case (i)). If γb is negotiable, he/she could continue and attempt to get a better option (case (i)). If γb is rejectable, he/she could try to negotiate for something that is not as good as the current goal (case (ii)). In each case, the agent can stop with rejection (case (iv)). An agent a should generate a new proposal γa whose goal G′ depends on the goal G of the given proposal γb, whose assumptions S′ cover the conditions R stated in γb (R ∩ H ⊆ S′ ), and whose conditions R′ identify all incorrect assumptions made in γb (S¬ ∩M ⊆ R′ ). An agent, who considers preferable proposals, would require that the support for the new proposal must be preferred to any support for accepting γb.

Example 8 The proposal γs = ({low}, {cash}, {prodA, qualA, makC}) by the seller ("I can sell you the prodA, made by makC, and has good quality for low if you pay in cash") is acceptable by the buyer wrt Kb. However, the buyer could respond with the proposal γb = ({lowest}, {prodA, qualA,makC}, {cash}) ("Can I get the lowest?").

Intelligent agents also update their negotiation KBs using incoming information during negotiation.

Definition 14 (Adaptive Agent) An agent a with the NKB Ka = (Π,H,N ≺) and a strategy F is said to be adaptive if for every proposal γb = (G, S, R) by another agent b,

• F(γb, 〈ωi〉) = (G′ , S′ ,R′ ) is a conscious response to γb; and if γb is acceptable wrt Ka, then G ≺ G′ or (G′ , S′ , R′ ) = (⊤, ∅, ∅).
• a changes his/her NKB toK′a = (Π′ , H, N ≺) where Π′ = 〈PD ∪ (R ∩ (H ∪ H¬)), AD〉 after his/her response to γb.

Intuitively, an agent is adaptive if it imports information received during a negotiation into his/her NKB and keeps this information for the next round of the negotiation. Furthermore, an adaptive agent prefers to accept a proposal if a better outcome cannot be achieved. It is easy to see that if both agents are adaptive then a negotiation will terminate.

5 Discussion

Logic programming has been used for formulating negotiation by many researchers. Chen et al. [2007] use answer sets of logic programs as a means for negotiation between agents. Their goal is to coordinate answer sets of two programs, and it has no mechanism for developing proposals for a particular goal. Sadri et al. [2002] realize negotiation using abductive programs. In their framework, a program specifies a negotiation plan to achieve a goal, and the behavior of agents is operationally specified by an observe-think-act cycle. In our framework, an agent can generate proposals using abductive assumptions, and the behavior of agents is flexibly changed by strategies. Son et al. [2009] use logic programs with consistency restoring rules (CR-Prolog) to formulate negotiation. Unlike abductive programs, a CR-Prolog program considers the most preferred answer sets only. This restricts options for building proposals that are supported by less preferred belief sets (with disinformation). Any proposal/response produced by CR-Prolog is also built in our current framework, but the converse implication does not hold in general. Our work is in the same spirit as the approaches to argumentation-based negotiation (ABN) [Kakas and Moraitis, 2006; Amgoud et al., 2007], 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 abductive programs, a nonmonotonic logic, while ABN's logic is monotonic. Our framework does not compute explanations for accepting/rejecting a proposal in advance as in [Amgoud et al., 2007], and it allows negotiators to non-monotonically modify their beliefs and change proposals using incoming information. Kakas et al. [2006] introduce priorities over arguments and use abduction to seek conditions to support arguments. They do not integrate abduction and preferences as done in this paper.

It is important to note that all studies mentioned above model negotiation between honest agents, which is not always realistic. There are few studies which provide a formal logic for negotiation between dishonest agents. Zlotkin et al. [1991] study negotiation in which agents may lie. The study focuses on multi-agents in a dynamic environment, where agents act and interact to achieve their individual or cooperative goals. However, it does not provide any computational method of building (dis)honest proposals. The issue has also been discussed in the context of game theory (e.g., [Ettinger and Jehiel, 2010]). The approach differs from most of the works we have discussed so far, including our own.

In this paper, we develop an abstract framework for negotiation based on logic programming. It can deal with incomplete information, preferences, disinformation, and compute proposals and conditions on a case-by-case basis using different negotiation strategies. Proposals and responses are computed by belief sets of abductive programs, so computational complexities follow from those of abductive programs. The proposed framework has been implemented on top of the ASP-Prolog platform [Nguyen et al., 2011]. On the other hand, this paper does not argue the issue of detecting and dealing with disinformation made by a dishonest agent. The investigation of these issues is left for future work.