16, Dialogues for Negotiation

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…