*Notes taken from ‘Dialogues for Negotiation: Agent Varieties and Dialogue Sequences’ (2001), by Fariba Sadri, Francesca Toni and Paolo Torroni*

“… (The proposed solution) relies upon agents agreeing solely upon a language of negotiation, while possibly adopting different negotiation policies, each corresponding to an agent variety. Agent dialogues can be connected within sequences, all aimed at achieving an individual agent’s goal. Sets of sequences aim at allowing all agents in the system to achieve their goals…”

**1, Introduction**

… Many approaches in the area of one-to-one negotiation are heuristic-based and, in spite of their experimentally proven effectiveness, they do not easily lend themselves to expressing

**theoretically provable properties**. Other approaches present a good descriptive model, but fail to provide an execution model that can help to

**forecast the behaviour**of any corresponding implemented system…

… Note that we do not make any concrete assumption on the internal structure of agents, except for requiring that they hold

**beliefs**,

**goals**,

**intentions**and, possibly,

**resources**.

**2, Preliminaries**

2.1, A

**performative or dialogue move**is an instance of a schema tell(X, Y, Subject, T)… e.g. tell(a, b, request(give(nail)), 1)…

2.2, A

**language for negotiation**L is a (possibly infinte) set of (possibly non ground) performatives. For a given L, we define two (possibly infinte) subsets of performatives, I(L) and F(L)…, called respectively

**initial moves**and

**final moves**. Each final move is either

**successful**or

**unsuccessful**.

2.3, An

**agent system**is a finite set A, where each x in A is a ground term, representing the name of an agent, equipped with a

**knowledge base**K(x).

**3, Dialogues**

3.4, Given an agent system A, equipped with a language for negotiation L, and an agent x in A, a

**dialogue constraint**for x is a (possibly non-ground) if-then rule of the form: p(T) & C => p’(T + 1), where… The performative p(T) is referred to as the

**trigger**, p’(T + 1) as the

**next move**and C as the

**condition**of the dialogue constraint.

3.5, A

**dialogue**between two agents x and y is a set of ground performatives, {p0, p1, p2, …}, such that… A dialogue {p0, p1, … pM)… is

**terminated**if pM is a ground final move…

3.6, A

**request dialogue**wrt a resource R and an intention I of agent x is a dialogue… such that…

3.7, (

**Types of terminated request dialogues**) Let I be the intention of some agent a, and R be a missing resource in I. Let d be a terminated resource dialogue wrt R and and I, and I’ be the intention resulting from d. Then, if missing(Rs), plan(P) are in I and missing(Rs’), plan(P’) are in I’:

i) d is

**successful**if P’ = P, Rs’ = Rs \ {R};

ii) d is

**conditionally**or

**c-successful**if Rs’ /= Rs and Rs’ /= Rs \ {R};

iii) d is

**unsuccessful**if I’ = I.

Note that, in the case of c-successful dialogues, typically, but not always, the agent’s plan will change (P’ /= P).

3.8, An agent x in A is

**convergent**iff, for every terminated request dialogue of x, wrt some resource R and some intention I, the cost of the returned intention I’ is not higher than the cost of I. The cost of an intention can be defined as the number of missing resources in the intention.

**4, Properties of Agent Programs**

4.9, An agent x in A is

**deterministic**iff, for each performative p(t) which is a ground instance of a schema in L(in), there exists

**at most one**performative p’(t+1) which is a ground instance of a schema in L(out) such that ‘p(t) & C => p’(t+1)’ is in the agent program S and ‘K & p(t)’ entails C.

4.10, An agent program S is

**non-overlapping**iff for each performative p which is a ground instance of a schema in L(in), for each C, C’in S(p) such that C /= C’, then C ^ C’ = false.

(Theorem 1) If the (grounded) agent program of x is non-overlapping, then x is deterministic.

4.11, An agent x in A is

**exhaustive**iff, for each performative p(t) which is a ground instance of a schema in L(in) \ F(L), there exists

**at least one**performative p’(t+1) which is a ground instance of a schema in L(out) such that ‘p(t) & C => p’(t+1)’ is in S and ‘K & p(t)’ entails C.

4.12, Let L(S) be the set of all (not necessarily ground) performatives p(T) that are triggers in dialogue constraints:

L(S) = {p(T) | there exists ‘p(t) & C => p’(t+1)’ in S}. (Obviously, L(S) is a subset of L(in)). Then, S /= {} is

**covering**iff for every performative p which is a ground instance of a schema in L(in), the disjunction of C’s in S(p) is ‘true’ and L(S) = L(in) \ F(L).

(Theorem 2) If the (grounded) agent program of x is covering, then x is exhaustive.

**5, Agent Varieties: Concrete Examples of Agent Programs…**

**6, Dialogue Sequences**

6.13, A

**sequence of dialogues**s(I) wrt an intention I of an agent x with goal(G) in I is an ordered set {d1, d2, …, dn, …}, associated with a sequence of intentions I1, I2, …, In+1, … such that…

6.14, A sequence of dialogues {d1, d2, …, dn} wrt an initial intention I of an agent x and associated with the sequence of intentions I1, I2, …, In+1 is

**terminated**iff there exists no possible request dialogue wrt In+1 that x can start.

6.15, (Success of a dialogue sequence) A terminated sequence of dialogues {d1, d2, …, dn} wrt an initial intention I of an agent x and associated with the sequence of intentions I1, I2, …, In+1 is

**successful**if In+1 has an empty set of missing resources; it is

**unsuccessful**otherwise.

6.16, Given an initial intention I of agent x, containing a set of missing resources Rs, the

**agent dialogue cycle**is the following…

(Theorem 3) Given an agent x in A, if x’s agent dialogue cycle returns ‘success’ then there exists a successful dialogue sequence wrt the initial intention I of x.

(Theorem 4) Given an agent x with intention I, and a successful dialogue sequence s(I) generated by x’s dialogue cycle, if x is convergent, then the number of dialogues in s(I) is bounded by m.|Rs|, where missing(Rs) is in I and |A \ {x}| = m, A being the set of agents in the system.

**7, Using Dialogue Sequences for Resource Reallocation**

7.17, (

**Resource reallocation problem**– rrp)

Given an agent system A, with each agent x in A equipped with a knowledge base K(x) and an intention I(x),

- the

**rrp for an agent**x in A is the problem of finding a knowledge base K’(x), and an intention I’(x) (for the same goal as I(x)) such that missing({}) is in I’(x).

- the

**rrp for the agent system**A is the problem of solving the rrp for every agent in A.

A rrp is solved if the required (sets of) knowledge base(s) and intention(s) is (are) found.

(Theorem 5) (

**Correctness of the agent dialogue cycle wrt the rrp**) Let A be the agent system, with the agent programs of all agents in A being convergent. If all agent dialogue cycles of all agents in A return ‘success’ then the rrp for the agent system is solved.

7.18, Let A be an agent system consisting of n agents. Let R(A) be the union of all resources held by all agents in A, and R(I(A)) be the union of all resources needed to make all agents’ initial intentions I(A) executable. A is

**weakly complete**if, given that R(I(A)) is a subset of R(A), then

**there exist**n successful dialogue sequences, one for each agent in A, such that the intentions I’(A) returned by the sequences have the same plans as I(A) and all have an empty set of missing resources.

**8, Conclusions…**

## No comments:

Post a Comment