Is Promoting Beliefs Useful to Make Them Accepted in Networks of Agents?

1 Introduction

We are interested in the issue of monotonicity in a multiagent system, represented as a Belief Revision Game (BRG) [Schwind et al., 2015]. The BRG setting is a framework for modeling the belief dynamics of a group of agents V , for instance agents involved in a social network. A BRG is a dynamical system where agents have their own belief bases (representing their belief states), and communicate synchronously with their acquaintances. The acquaintance relationship is given through a binary relation A over V , i.e., (V↪ A) is a graph. Let us introduce a motivating example:

Example 1. Consider a group of friends Alex, Beth and Chris who are discussing on whether they should trust the quality of the food served in a given restaurant. Alex and Beth know each other, Alex and Chris as well, but Beth and Chris do not know each other. Two meals are considered by them. At the beginning, Alex believes that either the first meal or the second one is healthy, but not both of them; Beth believes that none of the two meals is healthy; whereas Chris believes that at least one of the two meals is healthy.

At each communication step, each agent revises her beliefs by considering the beliefs of her acquaintances. Several merging-based revision policies have been defined, each of them reflecting how much an agent is ready to question her current beliefs in front of the beliefs of her acquaintances. Then a piece of belief ' is accepted by an agent i of V when there exists a step of the game from which ' holds in the belief bases of i at each subsequent step; and ' is unanimously accepted when it is accepted by every agent of V .

Now, the question is, given a piece of belief ', is adding "more '" in a BRG always beneficial to '? More precisely, whenever a piece of belief ' is unanimously accepted in a BRG, is it always harmless to replace at the beginning some bases by ', or more generally, by a base that is "closer" to ', i.e., by a "promotion" of '? This monotonicity condition is essential when one wants to investigate the potential manipulation of such sytems, in particular the control issue: consider a set of agents from a predefined subset C of V and an additional agent M who can "control" the agents from C, i.e., M can modify the initial beliefs of agents from C, then is it possible for M to make a piece of belief unanimously accepted? Such a control issue is significant for a number of multi-agent problems, including brand crisis management [Dawar and Pillutla, 2000]; in such applications, it is useful to know what information agents from C should convey to their acquaintances in order to avoid the propagation of negative perceptions.

In the next section we provide some preliminaries on BRGs. We then define and investigate in Section 3 the notion of promoting a formula ' in a belief base, and show that many rational change operators (including revision and contraction operators) can be used for the promotion purpose. We then formalize in Section 4 the monotonicity property based on promotion operators and show that this condition is not always satisfied by BRGs. As a consequence, replacing some agents' initial beliefs by ' is not always the best way to make ' unanimously accepted. In Section 5 we show that the monotonicity property holds for BRGs based on the complete graph topology, focusing on revision policies based on a specific merging operator. We discuss some related work in Section 6 before concluding. For space reasons, proofs are omitted but can be found online at http://www.cril.univartois.fr/⇠marquis/ijcai16-long.pdf.

2 Belief Revision Games

Let LP be a propositional language built up from a finite set of propositional variables P and the usual connectives, including ⊕, the xor connective. ? (resp. >) is the Boolean constant always false (resp. true). Formulae are interpreted in a standard way. Mod(') denotes the set of models of the formula ', ♣= denotes logical entailment and ⌘ logical equivalence, i.e., ' ♣= iff Mod(') ✓ Mod( ) and ' ⌘ iff Mod(') = Mod( ). A belief base B denotes the set of beliefs of an agent, it is a finite set of propositional formulae interpreted conjunctively, so that B is identified with the conjunction of its elements. A profile C = hB1↪ ▷ ▷ ▷ ↪ Bni is a finite vector of belief bases. A Belief Revision Game (BRG for short) is formalized as follows [Schwind et al., 2015]:

Definition 1 (Belief Revision Game). A Belief Revision Game (BRG) is a tuple G = (V↪ A↪ LP ↪ B↪ R) where

• ÷ A ✓ V ⇥V is an irreflexive binary relation on V which represents the acquaintances between the agents;
• ÷ V = ¶1↪ ▷ ▷ ▷ ↪ n♦ is a finite set of agents;
• ÷ LP is a finite propositional language;
• ÷ B is a mapping from V to LP where for each i 2 V , B(i) (noted Bi) is the initial belief base of agent i;
• ÷ R = ¶R1↪ ▷ ▷ ▷ ↪ Rn♦, where each Ri is the revision policy of agent i, i.e., a mapping from LP ⇥LP in(i) to LP with in(i) = ♣¶j ♣ (j↪ i) 2 A♦♣ the in-degree of i, such that if in(i) = 0, then Ri is the identity function.

Let G = (V↪ A↪ LP↪ B↪ R) be a BRG and let us denote Ci the context of i, defined as the profile Ci = hBi1 ↪ ▷ ▷ ▷ ↪ Biin(i) i where ¶i1↪ ▷ ▷ ▷ ↪ iin(i)♦ = ¶ij ♣ (ij↪ i) 2 A♦. Then Ri(Bi↪ Ci) is the belief base of agent i once revised by taking into account her own current beliefs Bi and her current context Ci. 1

In a BRG, the beliefs of each agent evolve at each time step according to her revision policy. This induces for each i 2 V a belief sequence (Bs i )s2N where Bs i denotes the belief base of agent i after s steps, defined as B0 i = Bi and for each s ≥ 0, Bs+1 i = Ri(Bs i ↪ C s i ), where C s i is the context of i at step s. Schwind et al. [2015] showed that in any BRG, the belief sequence of each agent i is cyclic, i.e., in (Bs i )s2N there exists a finite subsequence Bb i ↪ ▷ ▷ ▷ ↪Be i such that for every j > e, we have Bj j ⌘ Bb+((j-b)mod(e-b+1)) i ; the belief cycle Cyc(i) of an agent i corresponds to the series of this subsequence of belief bases Cyc(i) = Bb i ↪ Bb+1 i ↪ ▷ ▷ ▷ ↪Be i . As we are interested in determining the pieces of beliefs resulting from the interaction of the agents, we focus on the outcome of each agent i in G, denoted AccG(i) and defined as:

1 Abusing notations, Ri(Bi↪ Ci) stands for

Ri(Bi↪ Bi1 ↪ ▷ ▷ ▷ ↪ Biin(i) ) where Ci = hBi1 ↪ ▷ ▷ ▷ ↪ Biin(i) i.

We say that a formula ' is accepted by i in G if AccG(i) ♣= ', ' is unanimously accepted in G if ' is accepted by all i 2 V in G, and G converges at step s if for each i 2 V , Bs+1 i = Bs i .

The formalization of a BRG allows each agent i to consider any revision policy Ri 2 R. However, one can take advantage of theoretical tools from Belief Change Theory (see e.g. [Alchourr´on et al., 1985]), more precisely, belief revision and merging operators for defining revision policies. A merging operator ∆ associates any formula θ (the integrity constraint) and any profile C with a new formula ∆θ(C) (the merged base). A merging operator ∆ aims at defining the merged base as the beliefs of a group of agents represented by the profile, under some integrity constraint. Standard properties (denoted (IC0)-(IC8)) are expected for merging operators, and such operators are called IC merging operators (see [Konieczny and Pino P´erez, 2002] for details on these properties).

IC merging operators include some distance-based operators, i.e., operators that are based on the selection of some models of the integrity constraint, the "closest" ones to the given profile. These operators are characterized by a distance d between interpretations and an aggregation function f [Konieczny et al., 2004]. They associate with every formula θ and every profile C a belief base ∆d↪f θ (C) satisfying Mod(∆d↪f θ (C)) = min(Mod(θ)↪d↪f C ), where d↪f C is the total preorder over interpretations induced by C defined by ! d↪f C !0 if and only if df (!↪ C)  df (!0 ↪ C), where df (!↪ C) = fB2C¶d(!↪ B)♦ and d(!↪ B) = min!0 ♣=B d(!↪ !0 ). Usual distances are dD, the drastic distance (dD(!↪ !0 ) = 0 if ! = !0 and 1 otherwise), and dH the Hamming distance (dH(!↪ !0 ) = n if ! and !0 differ on n variables). Using aggregation functions such as ⌃ and GMax lead to IC merging operators. For instance, GMax operators consider for each profile C the total preorder over interpretations d↪GMax C defined by ! d↪GMax C !0 if and only if dGMax (!↪ C) lex dGMax (!0 ↪ C) (where lex is the lexicographic ordering induced by the natural order) and dGMax (!↪ C) is the vector of numbers d1↪ ▷ ▷ ▷ ↪ dn obtained by sorting in a descending order the vector hd(!↪Bi) ♣ Bi 2 Ci. Lastly, belief revision operators can be seen as belief merging operators applied to singleton profiles: indeed, if ∆ is an IC merging operator then the revision operator ◦∆ induced by ∆ defined for all bases B1↪B2 as B1 ◦∆ B2 = ∆B2 (hB1i) satisfies the standard KM revision postulates [Katsuno and Mendelzon, 1992].

Let us go back to BRGs. Six classes of revision policies have been proposed in [Schwind et al., 2015]. Each of them, denoted Rk∆ (k 2 ¶1↪ ▷ ▷ ▷ ↪ 6♦) is parameterized by an IC merging operator ∆. Each class is defined as follows, 2 at each step s and for any agent i such that Ci 6= ;:

2 When using a merging operator without integrity constraints we just note ∆(C) instead of ∆>(C) for improving readibility.

2k +2 p1 ⊕p2 ≻p1 _≻p2 ≻p1 _≻p2

Table 1: The belief sequences of Alex, Beth and Chris in G⇤.

• ÷ R1∆(Bs i ↪ C s i ) = ∆(C s i );
• ÷ R2∆(Bs i ↪ C s i ) = ∆∆(Cs i )(hBs i i) [= Bs i ◦∆ ∆(C s i )];
• ÷ R3∆(Bs i ↪ C s i ) = ∆(hBs i ↪ C s i i);
• ÷ R5∆(Bs i ↪ C s i ) = ∆Bs i (∆(C s i )) [= ∆(C s i ) ◦∆ Bs i ];
• ÷ R4∆(Bs i ↪ C s i ) = ∆(hBs i ↪∆(C s i )i);
• ÷ R6∆(Bs i ↪ C s i ) = ∆Bs i (C s i ).

[Schwind et al., 2015] studied the extent to which BRGs satisfy some basic logical properties depending on the class of revision policies used by the agents, and focused on the case when all agents use the same revision policy ranging over Rk∆, k 2 ¶1↪ ▷ ▷ ▷ ↪ 6♦. It turned out that when the revision policy is induced from the merging operator ∆dD↪⌃, i.e., the merging operator based on the drastic distance and the summation function, the underlying BRGs satisfy a number of expected properties [Schwind et al., 2015]. The authors also developed a software allowing one to play BRGs, available online at http://www.cril.univ-artois.fr/software/brg.html.

Example 1 (continued). We consider the BRG G⇤ = (V⇤↪A⇤↪LP⇤ ↪ B⇤↪R⇤) defined as follows. V⇤ = ¶1↪ 2↪ 3♦ where 1 corresponds to Alex, 2 to Beth, and 3 to Chris. A⇤ = ¶(1↪ 2)↪ (2↪ 1)↪ (1↪ 3)↪ (3↪ 1)♦ expresses that Alex knows Beth and vice-versa, and Alex knows Chris and vice-versa, but Beth and Chris are not connected. LP⇤ is the propositional language defined from the variables P⇤ = ¶p1↪ p2♦, where p1 stands for "the first meal is healthy" and p2 means "the second meal is healthy." The initial beliefs of the group members are B1 = p1 ⊕ p2, B2 = ≻p1 ^ ≻p2 and B3 = p1 _ p2. Assume that all agents use the same revision policy, Ri = R1∆dH↪GMax for each i 2 V⇤. The belief sequences associated with the three agents are given in Table 1: the belief cycle of agent 1 (resp. 2, 3) is given by (B0 1 ↪ B1 1 ) (resp. (B1 2 ↪ B2 2 ), (B1 3 ↪ B2 3 )). We have for each i 2 V⇤, Cyc(i) = p1 ⊕ p2↪ ≻p1 _ ≻p2 and AccG(i) = ≻p1 _ ≻p2.

3 On the Notion of Promotion

Belief control in a multi-agent system can take various forms, depending on the meaning given to "control." Here, we are specifically interested in control strategies that consist in promoting a certain belief ' in the beliefs of the agents. A key issue to be addressed is then to determine what "promoting" precisely means in this context. A simple view is to consider that promoting ' in the belief base B of an agent consists in replacing B by a base equivalent to '. While such a drastic way of promoting ' makes sense, it is not the only one. Thus, for instance, revising B by ' is another approach to do the job. Considering the whole spectrum of promotion techniques is interesting because in some scenarios it could be the case that the agent under consideration can be ready to promote ' by revising her own beliefs B with it, while she would be reluctant in questioning her whole base B and replacing it by '. In a bribery context, she could for instance ask much more money to accept to change her base B to ' than to change it to the revision of B by '.

We now characterize the notion of "promotion" of ' through a preorder ⪯' over belief bases which reflects the closeness relationship to '; thus, B0 ⪯' B states that B0 is at least as close to ' as B. On this ground, promoting B consists in replacing B by any B0 satisfying B0 ⪯' B:

Definition 2 ('-promotion). For every formula ' 2 LP, the '-promotion relation is the binary relation ⪯' on LP ⇥ LP defined for all belief bases B↪B0 as B0 ⪯' B if and only if B ^' ♣= B0 ♣= B _'.

Obviously, one can check that for any ' 2 LP, the binary relation ⪯' is reflexive and transitive. More precisely:

Proposition 1. For every formula ' 2 LP, (LP↪⪯') is a Boolean lattice (LP↪ u'↪ t'↪ ˙≻↪ '↪ ≻'), where:

• ÷ u' is the meet operation defined for each B↪B0 2 LP as B u' B0 = (B ^ B0 ) _ ((B _ B0 ) ^ '),
• ÷ t' is the join operation defined for each B↪ B0 2 LP as B t' B0 = (B ^ B0 ) _ ((B _ B0 ) ^ ≻'),
• ÷ ˙≻ is the complement corresponding to the standard logical negation ≻,
• ÷ ' is the least element, i.e., for each B 2 LP, ' ⪯' B,
• ÷ ≻' is the top element, i.e., for each B 2 LP, B ⪯' ≻'.

where formulae of LP are considered up to equivalence.

Every base B0 promoting ' in B satisfies ' ⪯' B0 ⪯' B. Thus B is (up to logical equivalence) the greatest formula w.r.t. ⪯' promoting ' in B, and ' is (up to logical equivalence) the least formula w.r.t. ⪯' promoting ' in B. Stated otherwise, the least demanding promotion of ' w.r.t. B consists in letting B unchanged, while the promotion of ' w.r.t. B leading to a formula as close as possible to ' consists in replacing B by '.

The following model-theoretic characterization of the notion of promotion can be derived easily. N denotes the symmetric difference between sets:

Proposition 2. Given a formula ', let B and B0 be two belief bases such that B0 promotes ' w.r.t. B. Then 9S ✓ Mod(B)NMod(') such that Mod(B0 ) = (Mod(B) \ Mod (')) [ S.

This proposition also illustrates the fact that B and ' play symmetric roles in the notion of promotion. Indeed, making B closer to ' is precisely the same as making ' closer to B:

When a promotion of ' in B is achieved, the set of interpretations assigning different truth values to B and to ' may only diminish. Formally:

Proposition 4. Given a formula ', let B and B0 be two belief bases such that B0 promotes ' in B. Then Mod (B0 )NMod (') ✓ Mod (B)NMod (').

We define a promotion operator ⊙ as a mapping from LP ⇥LP to LP such that ⊙' ⪯' . Interestingly, some belief change operators of the literature are promotion operators. We recall below some of the postulates for rational revision operators ◦, and contraction operators - [Katsuno and Mendelzon, 1992, Caridroit et al., 2015], as well as some postulates for arbitration (alias symmetric revision) operators ⇧ [Liberatore and Schaerf, 1998]:

• (R1) ' ◦ θ ♣= θ.
• (C1) ' ♣= '-θ.
• (R2) If '^ θ is consistent, then ' ◦ θ ⌘ '^ θ.
• (C2) If ' 6♣= θ, then '-θ ♣= '.
• (LS2) '^ θ ♣= ' ⇧ θ.
• (C4) If ' ♣= θ, then ('-θ) ^ θ ♣= '.
• (LS7) ' ⇧ θ ♣= '_ θ.

Proposition 5. Let ' be a formula and let B be a belief base. Let ◦ be any revision operator satisfying (R1) and (R2), let - be any KM contraction operator satisfying (C1), (C2) and (C4), and let ⇧ be any arbitration operator satisfying (LS2) and (LS7). We have:

1. (i) B◦' ⪯' B^' ⪯' B, (ii) B_' ⪯' B-≻' ⪯' B, and (iii) B ⇧ ' ⪯' B;
2. B◦', B^', B_', B-≻' andB⇧' are incomparable w.r.t. ⪯' in the general case. 3

We can now lift the relation of formula promotion to BRGs defined on the same set of variables V , acquaintance relation A, propositional language LP and revision policies R. Given two BRGs G = (V↪ A↪ LP↪ B↪ R) and G0 = (V↪ A↪ LP↪ B0 ↪ R) and a formula ', we note G0 ⪯' G if and only if for each agent i 2 V , B0i ⪯' Bi. Finally, we note G⊙' any BRG G0 such that G0 ⪯' G. Observe that such a promotion operation of ' in G can be non-uniform, i.e., it is not necessarily the case that the promotion of ' in distinct bases of G0 is achieved thanks to the same promotion operator. For instance, it can be the case that B0i = Bi for agent i 2 V , while B0j = Bj ◦ ' for agent j 2 V , and B0k = ' for agent k 2 V .

4 OnMonotonicity in BRGs

In this section, we focus on the issue of monotonicity for BRGs instantiated with revision policies from the six classes defined in Section 2. Given a merging operator ∆ and E ✓ ¶1↪ ▷ ▷ ▷ ↪ 6♦ RE∆ denotes the set ¶Rk∆ ♣ k 2 E♦. We use the simpler notation Rk∆ instead of RE∆ when E = ¶k♦. Given a class G of BRGs and E ✓ ¶1↪ ▷ ▷ ▷ ↪ 6♦, G(RE∆) is the subclass of all BRGs (V↪ A↪ LP ↪ B↪ R) from G where for each Ri 2 R, Ri 2 RE∆. Additionally, a set of revision policies RE∆ is said to satisfy a given property P on a given class G of BRGs if all BRGs from G(RE∆) satisfy P .

Given a BRG G = (V↪ A↪ LP↪ B↪ R), a subset C of V of so-called "controllable agents" whose initial beliefs can be modified, and a formula ', one is interested in determining s ≥ 1 p1 ⊕p2 p1 ⊕p2 p1 ⊕p2

3 This is even the case for ◦ and - when they correspond one another thanks to Levi/Harper identities.

Table 2: An example of control strategy for G⇤ where ' = p1 _ p2 is unanimously accepted.

how to modify the belief bases of agents in C in order to make ' unanimously accepted in the resulting game (when possible). The objective is thus to determine a successful "control strategy" to be implemented in order to reach the goal when it can be reached. A control strategy for G given C takes here the form of a mapping σ from C to LP , stating for each i 2 C that Bi must be replaced by σ(i); it is successful for ' if ' is unanimously accepted in the BRG obtained by applying σ to G. Typically, one wants to minimize the number of agents in C to be controlled, but the optimization problem under consideration can also be much more complex (for instance, it may take into account the cost of controlling each agent in C which may not be uniform).

Among the potential control strategies is the basic strategy σ' for G given C defined for any i 2 C by σ(i) ⌘ ': it simply amounts to promoting ' as much as possible in the belief base of each agent from C by just replacing it by '. We have the following surprising result:

Proposition 6. Given a BRG G = (V↪ A↪ LP↪ B↪ R), a set C ✓ V of controllable agents, and a formula ', it can be the case that the basic strategy σ' for G given C is not successful for ', while a control strategy for G given C which is successful for ' exists.

Example 1 (continued). Assume that the goal of the restaurant manager is to convince all protagonists that at least one of the meals is healthy, i.e., ' = p1 _ p2. Note that at the beginning, Chris' beliefs coincide with this goal (since B3 = ') and that ' is not unanimously accepted. So if Chris is the only controllable agent, the basic strategy σ' is not successful. However, when we replace Chris' beliefs by p1 ^ p2 instead, we get that AccG⇤ (i) = p1 ⊕ p2 for each i 2 V , so p1 _ p2 is unanimously accepted (see Table 2). This shows that control is possible here given C = ¶3♦ as the only controllable agent, but not with the basic strategy.

This example illustrates the complexity of the controllability issue for BRGs in the general case. This explains why it is important to identify some conditions on BRGs for which focusing on the basic strategy would be enough to decide whether a positive answer can be given or not to the controllability question. In the following, we show that some monotonicity properties can be used as such conditions. A first property of monotonicity has been introduced in [Schwind et al., 2015]. Given a BRG G = (V↪ A↪ LP ↪ B↪ R), a formula ↵ and an agent i 2 V , let us denote Gi!↵ the BRG (V , A↪ LP↪ B0 ↪ R) where B0 maps V to ¶B01 ↪ ▷ ▷ ▷ ↪ B0n ♦, with B0i = Bi ^↵ and for every j 2 V , j 6= i, B0j = Bj .

Definition 3 (Monotonicity (Mon)). A BRG G = (V↪ A↪ LP↪ B↪ R) satisfies (Mon) if whenever ' is unanimously accepted in G, ' is unanimously accepted in Gi!' for every i 2 V .

'max(Bs ) ^ Bs

Table 3: Bs+1 i depending on the revision policy applied by agent i in any BRG from Gcom(R¶1↪▷▷▷↪6♦ ∆dD↪⌃ ).

(Mon) is similar to the monotonicity criterion in Social Choice Theory. In the BRG context, a formula ' that is unanimously accepted should still be so if some agent's initial beliefs were "strengthened" by '. Note that the strengthening of a belief base by a formula ' involved here consists in just expanding the base by '. However, one could consider weaker versions than expansion, i.e., the promotion operators ⊙ we formalized in the previous section. So we introduce now a stronger version of the monotonicity property (cf. Definition 3) on BRGs based on the promotion relation:

Definition 4 (Strong Monotonicity (SMon)). A BRG G = (V↪ A↪ LP↪ B↪ R) satisfies (SMon) if for each i 2 V , if ' is unanimously accepted in G, then ' is unanimously accepted in any BRG G ⊙ '.

It is easy to see that (SMon) implies (Mon) and that the converse does not hold in general. BRGs satisfying (SMon) are interesting in terms of strategy-proofness. Indeed, Proposition 1 tells us that ' is the least element of (LP↪⪯'). As a consequence, for such BRGs, determining whether it is possible to convince all the agents involved in the BRG to accept some piece of belief ' simply amounts to determining whether ' is unanimously accepted in the BRG obtained by the promotion of ' in every Bi associated with a controllable agent so that Bi ⊙ ' = '. Stated otherwise:

Proposition 7. Let G = (V↪ A↪ LP↪ B↪ R) satisfying (SMon), a set C ✓ V of controllable agents, and a formula '. If the basic strategy σ' for G given C is not successful for ' then no control strategy for G given C is successful for '.

An interesting issue now is to know whether there are BRGs satisfying (SMon). We provide a positive answer to this question in the next section.

5 The Case of Complete Graphs

We now study the extent to which (SMon) is satisfied by BRGs whose acquaintance graph is a complete graph. This simple topology is adequate to the cases when all the agents of V know each other (for instance, this is the case in meetings where all agents are sitting around a table). We simply call the corresponding class of BRGs the complete BRGs:

Definition 5 (Complete BRG). A BRG G = (V↪ A↪ LP↪ B↪ R) is complete if (V↪ A) is a complete graph, i.e., for all i↪ j 2 V , i 6= j, (i↪ j) 2 A. Given a class G of BRGs, Gcom denotes the subclass of complete BRGs from G.

In the general case, (SMon) is not satisfied by BRGs from Gcom(Rk∆) with k 2 ¶1↪ ▷ ▷ ▷ ↪ 6♦, even when ∆ is "fully" rational in the sense that it satisfies all IC postulates. Indeed: Proposition 8. For ∆ 2 ¶∆dH↪⌃↪∆dH↪GMax ♦, for any k 2

¶1↪ ▷ ▷ ▷ ↪ 6♦, Rk∆ does not satisfy (SMon) on Gcom.

In the following, we investigate the monotonicity issue for complete BRGs when the merging operator used for defining the revision policies is the distance-based merging operator based on the drastic distance (and the summation function) ∆dD↪⌃. Computing ∆dD↪⌃ θ (C) consists in selecting in the models of the integrity constraint θ those satisfying as many bases of the profile C as possible. Several works have proved this specific operator to satisfy a number of expected properties, e.g., some (language) independence conditions [Konieczny et al., 2011, Marquis and Schwind, 2014]. In particular, ∆dD↪⌃ is robust from the point of view of strategyproofness [Everaere et al., 2007], this is why this operator appears as a good candidate for the monotonicity issue.

The following notations are used in the rest of this section. Let C be a profile and ! be an interpretation. V C = V¶Bi ♣ Bi 2 C♦. #E denotes the number of elements from a finite set E. #max(C) is the maximal number of bases in C that are consistent when interpreted conjunctively, i.e., #max(C) = max(#¶C 0 ♣ C 0 ✓ C↪ V C 0 6♣= ?♦). 'max(C) = ∆dD↪⌃(C). And 'max-1(C) is any formula ' such that Mod(') = ¶! ♣ #¶Bi 2 C ♣ ! ♣= Bi♦ = #max(C) - 1♦.

Let us first show that a stronger version of the agreement preservation property (AP) (see [Schwind et al., 2015]) is satisfied by complete BRGs:

Proposition 9. Let G = (V↪ A↪ LP↪ B↪ R) be a BRG from Gcom(R¶1↪▷▷▷↪6♦ ∆dD↪⌃ ). If there is a step s where V¶Bs i ♣ i 2 V ♦ is consistent, then for each i 2 V , AccG(Bi) = V¶Bi ♣ i 2 V ♦. Moreover, G converges at step s+2 at most. It converges at step s + 1 at most if G 2 Gcom(R¶2↪▷▷▷↪6♦ ∆dD↪⌃ ).

We now intend to characterize the outcome of a BRG from its initial state. Beforehand, let us introduce an intermediary result characterizing the belief base of any agent in a BRG from Gcom(Rk∆dD↪⌃) where k 2 ¶1↪ ▷ ▷ ▷ ↪ 6♦, at some step s+1 given the belief bases of all agents at step s:

Lemma 1. Let E ✓ ¶1↪ ▷ ▷ ▷ ↪ 6♦ and G be a BRG from Gcom(RE∆dD↪⌃). Then for each agent i 2 V and each step s, her base Bs+1 i can be characterized as shown in Table 3.

Obviously enough, a consequence of Table 3 is that all six revision policies from Rk∆dD↪⌃, k 2 ¶1↪ ▷ ▷ ▷ ↪ 6♦, remain distinct. Moreover, in the case when all agents have the same revision policy among Rk∆dD↪⌃, k 2 ¶1↪ ▷ ▷ ▷ ↪ 4♦, the outcome of complete BRGs can be fully characterized:

Proposition 10. Let k 2 ¶1↪ ▷ ▷ ▷ ↪ 4♦ and G = (V↪ A↪ LP↪ B↪ R) be a BRG from Gcom(Rk∆dD↪⌃). Then for each i 2 V , AccG(i) = ∆dD↪⌃(hB1↪ ▷ ▷ ▷ ↪ Bni).

The cases when all agents have the same revision policy among Rk∆dD↪⌃, k 2 ¶5↪ 6♦ is simpler to characterize:

Proposition 11. Let k 2 ¶5↪ 6♦ and G = (V↪ A↪ LP↪ B↪ R) be a BRG from Gcom(Rk∆dD↪⌃).

• ÷ If k = 6, then for all i 2 V , AccG(i) = Bi if ∆dD↪⌃(hB1↪ ▷ ▷ ▷ ↪Bni) ^ Bi ♣= ?, otherwise AccG(i) = ∆dD↪⌃(hB1↪ ▷ ▷ ▷ ↪ Bni) ^ Bi.
• ÷ If k = 5, then for all i 2 V , AccG(i) = Bi if ∆dD↪⌃(hB1↪ ▷ ▷ ▷ ↪Bni) 6♣= Bi, otherwise AccG(i) = ∆dD↪⌃(hB1↪ ▷ ▷ ▷ ↪ Bni).

These results allow us now to derive monotonicity results for the class of complete BRGs we are dealing with:

Proposition 12. Let k 2 ¶1↪ ▷ ▷ ▷ ↪ 6♦. Then all BRGs from the class Gcom(Rk∆dD↪⌃) satisfy (SMon).

A consequence of Propositions 7 and 12 is that considering the basic strategy is enough for BRGs from Gcom(Rk∆dD↪⌃), i.e., to decide whether a control strategy exists for making a formula ' accepted by all agents in such a BRG, it is enough to focus on the basic strategy.

Let us illustrate how these monotonicity results apply to the following slightly modified version of our running example:

Example 1 (continued). Consider again the BRG G⇤ = (V⇤↪ A⇤↪ LP⇤ ↪ B⇤↪ R⇤) from our running example, and let G0⇤ be the BRG (V⇤↪ A0⇤ ↪ LP⇤ ↪ B0⇤ ↪ R⇤) where:

• ÷ A0 is the total relation over V⇤, i.e., Beth and Chris know each other as well;
• ÷ B0⇤ maps V⇤ to ¶B01 ↪B02 ↪B03 ♦, with B01 = B1, B02 = B2 and B03 = ≻p1 ^ ≻p2, i.e., the beliefs of Alex and Beth in G0⇤ remain the same as in G⇤, but Chris now initially believes in G0⇤ that none of the two meals is healthy.

From Proposition 10, we get that AccG0⇤ (i) = ∆dD↪⌃(hB01 ↪ B02 ↪ B03 i) ⌘ ≻p1 ^≻p2 for each i 2 V⇤. Note that p1 _ p2 is not accepted by any agent. By applying the basic strategy σ' where ' = p1 _ p2 and when Chris is the only controllable agent, one gets that the outcome of each agent in the resulting BRG becomes p1 ⊕ p2. We have now ' being unanimously accepted, which means that σ' is successful.

6 RelatedWork

As far as we know, the control problem for multi-agent systems has not been investigated to date in settings similar to BRGs. Though there are many works on opinion dynamics where some control or influence issues have been studied, the opinion of an agent takes typically the form of a real number, as in Hegselmann-Krause's model [Hegselmann and Krause, 2005]. Let us mention among others [Tsang and Larson, 2014, Bloembergen et al., 2014, Ranjbar-Sahraei et al., 2014, Blondel et al., 2009]. The very nature of the agents opinions (real number vs. propositional formula) makes these studies and our own approach quite unrelated. Indeed, unlike real numbers that can be simply averaged, merging propositional formulae is a much more complex process (this is why many works on the topic in the knowledge representation area have been done for two decades). The quite paradoxical result presented in the paper (roughly, promoting some belief is not guaranteed to be the safest way to make it unanimously accepted) echoes paradoxes pointed out in other settings for multi-agent systems, in particular social network games [Apt et al., 2013]. However, the resemblance is only at a shallow level since the BRG model departs a lot from social network games. Especially, social network games are "true" games, unlike BRGs (in the BRG model, agents do not have strategies and there is no payoff based on the adequacy of an agent's beliefs with the beliefs of her acquaintances).

On the other hand, some control issues (under various forms: manipulation, bribery, etc.) have received much attention recently in voting theory, especially from the viewpoint of computational complexity. See among many others [Amanatidis et al., 2015, Bredereck et al., 2015, Faliszewski et al., 2015, Loreggia et al., 2015, Faliszewski et al., 2014, Bouveret and Lang, 2014, Christian et al., 2007]. However, the results obtained in voting theory cannot be exploited directly for BRGs since in BRGs the agents beliefs may evolve after each communication step (when voting is considered, the users preferences are typically considered as fixed and agents do not influence each other). An exception is [Hassanzadeh et al., 2013] which shows how to reach a consensus on rankings (encoding the agents preferences) by iterative voting. However, the corresponding model is quite different from the BRG one since it deals with preferences, and not with beliefs, and the system dynamics is ruled by distinct mechanisms (voting vs. revision). Furthermore, belief control has not been investigated in this model (the focus is on convergence issues).

Finally, other approaches have been considered for modeling the belief dynamics of a group of agents (see dynamic epistemic logic [Harel et al., 2000, Hendricks and Symons, 2006], or in propositional logic [Gauwin et al., 2007, Delgrande et al., 2007, Grandi et al., 2015]), but the belief control issue for such settings has not been considered as well.

7 Conclusion

We pointed out a quite paradoxical result in belief diffusion: in a network of agents, replacing some agents' belief bases by a piece of belief ' may not be the "optimal" way to make ' unanimously accepted. However, we have identified a class of BRGs satisfying a property of strong monotonicity, and thus, avoiding this paradox, making for these BRGs the belief control issue easier to manage.

As perspectives for further research, we plan to identify additional classes of BRGs for which the strong monotonicity property holds, e.g., by considering other topologies as the line, single loop and more generally regular graph topologies. For all these BRGs, the next step will be to search for control strategies by focusing now on the "who" issue, i.e., which agents from a predefined set C should be considered. Another interesting perspective is to study further the notion of "promotion," as an attempt to provide a uniform axiomatization of a large class of standard belief change operators.