Reasoning about manipulation in multi-agent systems

ABSTRACT

Selfish, dishonest or malicious agents may find an interest in manipulating others. While many works deal with designing robust systems or manipulative strategies, few works are interested in defining in a broad sense what is a manipulation and how we can reason with such a notion. In this article, based on a social science literature, we give a general definition of manipulation for multi-agent systems. A manipulation is a deliberate effect of an agent – called manipulator – to instrumentalize another agent – called victim – while making sure to conceal that effect. We present then a logical framework, called KBE, to express and reason about manipulations. Since manipulation relies on deliberate effects, KBE introduces a deliberate BIAT operator which abstracts deliberate consequences of actions. We prove that this logic is sound and complete. Furthermore,we express related notions such as coercion, persuasion, or deception.

KEYWORDS:

• Deception
• manipulation
• modal logics
• neighbourhood semantics

Disclosure statement

No potential conflict of interest was reported by the author(s).

Notes

1 An S5 system for a $◻$ modality is a system where the axioms: (K) $◻(\phi \Rightarrow \psi )\Rightarrow (◻\phi \Rightarrow ◻\psi ),\left(T\right)$ $◻\phi \Rightarrow \phi$, (4) $\mathrm{\neg }◻\phi \Rightarrow ◻\mathrm{\neg }◻\phi$ and $\left(5\right)$ $◻\phi \Rightarrow ◻◻\phi$ are considered.

2 A bisimulation is a relation between two models in which related states have identical atomic information and matching transition possibilities (Blackburn, 2002).

3 We also accept the expressions ‘φ is a deliberate effect of agent i’ or ‘agent i deliberately sees to it that φ’.

4 A binary relation $\mathcal{R}$ on $\mathcal{W}$ is confluent if, and only if, the following property is satisfied $\mathrm{\forall }w,u,v\in \mathcal{W},w\mathcal{R}u\wedge w\mathcal{R}v\to \mathrm{\exists }z\in \mathcal{W}:u\mathcal{R}z\wedge v\mathcal{R}z$. Here we do not consider an S5 system with negative introspection but an S4.2 system. An S4.2 system is an S4 system – a system with the axioms for a $◻$ modality (K) $◻(\phi \Rightarrow \psi )\Rightarrow ◻\phi \Rightarrow ◻\psi$, (T) $◻\phi \Rightarrow \phi$, and $\left(4\right)$ $\mathrm{\neg }◻\phi \Rightarrow ◻\mathrm{\neg }◻\phi$ – with a 4.2 axiom, ie. $◊◻\phi \Rightarrow ◻◊\phi$. The main reason is that since we would like to model also human agents' reasoning, we cannot accept that humans know everything they do not know. For more details, the interested reader may refer to Stalnaker (2006) who gave arguments to support S4.2 rather than S5 for modelling knowledge.

5 An equivalence relationship is by definition a reflexive, transitive and symmetrical relationship, but equivalently we can consider any reflexive, transitive and Euclidean relationship.

6 A set of formulas Σ is closed under single negation iff if $\sigma \in \mathrm{\Sigma }$ and σ is not of the form $\mathrm{\neg }\theta$, then $\mathrm{\neg }\sigma \in \mathrm{\Sigma }$.

7 We explain why $a\in \Vert \mathrm{\neg }{K}_j{E}_i^d{E}_{j}q\Vert$ and $u\notin \Vert \mathrm{\neg }{K}_j{E}_i^d{E}_{j}q\Vert$. Firstly, notice that $\Vert E_{j}q\Vert \notin {\mathcal{E}}_i^d\left(a\right)$, and $\mathcal{M},a\models \mathrm{\neg }{E}_i^d{E}_{j}q$ and $\mathrm{\forall }x\in \mathcal{W}:a{\mathcal{K}}_{j}x,\mathcal{M},x\models \mathrm{\neg }{E}_i^d{E}_{j}q$. Thus$,\mathcal{M},a\models K_j\mathrm{\neg }{E}_i^d{E}_{j}q$, and so $\mathcal{M},a\models \mathrm{\neg }{K}_j{E}_i^d{E}_{j}q$. Secondly, notice that $\Vert E_i^d{E}_{j}q\Vert =\{w,u\}$ and since $\mathrm{\forall }x\in \mathcal{W},u{\mathcal{K}}_{j}x,\mathcal{M},x\models E_i^d{E}_{j}q$, we have $\mathcal{M},u\models K_j{E}_i^d{E}_{j}q$ and so $u\notin \Vert \mathrm{\neg }{K}_j{E}_i^d{E}_{j}q\Vert$.

8 To make sure, just compute the set $\Vert E_i^d{E}_j^{d}q\Vert =\{w,u\}$ and so the only possible world x such that $\mathrm{\forall }z\in \mathcal{W},x{\mathcal{K}}_{j}z,\mathcal{M},z\models E_i^d{E}_j^{d}q$ is the world $x=u$.

9 It is an obvious theorem of the theory of set. Let E, F be two sets. $(\Rightarrow )$ Let assume $(E\subseteq F\wedge \mathrm{\forall }e,e\notin E\Rightarrow e\notin F)$. W have $E\subseteq F$ and so, let us show that $F\subseteq E$. Let $f\in F$. Since $\mathrm{\forall }e,e\notin E\Rightarrow e\notin F$ is equivalent, by contraposition, to $\mathrm{\forall }e,e\in F\Rightarrow e\in E$, we deduce that $f\in E$. So E = F. $(\Leftarrow )$ Let us assume E = F, thus $E\subseteq F$ and $F\subseteq E$. Thus $\mathrm{\forall }e,e\in F\Rightarrow e\in E$ and by contraposition, we deduce $\mathrm{\forall }e,e\notin E\Rightarrow e\notin F$.

10 $X\in \bigcap _{v\in \mathcal{W}:w{\mathcal{K}}_{i}v}{\mathcal{E}}_i^d\left(v\right)$ iff $\mathrm{\forall }v\in {\mathcal{K}}_i\left(w\right),X\in {\mathcal{E}}_i^d\left(v\right)$. Thus, $X\notin \bigcap _{v\in \mathcal{W}:w{\mathcal{K}}_{i}v}{\mathcal{E}}_i^d\left(v\right)$ iff $\mathrm{\exists }v\in {\mathcal{K}}_i\left(w\right),X\notin {\mathcal{E}}_i^d\left(v\right)$.

11 Since p is not an atom involved in the substitution, regardless if $w\notin h^{\prime }\left(p\right)$ or $w\in h^{\prime }\left(p\right)$, it will not affect the demonstration. We are just making sure we have got the right model here.

12 We apply here the Case-Based Reasoning i.e. the elimination of the disjunction.