# Trust in complex actions (ECAI 2010)

Julien Bourdon, Guillaume Feuillade, Andreas Herzig, Emiliano Lorini

## ► To cite this version:

Julien Bourdon, Guillaume Feuillade, Andreas Herzig, Emiliano Lorini. Trust in complex actions (ECAI 2010). 19th European Conference on Artificial Intelligence (ECAI 2010), Aug 2010, Lisbon, Portugal. pp.1037-1038, 10.3233/978-1-60750-606-5-1037. hal-03470308

HAL Id: hal-03470308

https://hal.science/hal-03470308

Submitted on 13 Dec 2021

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Trust in complex actions

Julien Bourdon<fnref n="1" /> and Guillaume Feuillade and Andreas Herzig and Emiliano Lorini<fnref n="2" />

## 1 Introduction

Recently Herzig, Lorini et al. undertook a logical analysis of the definition of trust proposed by Castelfranchi and Falcone (C&F henceforth) [3, 4]. They defined the predicate $Trust_0(i, j:a, \varphi)$ (agent $i$ trusts agent $j$ to do action $a$ in order to achieve $i$'s goal $\varphi$) as follows:<fnref n="3" />

$$ \text{Goal}(i, \varphi) \wedge \text{Bel}_i(\text{CExt}(i:a) \wedge \text{Int}(i:a) \wedge \text{Res}(i:a, \varphi)) $$

$\text{Goal}(i, \varphi)$ means that $i$ has the goal that $\varphi$; $\text{CExt}(i:a)$ are the external conditions (conditions on the world): $j$ is capable to perform $a$; $\text{Int}(i:a)$ are the internal conditions (conditions on the agent's mental state): $j$ is willing to perform $a$; and $\text{Res}(i:a, \varphi)$ links the conditions on the agent's mental state with those on the world: $j$ has the power to achieve $\varphi$ by doing $a$.<fnref n="4" /> They then defined the predicates $\text{CExt}(j:a)$, $\text{Int}(j:a)$ and $\text{Res}(j:a, \varphi)$ in terms of the concepts of belief, choice, action and time. Both C&F and Herzig, Lorini et al. only considered trust in the atomic action of another agent and did not consider trust in complex actions where the elements in the complex action are atomic actions of different agents.

In the context of services architecture, some provider agents publish atomic services; however, when a user needs to implement a more complex business process, it must chain service calls according to a specific workflow structure. Automating the service calls is called service composition: given the business process to implement, the control flow has to be computed in order to guarantee that the goal of the service caller is satisfied. Since services are provided by agents, users may trust some agents for certain actions but not for other actions which they deem critical, usually depending on the nature of the information they have to send to this agent for the service action to perform the action. In the literature (e.g. [5]), service selection for composition assumes the existence of a central authority guaranteeing the non-functional properties of the services. In practice such an authority might not exist (cf. e.g. P2P networks [6]), or may not itself be trustworthy. A model for trust in the services world, allows to express composition objectives as dynamic logic formulas with a trust component. The service composition problem would then reduce to the satisfaction of such a formula. This method would ensure that the composition is correct and compatible with the beliefs of the user, thus ensuring a trustworthy sequence of service call for achieving the goal of the user.

The details are presented in the extended version of the paper [1].

## 2 A logical language with complex actions

We recall the logical framework of [3, 4], that we extend towards complex actions. Given a set of propositional variables $Atm$, a set of agents $Agt$ and a set of atomic actions $Act$, complex formulas $\varphi$ and complex actions $\alpha$ are defined by the following BNF:

$$ \varphi ::= \begin{array}{l} p \mid \neg \varphi \mid \varphi \wedge \varphi \mid \text{Bel}_i \varphi \mid \text{Ch}_i \varphi \mid \text{Feasible}_\alpha \varphi \\ \qquad \text{Happens}_\alpha \varphi \mid \text{F}\varphi \end{array} $$

$$ \alpha ::= \begin{array}{l} i:a \mid \alpha; \alpha \mid \alpha+\alpha \mid \varphi? \mid \alpha^* \end{array} $$

where $p$ ranges over $Atm$, $i$ ranges over $Agt$, and $a$ ranges over $Act$. $\text{Bel}_i \varphi$ reads “$i$ believes that $\varphi$”; $\text{Ch}_i \varphi$ reads “$i$ chooses that $\varphi$”; $\text{Feasible}_\alpha \varphi$ reads “there is a possible execution of $\alpha$ after which $\varphi$ is true”; $\text{Happens}_\alpha \varphi$ reads “$\alpha$ happens, and $\varphi$ is true afterwards”; and $\text{F}\varphi$ reads “$\varphi$ will eventually be true”.

The atomic action $i:a$ reads “$i$ performs $a$”; the complex action $\alpha_1$; $\alpha_2$ reads “do $\alpha_1$ and then $\alpha_2$”; $\alpha_1+\alpha_2$ reads “choose nondeterministically between $\alpha_1$ and $\alpha_2$”, where the choice is understood to be up to the environment, and not up to the agents performing $\alpha_1$ and $\alpha_2$; $\varphi$? reads “if $\varphi$ is true then continue, else fail”; and finally, $\alpha^*$ reads “do $\alpha$ an arbitrary number of times”.

We define $\text{After}_\alpha \varphi$ to be an abbreviation of $\neg \text{Feasible}_\alpha \neg \varphi$. Moreover we have the following standard program constructions:

$$ \begin{array}{lclcl} \text{skip} & \stackrel{\text{def}}{=} & \top? & & \\ \text{fail} & \stackrel{\text{def}}{=} & \bot? & & \\ \text{if } \varphi \text{ then } \alpha_1 \text{ else } \alpha_2 & \stackrel{\text{def}}{=} & (\varphi?; \alpha_1) + (\neg \varphi?; \alpha_2) & & \\ \text{while } \varphi \text{ do } \alpha & \stackrel{\text{def}}{=} & (\varphi?; \alpha)^*; \neg \varphi? & & \end{array} $$

## 3 Trust about complex actions

We now generalize the definition of (occurrent) trust about atomic actions of [3, 4] to trust about complex actions and study its constituents. Among all possible complex actions we here only consider deterministic actions [2]: actions built with “skip”, “fail”, “;”, “if $\varphi$ then $\alpha_1$ else $\alpha_2$”, and “while $\varphi$ do $\alpha$”. Their BNF is:

$$ \alpha ::= \begin{array}{l} i:a \mid \text{skip} \mid \text{fail} \mid \\ \qquad \alpha; \alpha \mid \text{if } \varphi \text{ then } \alpha \text{ else } \alpha \mid \varphi? \mid \text{while } \varphi \text{ do } \alpha \end{array} $$

We therefore do not consider nondeterministic composition and iteration in our analysis of trust in complex actions. Note that tests $\varphi$? can be defined as if $\varphi$ then skip else fail.

Let us first recall the definition of the original trust predicate in [3, 4]. There, the goal condition $\text{Goal}(i, \varphi)$ was defined as $\text{Ch}_i \text{F}\varphi$, i.e. as $i$'s choice of futures where $\varphi$ holds. The external condition $\text{CExt}(j:a)$

<footnote n="1">¹ Kyoto University, Department of Social Informatics, Japan</footnote>

<footnote n="2">² Université de Toulouse, CNRS, IRIT, France</footnote>

<footnote n="3">³ They distinguish occurrent trust—$i$'s trust that $j$ is going to perform $a$ here and now— and dispositional trust: $i$'s trust that $j$ is going to perform $a$ whenever some suitable conditions obtain. We here consider the former.</footnote>

<footnote n="4">⁴ They used a 4-ary predicate $\text{Trust}(i, j:a, \varphi)$ instead of our ternary $\text{Trust}_0(i, j:a, \varphi)$. Moreover, their trust definition was in terms of the predicates $\text{Capable}(j:a)$, $\text{Willing}(j:a)$ and $\text{Power}(j:a, \varphi)$ instead of our $\text{CExt}(j:a)$, $\text{Int}(j:a)$ and $\text{Res}(j:a, \varphi)$. We here introduce these terms and notations because they better generalize to complex actions.</footnote>
was defined as Feasible<sub>j,a</sub> ⊤ (j:a is executable), and the internal condition CInt(j:a) as Ch<sub>j</sub>Happens<sub>j,a</sub> ⊤ (j chooses that j:a is going to occur). Finally, the power condition Res(j:a, φ) was defined as After<sub>j,a</sub>φ (φ will hold immediately after every possible performance of j:a).

## 3.1 Definition of trust

Our move from trust in atomic actions to trust in complex actions requires an adjustment of the definition of trust in a complex action:

$$ \text{Trust}(i, \alpha, \varphi) \stackrel{\text{def}}{=} \text{Goal}(i, \varphi) \wedge \text{Bel}_i(\text{CExt}(\alpha) \wedge \text{CInt}(\alpha) \wedge \text{Res}(\alpha, \varphi)) $$

where *i* is an agent, *α* is a deterministic action, and *φ* is a formula. As before, CExt and CInt stand for the external and the internal conditions in trust assessment.

Observe that trust in atomic actions involved a single trustee *j*. Here we have to account for trust in complex actions that may be performed by several agents; we therefore consider trust in a group of agents. Note also that before, the trustee *j*—which here would be a set of agents *J*— appeared explicitly in the definition of the predicate Trust. However, one may consider that *J* is implicitly already there: it is the set of agents occurring in *α*. Therefore the agent argument need not to appear as a separate argument in the definition. It remains to explain the predicates on the right hand side of the definition of trust.

## 3.2 Defining the ingredients of trust

The definition of the Goal predicate transfers straightforwardly because no action occurs in it:

$$ \text{Goal}(i, \varphi) \stackrel{\text{def}}{=} \text{Ch}_i F \varphi $$

So it remains to define CExt, CInt and Res.

The original power condition Bel<sub>i</sub>After<sub>j,a</sub>φ stipulated that *i* believes *φ* immediately results from *j*'s performance of atomic action *a*. However, consider *i*'s trust in *j*₁ and *j*₂ to perform the sequence of actions *j*₁:a₁; *j*₂:a₂ in order to achieve *i*'s goal *φ*. With respect to which goal should *i* trust *j*₁? The truster *i* typically does not bother about the direct effect of *j*₁'s action *a*₁ and is only interested in the overall effect *φ* of the complex action *j*₁:a₁; *j*₂:a₂. In other words, we have to account for the case where *φ* is not achieved immediately, but only at some time point in the future. We therefore redefine

$$ \text{Res}(\alpha, \varphi) \stackrel{\text{def}}{=} \text{After}_{\alpha} F \varphi $$

Up to now, all our definitions were directly in terms of well-defined formulas of our logic. Things are not as simple for the external condition CExt and for the internal condition CInt.

As to the external condition, CExt(α) means that the complex action α is executable whatever the other agents and nature choose to do. This means that the preconditions of α must obtain at every step of every execution of α. It follows that while CExt(α) implies Feasible<sub>α</sub> ⊤, it should not be equivalent to it. For example, the complex action (i:a+i:a'); i:b cannot be said to be executable (in the above sense) when just Feasible<sub>i:a+i:a';i:b</sub> ⊤ holds. Indeed, a situation where Feasible<sub>i:a'</sub>After<sub>i:b</sub> ⊤ is compatible with the latter formula, and if nature chooses i:a' when executing the nondeterministic i:a+i:a' then it cannot be said that Feasible<sub>i:a+i:a';i:b</sub> ⊤ is executable.

Given these considerations we recursively define CExt(α) as:

$$ \begin{align*} \text{CExt}(\text{skip}) &\stackrel{\text{def}}{=} \top \\ \text{CExt}(i:a) &\stackrel{\text{def}}{=} \text{Feasible}_{i:a} \top \\ \text{CExt}(\alpha; \beta) &\stackrel{\text{def}}{=} \text{CExt}(\alpha) \wedge \text{After}_{\alpha} \text{CExt}(\beta) \\ \text{CExt}(\text{if } \varphi \text{ then } \alpha_1 \text{ else } \alpha_2) &\stackrel{\text{def}}{=} (\varphi \wedge \text{CExt}(\alpha)) \vee (\neg \varphi \wedge \text{CExt}(\beta)) \\ \text{CExt}(\text{while } \psi \text{ do } \alpha) &\stackrel{\text{def}}{=} \text{F}\neg\psi \wedge \text{After}_{(\psi;\alpha)^*;\psi'} \text{CExt}(\alpha) \end{align*} $$

The clause for “;” makes that CExt(α) is stronger than Feasible<sub>α</sub> ⊤. As to the (internal) willingness condition, we define CInt(α) as:

$$ \begin{align*} \text{CInt}(\text{fail}) &\stackrel{\text{def}}{=} \top \\ \text{CInt}(i:a) &\stackrel{\text{def}}{=} \text{Ch}_i \text{Happens}_{i:a} \top \\ \text{CInt}(\alpha; \beta) &\stackrel{\text{def}}{=} \text{CInt}(\alpha) \wedge \text{After}_{\alpha} \text{CInt}(\beta) \\ \text{CInt}(\text{if } \varphi \text{ then } \alpha_1 \text{ else } \alpha_2) &\stackrel{\text{def}}{=} (\varphi \wedge \text{CInt}(\alpha)) \vee (\neg \varphi \wedge \text{CInt}(\beta)) \\ \text{CInt}(\text{while } \psi \text{ do } \alpha) &\stackrel{\text{def}}{=} \text{After}_{(\psi;\alpha)^*;\psi'} \text{CInt}(\alpha) \end{align*} $$

## 4 Properties of trust

First of all, we observe that our and the original definition coincide for atomic actions, except that we have relaxed the result condition: for us it suffices that the result φ obtains at some point in the future, and not immediately after the action. We therefore have Trust(i, j:a, φ) ↔ Trust<sub>0</sub>(i, j:a, Fφ).

For complex actions we are going to have reductions in terms of equivalences for the cases of skip, fail, if-then-else conditionals and while loops. For trust in sequential compositions we only give a sufficient condition.

**Theorem 1** The following formulas are valid.

* Trust(i, fail, φ) ↔ ⊥

* Trust(i, skip, φ) ↔ (Goal(i, φ) ∧ Bel<sub>i</sub>Fφ)

* (Trust(i, α, φ) ∧ Bel<sub>i</sub>After<sub>α</sub>Trust(i, β, φ)) → Trust(i, (α; β), φ)

* Trust(i, (α; β), φ) → Trust(i, α, φ)

* Trust(i, (α; β), φ) → After<sub>α</sub>(¬Goal(i, φ) ∨ Trust(i, β, φ))

* Trust(i, if ψ then α else β, φ) ↔ 
  Bel<sub>i</sub>((ψ → Trust(i, α, φ)) ∧ (¬ψ → Trust(i, β, φ)))
* Trust(i, (while ψ do α), φ) ↔ 
  Bel<sub>i</sub>After<sub>(ψ;α)^*(ψ → (CExt(α) ∧ CInt(α)))</sub> ∧ 
  Goal(i, φ) ∧ Bel<sub>i</sub>After<sub>while ψ do α</sub>Fφ ∧ Bel<sub>i</sub>F¬ψ

## REFERENCES

[1] J. Bourdon, G. Feuillade, A. Herzig, and E. Lorini. Trust in complex actions. In D. Gabbay and L. van der Torre, editors, *Proceedings of the International Workshop on Logics in Security 2010*, Copenaghen, 9-13 August, 2010. to appear.

[2] J.Y. Halpern and J. H. Reif. The propositional dynamic logic of deterministic, well-structured programs. *Theoretical Computer Science*, 27:127–165, 1983.

[3] Andreas Herzig, Emiliano Lorini, Jomi F. Hübner, and Laurent Vercouter. A logic of trust and reputation. *Logic Journal of the IGPL*, to appear.

[4] E. Lorini and R. Demolombe. Trust and norms in the context of computer security. In *Proc. of the Ninth International Conference on Deontic Logic in Computer Science (DEON’08)*, number 5076 in LNCS, pages 50–64. Springer-Verlag, 2008.

[5] E. Sirin, B. Parsia, and J. Hendler. Composition-driven filtering and selection of semantic web services. In *AAAI Spring Symposium on Semantic Web Services*, pages 129–138, 2004.

[6] Y. Wang and J. Vassileva. Trust and reputation model in peer-to-peer networks. In *Proc. of IEEE Conference on P2P Computing*, pages 150–157. IEEE Press, 2003.