Information-Based Agency

1 Introduction

In this paper we introduce an agency framework grounded on information-based concepts [MacKay, 2003]. It presents an agent architecture that admits a game-theoretical reading and an information-theoretical reading. And, what is more interesting, permits a connection between these two worlds by considering negotiation as both cooperative, in the sense that all interaction involves the exchange of information, and competitive, in the sense that agents aim at getting the best they can. This approach contrasts with previous work on the design of negotiation strategies that did not take information exchange into account, but focused on the similarity of offers [Jennings et al., 2001; Faratin et al., 2003], game theory [Rosenschein and Zlotkin, 1994], or first-order logic [Kraus, 1997].

We assume that a multiagent system {α, β1, . . . , βo, ξ, θ1, . . . , θt}, contains an agent α that interacts with negotiating agents, βi, information providing agents, θj, and an institutional agent, ξ, that represents the institution where we assume the interactions happen [Arcos et al., 2005]. Institutions give a normative context to interactions that simplify matters (e.g an agent can't make an offer, have it accepted, and then renege on it). We will describe a communication language C based on an ontology that will permit us both to structure the dialogues and to structure the processing of the information gathered by agents. Agents have an internal language L used to build a probabilistic world model.

We understand agents as being built on top of two basic functionalities. First, a proactive machinery, that transforms

John Debenham

Faculty of Information Technology University of Technology, Sydney NSW, Australia debenham@it.uts.edu.au

needs into goals and these into plans composed of actions. Second, a reactive machinery, that uses the received messages to obtain a new world model by updating the probability distributions in it. Agents summarise their world models using a number of measures (e.g. trust, reputation, and reliability [Sierra and Debenham, 2006]) that can then be used to define strategies for "exchanging information" - in the sense developed here, this is the only thing that an agent can do.

We introduce the communication language in Section 2, the agent architecture in Section 3, some summary measures based on the architecture in Section 4, and some associated interaction strategies in Section 5.

2 The Multiagent System

Our agent α has two languages: C is an illocutionary-based language for communication, and L is a language for internal representation. C is described following, and L in Section 3.

2.1 Communication Language C

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 activities that agents α and β are respectively responsible for. 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 then 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 define the context that the agent has to take into account.

The communication language that α needs requires two fundamental primitives: Commit(α, β, ϕ) to represent, in ϕ, what is the world α aims at bringing about and that β has the right to verify, complain about or claim compensation for any deviations from, and Done(a) to represent the event that a certain action a1 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:

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, or code that aligns the ontological differences between the speakers needed to interpret an action a.

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:

Note the use of the institution agent ξ to report the payment.

In order to define the language introduced above that structures 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)). 2 We model ontologies following an algebraic approach [Kalfoglou and Schorlemmer, 2003] as:

An ontology is a tuple O = (C, R, ≤, σ) where C is a finite set of concept symbols (including basic data types), R is a finite set of relation symbols, ≤ is a reflexive, transitive and anti-symmetric relation on C (a partial order), and σ : R → C+ is the function assigning to each relation symbol its arity. ≤ is a traditional is-a hierarchy, and R contains relations between the concepts in the hierarchy.

The concepts within an ontology are closer, semantically speaking, depending on how far away are they 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 on nearby semantic regions is crucial to model the common sense that human beings apply in managing trading relationships. A measure [Li et al., 2003] 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 could then be defined as:

1 Without loss of generality we will assume that all actions are dialogical.

2 Usually, a set of axioms defined over the concepts and relations is also required. We will omit this here.

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 contribution of shortest path length and depth respectively.

Given a formula ϕ ∈ C in the communication language we define the vocabulary or ontological context of the formula, O(ϕ), as the set of concepts in the ontology used in it. Thus, we extend the previous definition of similarity to sets of concepts in the following way:

The following does not depend on this particular definition.

3 Agent Architecture

Agent α receives all messages expressed in C in an in-box X where they are time-stamped and sourced-stamped. A message μ from agent β (or θ or ξ) is then moved from X to a percept repository Y t where it is appended with a subjective belief function Rt (α, β, μ) that normally decays with time. α acts in response to a message that expresses a need. 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 described in Section 3.1, other messages are dealt with by α's reactive reasoning described in Section 3.2.

3.1 Proactive Reasoning

α's goal/plan machinery operates in a climate of changing uncertainty and so typically will pursue multiple sub-goals concurrently. This applies both to negotiations with a potential trading partner, and to interaction with information sources that either may be unreliable or may take an unpredictable time to respond. Each plan contains constructors for a world model Mt that consists of probability distributions, (Xi), in first-order probabilistic logic L. Mt is then maintained from percepts received using update functions that transform percepts into constraints on Mt - described in Section 3.2.

The distributions in Mt are determined by α's plans that are determined by its needs. If α is negotiating some contract δ in satisfaction of need χ then it may require the distribution Pt (eval(α, β, χ, δ) = ei) where for a particular δ, eval(α, β, χ, δ) is an evaluation over some complete and disjoint evaluation space E = (e1, . . . , en) that may contain hard (possibly utilitarian) values, or fuzzy values such as "reject" and "accept". This distribution assists α's strategies to decide whether to accept a proposed contract leading to a probability of acceptance Pt (acc(α, β, χ, δ)). For example, Pt (eval(α, β, χ, δ) = ei) could be derived from the subjective estimate Pt (satisfy(α, β, χ, δ) = fj) of the expected extent to which the execution of δ by β will satisfy χ, and an objective estimate Pt (val(α, β, δ) = gk) of the expected valuation of the execution of δ possibly in utilitarian terms. This second estimate could be derived by proactive reference to the {θi} for market data. In a negotiation α's plans may also construct the distribution Pt (acc(β, α, δ)) that estimates the probability that β would accept δ - we show in Section 3.2 how α may derive this estimate from the information in β's proposals.

α's plans may construct various other distributions such as: Pt (trade(α, β, o) = ei) that β is a good person to sign contracts with in context o, and Pt (confide(α, β, o) = fj) that α can trust β with confidential information in context o.

The integrity of percepts decreases in time. α may have background knowledge concerning the expected integrity of a percept as t → ∞. Such background knowledge is represented as a decay limit distribution. If the background knowledge is incomplete then one possibility is for α to assume that the decay limit distribution has maximum entropy whilst being consistent with the data. Given a distribution, P(Xi), and a decay limit distribution D(Xi), P(Xi) decays by:

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: Δti and Dt (Xi).

3.2 Reactive Reasoning

In the absence of in-coming messages the integrity of Mt decays by Eqn. 1. The following procedure updates Mt for all percepts expressed in C. Suppose that α receives a message μ from agent β at time t. Suppose that this message states that something is so with probability z, and suppose that α attaches an epistemic belief Rt (α, β, μ) to μ - this probability reflects α's level of personal caution. Each of α's active plans, s, contains constructors for a set of distributions {Xi} ∈ Mt together with associated update functions, Js(·), such that J Xi s (μ) is a set of linear constraints on the posterior distribution for Xi. Examples of these update functions are given in Section 3.4. Denote the prior distribution Pt (Xi) by ⃗ p, and let ⃗ p(μ) be the distribution with minimum relative entropy 3 with respect to ⃗ p: ⃗ p(μ) = argmin⃗r ∑j rj log rj pj that satisfies the constraints J Xi s (μ). Then let ⃗q(μ) be the distribu-

3 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 Pi pi - 1 = 0) is: ⃗ p = argmin⃗r Pj rj log rj qj . This may be calculated by introducing Lagrange multipliers ⃗λ: L(⃗ p, ⃗λ) = Pj 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 [Cheeseman and Stutz, 2004] and encapsulates commonsense reasoning [Paris, 1999].

A general measure of whether ⃗q(μ) is more interesting than ⃗ p is: K(⃗q(μ)‖D(Xi)) > K(⃗ p‖D(Xi)), where K(⃗x‖⃗y) = ∑j xj ln xj yj is the Kullback-Leibler distance between two probability distributions ⃗x and ⃗y.

Finally merging Eqn. 3 and Eqn. 1 we obtain the method for updating a distribution Xi on receipt of a message μ:

This procedure deals with integrity decay, and with two probabilities: first, the probability z in the percept μ, and second the belief Rt (α, β, μ) that α attached to μ.

In a simple multi-issue contract negotiation α may estimate Pt (acc(β, α, δ)), the probability that β would accept δ, by observing β's responses. Using shorthand notation, if β sends the message Offer(δ1) then α may derive the constraint: J acc(β,α,δ) (Offer(δ1)) = {Pt (acc(β, α, δ1)) = 1}, and if this is a counter offer to a former offer of α's, δ0, then: J acc(β,α,δ) (Offer(δ1)) = {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" [Debenham, 2004].

3.3 Reliability

Rt (α, β, μ) is an epistemic probability that takes account of α's personal caution. An empirical estimate of Rt (α, β, μ) may be obtained by measuring the 'difference' between commitment and enactment. Suppose that μ is received from agent β at time u and is verified by ξ as μ′ at some later time t. Denote the prior Pu (Xi) by ⃗ p. Let ⃗ p(μ) be the posterior minimum relative entropy distribution subject to the constraints J Xi s (μ), and let ⃗ p(μ′ ) be that distribution subject to J Xi s (μ′ ). We now estimate what Ru (α, β, μ) should have been in the light of knowing now, at time t, that μ should have been μ′ .

The idea of Eqn. 2, is that Rt (α, β, μ) should be such that, on average across Mt , ⃗q(μ) will predict ⃗ p(μ′ ) - no matter whether or not μ was used to update the distribution for Xi, as determined by the condition in Eqn. 3 at time u. The observed reliability for μ and distribution Xi, RtXi (α, β, μ)|μ′ , on the basis of the verification of μ with μ′ , is the value of k that minimises the Kullback-Leibler distance:

The predicted information in the enactment of μ with respect to Xi is:

that is the reduction in uncertainty in Xi where H(·) is Shannon entropy. Eqn. 5 takes account of the value of Rt (α, β, μ).

If X(μ) is the set of distributions that μ affects, then the observed reliability of β on the basis of the verification of μ with μ′ is:

If X(μ) are independent the predicted information in μ is:

Suppose α sends message μ to β where μ is α's private information, then assuming that β's reasoning apparatus mirrors α's, α can estimate It (β, α, μ).

For each formula ϕ at time t when μ has been verified with μ′ , the observed reliability that α has for agent β in ϕ is:

where Sim measures the semantic distance between two sections of the ontology as introduced in Section 2.1, and ν is the learning rate. Over time, α notes the context of the various μ received from β, and over the various contexts calculates the relative frequency, Pt (μ). This leads to an overall expectation of the reliability that agent α has for agent β:

3.4 Commitment and Enactment

The interaction between agents α and β will involve β making contractual commitments and (perhaps implicitly) committing to the truth of information exchanged. No matter what these commitments are, α will be interested in any variation between β's commitment, ϕ, and what is actually observed (as advised by the institution agent ξ), as the enactment, ϕ′ . We denote the relationship between commitment and enactment, Pt (Observe(ϕ′ )|Commit(ϕ)) simply as Pt (ϕ′ |ϕ) ∈ Mt .

In the absence of in-coming messages the conditional probabilities, Pt (ϕ′ |ϕ), should tend to ignorance as represented by the decay limit distribution and Eqn. 1. We now show how Eqn. 4 may be used to revise Pt (ϕ′ |ϕ) as observations are made. Let the set of possible enactments be Φ = {ϕ1, ϕ2, . . . , ϕm} with prior distribution ⃗ p = Pt (ϕ′ |ϕ). Suppose that message μ is received, we estimate the posterior ⃗ p(μ) = (p(μ)i)mi=1 = Pt+1 (ϕ′ |ϕ).

First, if μ = (ϕk, ϕ) is observed then α may use this observation to estimate p(ϕk)k as some value d at time t + 1. We estimate the distribution ⃗ p(ϕk) by applying the principle of minimum relative entropy as in Eqn. 4 with prior ⃗ p, and the posterior ⃗ p(ϕk) = (p(ϕk)j)mj=1 satisfying the single constraint: J (ϕ′ |ϕ) (ϕk) = {p(ϕk)k = d}.

Second, we consider the effect that the enactment φ′ of another commitment φ, also by agent β, has on ⃗ p. This is achieved in two ways, first by appealing to the structure of the ontology using the Sim(·) function, and second by introducing a valuation function.

The Sim(·) method. Given the observation μ = (φ′ , φ), define the vector ⃗t by

for i = 1, . . . ,m. ⃗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 ⃗ p(φ′ ,φ) is defined to be the normalisation of ⃗t.

The valuation method. α may wish to value ϕ in some sense. This value will depend on the future use that α makes of it. So α estimates the value of ϕ using a probability distribution (p1, . . . , pn) over some evaluation space E = (e1, . . . , en). pi = wi(ϕ) is the probability that ei is the correct evaluation of the enactment ϕ, and ⃗w : L×L → [0, 1]n is the evaluation function.

For a given ϕk, (Pt (ϕ1|ϕk), . . . , Pt (ϕm|ϕk)) is the prior distribution of α's estimate of what will be observed if β committed to ϕk, and ⃗w(ϕk) = (w1(ϕk), . . . ,wn(ϕk)) is α's evaluation over E of β's commitment ϕk. α's expected evaluation of what will be observed that β has committed to ϕk is ⃗wexp (ϕk):

for i = 1, . . . , n. Now suppose that α observes the enactment φ′ of another commitment φ also by agent β. Eg: α may buy wine and cheese from the same supplier. α may wish to revise the prior estimate of the expected valuation ⃗wexp (ϕk) in the light of the observation (φ′ , φ) to:

for some function ⃗g - the idea being, for example, that if the commitment, φ, a contract for cheese was not kept then α's expectation that the commitment, ϕ, a contract for wine will not be kept should increase. We estimate the posterior ⃗ p(φ′ ,φ) by applying the principle of minimum relative entropy as in Eqn. 4 with prior ⃗ p and ⃗ p(φ′ ,φ) = (p(φ′ ,φ)j)mj=1 satisfying the n constraints:

This is a set of n linear equations in m unknowns, and so the calculation of the minimum relative entropy distribution may be impossible if n > m. In this case, we take only the m equations for which the change from the prior to the posterior value is greatest. That is, we attempt to select the most significant factors.

4 SummaryMeasures

The measures here generalise what are commonly called trust, reliability and reputation measures into a single computational framework. It they are applied to the execution of contracts they become trust measures, to the validation of information they become reliability measures, and to socially transmitted behaviour they become reputation measures.

Ideal enactments. Consider a distribution of enactments that represent α's "ideal" in the sense that it is the best that α could reasonably expect to happen. This distribution will be a function of α's context with β denoted by e, and is PtI (ϕ′ |ϕ, e). Here we measure the relative entropy between this ideal distribution, PtI (ϕ′ |ϕ, e), and the distribution of expected enactments, Pt (ϕ′ |ϕ). That is:

where the "1" is an arbitrarily chosen constant being the maximum value that this measure may have. This equation measures one, single commitment ϕ. It makes sense to aggregate these values over a class of commitments, say over those ϕ that are in the context o, that is ϕ ≤ o:

where Ptβ (ϕ) is a probability distribution over the space of commitments that the next commitment β will make to α is ϕ. Similarly, for an overall estimate of β's reputation to α:

Preferred enactments. The previous measure requires that an ideal distribution, PtI (ϕ′ |ϕ, e), has to be specified for each ϕ. Here we measure the extent to which the enactment ϕ′ is preferable to the commitment ϕ. Given a predicate Prefer(c1, c2, e) meaning that α prefers c1 to c2 in environment e. An evaluation of Pt (Prefer(c1, c2, e)) may be defined using Sim(·) and the evaluation function ⃗w(·) - but we do not detail it here. Then if ϕ ≤ o:

and:

Certainty in enactment. Here we measure the consistency in expected acceptable enactment of commitments, or "the lack of expected uncertainty in those possible enactments that are better than the commitment as specified". If ϕ ≤ o let: Φ+(ϕ, o, κ) = {ϕ′ | Pt (Prefer(ϕ′ , ϕ, o)) > κ} for some constant κ, and:

where Pt+(ϕ′ |ϕ) is the normalisation of Pt (ϕ′ |ϕ) for ϕ′ ∈ Φ+(ϕ, o, κ),

As above we aggregate this measure for those commitments in a particular context o, and measure reputation as before. Computational Note. The various measures given above involve extensive calculations. For example, Eqn. 8 contains ∑ϕ′ that sums over all possible enactments ϕ′ . We obtain a more computationally friendly measure by appealling to the structure of the ontology described in Section 2.1, and the right-hand side of Eqn. 8 may be approximated to:

where Ptη,I (ϕ′ |ϕ, e) is the normalisation of PtI (ϕ′ |ϕ, 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 Strategies

An approach to issue-tradeoffs is described in [Faratin et al., 2003]. That strategy attempts to make an acceptable offer by "walking round" the iso-curve of α's previous offer (that has, say, an acceptability of c) towards β's subsequent counter offer. In terms of the machinery described here:

In multi-issue negotiation the number of potential contracts that satisfy, or nearly satisfy, a utilitarian strategy such as this will be large - there is considerable scope for refining the choice of response.

Everything that an agent communicates gives away information. So even for purely self-interested agents interaction is a semi-cooperative process. α's machinery includes measures of expected information gain in messages either sent to, or received from, β. For example, α can refine a strategy such as Eqn. 9 by replying to a message μ from β with μ′ that attempts to give β equitable information gain: It-1 (α, β, μ) ≈ It (β, α, μ′ ). This refinement aims to be fair in sharing α's private information. Unlike the quasiutilitarian measures, both the measure of information gain and the semantic measure (see below) apply to all messages.

The structure of the ontology is provided by the Sim(·) function. Given two contracts δ and δ′ containing concepts {o1, . . . , oi} and {o′1 , . . . , o′j } respectively, the (nonsymmetric) distance of δ′ from δ is the vector ⃗Γ(δ, δ′ ) = (dk : o′′ k )ik=1 where dk = minx{Sim(ok, o′x ) | x = 1, . . . , j}, o′′ k = sup(argminx{Sim(ok, x) | x = o′1 , . . . , o′j }, ok) and the function sup(·, ·) is the supremum of two concepts in the ontology. ⃗Γ(δ, δ′ ) quantifies how different δ′ is to δ and enables α to "work around" or "move away from" a contract under consideration.

More generally, suppose that α has selected a plan s that is attempting to select the 'best' action in some sense. Then s will construct a distribution D = (di) ∈ Mt where di is the probability that zi is the best action that α can take, and {z1, . . . , zr} are the available actions. s reduces H(D) to an acceptable level before committing itself to act - here α is an uncertainty minimising agent. s reduces the entropy of Mt by acquiring information as we now describe.

Distribution D will typically be defined in terms of other distributions. For example, the 'best' action may be defined in terms of the trustworthiness of β (Section 4), quasi-utilitarian distributions such as those described in Section 3.1, measures of information gain in Section 3.3, and measures of semantic context in Section 2.1. Suppose that D is defined in terms of {Xi}. The integrity of each Xi will develop in time by Eqn. 4. The update functions for Xi, J Xi , identify potential "entropy reducing" information that may perhaps be obtained from the information sources {θi}ti=1 . If α requests information ϕ from θj that is delivered as ϕ′ it is managed as described in Section 3.4. That section also showed how nearby observations, (φ′ , φ), may be used to update distributions, so identifying additional information that may reduce entropy.

Let M tαβ be the set of time-stamped messages that α has sent to β, and M tβα likewise both at time t. The next action that α takes in this dialogue will be to send β a message μ that is determined by its strategy. α's strategy is a function f(·) of the following form:

It takes account of the acceptability (expected utility) of proposals, the expected information gain in each communication and the semantic relationship between proposals, both as seen by itself and by β.

6 Conclusion

Information-based agency integrates in an homogeneous agent architecture the exchange of information and the negotiation of norms and contracts using a rich communication language. These agents' world models are manipulated by the agent's proactive and reactive machinery using ideas from information theory. These agents are aware of the value of the information in every utterance, the semantic relationship between utterances as well as their utilitarian value. Summary measures that generalise trust, reliability and reputation illustrate the strength of the architecture. These agents' negotiation strategies are based on three dimensions: informational, rational and semantic.

Acknowledgments Carles Sierra has been supported by the EU funded STREP project OpenKnowledge and the Spanish MEC project Webi-2. Both authors are supported by the Australian ARC Discovery Project 'The Curious Negotiator'.