What Has Been Said? Identifying the Change Formula in a Belief Revision Scenario

1 Introduction

Announcements have been widely studied in the Dynamic Epistemic Logic framework [van Ditmarsch et al., 2008; Baltag and Moss, 2004]. Three main types of announcements have been identified in this setting: private announcements, where some agents receive new information but the other agents are not aware of this communication, semi-private announcements where the other agents know that the agents receive some information about a formula ϕ (but they do not know whether it was ϕ or ¬ϕ), and finally, public announcements where the exact message is known by all agents.

We want to address another kind of announcement, that is in-between private and semi-private, where the other agents are aware that something has been said to the agents but do not know what. Let us call these announcements quasiprivate announcements. This corresponds to very common situations when one can see a conversation between several persons but cannot hear what is said. Thus, in this work, we focus on the case when a formula µ (announcement) has been said to a group of agents, and each person of this group has rationally incorporated this new piece of information into her beliefs, using a belief revision operator [Alchourr´on et al., 1985; Katsuno and Mendelzon, 1991]. We want to know what can be said about this formula from the prior and revised beliefs of the agents.

∗Contact Author

Technically, this issue can be considered as an inverse problem for belief revision. Usually, in belief revision, one knows the prior beliefs ϕi of an agent i and the new piece of information µ, and the aim is to compute her revised beliefs γi so that γi = ϕi ◦ µ. Here, our goal is to find the new piece of information µ from the prior beliefs ϕi and the revised beliefs γi of a group of agents. In formal terms, the problem amounts to "solving" the system of equations ϕi ◦ µ = γi, where the unknown is µ.

For the sake of illustration, let us present a scenario that will be used as a running example in the paper:

Example 1. We know that Amy and Beniko received some announcement about a park they plan to visit. The prior beliefs of Amy were that the park is far to the north and that the park's entrance is free, whereas Beniko believes at start that the park is near to the south and that the entrance is subject to a fee. Then we saw that a third person told them something, but we do not know what. Nevertheless, we know that, after the occurrence of this event, the beliefs of Amy have evolved in such a way that she now believes that the park's entrance is free, but that the park is located to the east, and is either near to the north or far to the south. We also know that Beniko still believes that the park is near and that entrance is subject to a fee, and additionally believes that it is located south east of their current location. The issue is to determine the announcement made to Amy and Beniko.

In this work the agents are supposed to be rational in the sense that each one of them uses a belief revision operator to revise her beliefs. This is enough to show that the set of candidate formulae for µ has the form of a logical interval. We explain how the bounds of this interval can be tightened when µ is known to be independent from a given set of variables (this captures a situation when the topic of the change formula is known), and/or when the revision operators used by the agents are known. We also study the completeness issue, i.e., whether the input allows one to identify µ (up to logical equivalence). We present some sufficient conditions for it, identify its computational complexity, and report the results of some experiments about the completeness issue when the revision operators used by the agents are Dalal's.

For space reasons, most proofs are omitted. An extended version of the paper containing all the proofs is available from https://www.cril.univ-artois. fr/˜marquis/ijcai19-IP-extended.pdf.

2 Preliminaries

Let LP be a propositional language built up from a finite set of propositional variables P and the usual connectives. ⊥ (resp. ⊤) is the Boolean constant always false (resp. true). An interpretation (or world) is a mapping from P to {0, 1}. The set of all interpretations is denotedW. [ϕ] denotes the set of models of the formula ϕ, i.e., [ϕ] = {ω ∈ W | ω |= ϕ}. |= denotes logical entailment and ≡ logical equivalence, i.e., ϕ |= ψ iff [ϕ] ⊆ [ψ] and ϕ ≡ ψ iff [ϕ] = [ψ]. V ar(α) denotes the set of propositional variables appearing in α.

A belief base (base for short) is a formula (or equivalently a finite set of propositional formulae considered conjunctively) that represents the set of beliefs of an agent.

Definition 1 (KM revision operator [Katsuno and Mendelzon, 1991]). A KM revision operator ◦ is a revision operator associating a base ϕ and formula µ with a new base ϕ ◦ µ, such that for all formulae µ, µ′ , ϕ, ϕ′ :

• (R1) ϕ ◦ µ |= µ;
• (R2) If ϕ∧ µ is consistent, then ϕ ◦ µ ≡ ϕ∧ µ;
• (R3) If µ is consistent, then ϕ ◦ µ is consistent;
• (R4) If ϕ ≡ ϕ′ and µ ≡ µ′ , then ϕ ◦ µ ≡ ϕ′ ◦ µ′ ;
• (R5) (ϕ ◦ µ) ∧ µ′ |= ϕ ◦ (µ ∧ µ′ );
• (R6) If (ϕ ◦ µ) ∧ µ′ is consistent, then ϕ ◦ (µ ∧ µ′ ) |= (ϕ ◦ µ) ∧ µ′ .

Postulates (R1 - R3) are the most essential ones. Postulate (R4) is the syntax-independence postulate. Postulates (R5 - R6) require that the minimality of change is induced by a notion of proximity between worlds (see [Katsuno and Mendelzon, 1991] for more details about the rationale of these postulates).

KM revision operators can be characterized in terms of total preorders over interpretations. Given a preorder ⪯, ≃ (resp. ≺) denotes the indifference (resp. strict) part of ⪯: a faithful assignment is a mapping associating every base ϕ with a preorder ⪯ϕ such that for all bases ϕ, ϕ1, ϕ2 and all interpretations ω, ω′ ∈ W, the following conditions are satisfied:

1. If ω, ω′ |= ϕ, then ω ≃ϕ ω′ ;
2. If ω |= ϕ and ω′ ̸|= ϕ, then ω ≺ϕ ω′ ;
3. If ϕ1 ≡ ϕ2, then ⪯ϕ1 =⪯ϕ2 .

Proposition 1. [Katsuno and Mendelzon, 1991] A revision operator ◦ is a KM revision operator if and only if there exists a faithful assignment associating each base ϕ with a total preorder ⪯ϕ such that for all ϕ, µ ∈ LP, [ϕ ◦ µ] = min([µ], ⪯ϕ).

An interesting class of KM revision operators is the class of distance-based revision operators ◦d characterized by a distance between interpretations 1 d : W×W ↦→ N [Lehmann et al., 2001; Konieczny et al., 2004]. For all ϕ, µ ∈ LP , ϕ◦dµ is defined as any formula whose models are the most plausible models of µ w.r.t. ⪯dϕ, i.e.,

where for all ω1, ω2 ∈ W, ω1 ⪯dϕ ω2 if and only if d(ω1, ϕ) ≤ d(ω2, ϕ), and for every ω ∈ W, d(ω, ϕ) = minω′ |=ϕ d(ω, ω′ ).

Noteworthy, KM revision operators include Dalal's revision operator ◦Dal [Dalal, 1988] which corresponds to the distance-based revision operator based on the Hamming distance dH defined for all ω, ω′ ∈ W as dH(ω, ω′ ) = |{x ∈ P | ω(x) ̸= ω′ (x)}|.

3 Identifying the Change Formula

We consider a finite set of agents n = {1, . . . , n}, n ≥ 1. Each agent i ∈ n is associated with a prior belief base ϕi. A formula, called change formula and denoted by µ, is assumed to be said to all agents but it is not known. Each agent i ∈ n revises her prior belief base ϕi by µ, resulting in the revised belief base γi. Lastly, we assume that each agent performs rational revision operations. More precisely, each agent i ∈ n uses a revision operator ◦i which is not known, but which satisfies all KM rationality postulates :

Overall, we consider an "inverse revision problem" whose input is characterized by an IP pair defined as follows:

Definition 2 (IP pair). Given a prior profile Φ = 〈ϕ1, . . . , ϕn〉 and a revised profile Γ = 〈γ1, . . . , γn〉, where for each i ∈ n, ϕi and γi correspond respectively to the prior belief base and the revised belief base of agent i, the pair IP = 〈Φ, Γ〉 is called an Inverse revision Problem description, or IP pair for short.

Our goal is to characterize the change formula µ when possible, or "approximate" it as much as possible given the information provided by the IP pair.

Definition 3 (Frame). The frame of an IP pair IP = 〈Φ, Γ〉, denoted by fr(IP), is the set of formulae δ from LP such that for each agent i ∈ n, there exists a revision operator ◦i satisfying all KM postulates and such that ϕi ◦i δ ≡ γi.

From now on, we assume that (i) the change formula µ is consistent, and (ii) no agent lies on her actual prior or revised belief base. Obviously enough, under these assumptions, we always have that fr(IP) ̸= ∅, since for each agent i ∈ n, the revised base γi results as a matter of fact from the revision of the prior base ϕi by µ. We say that a frame fr(IP) is complete when for all δ, δ′ ∈ fr(IP), we have that δ ≡ δ′ . Intuitively, this means that the change formula of an IP pair IP can be characterized (up to logical equivalence) precisely when fr(IP) is complete.

1 Actually a pseudo-distance is enough, i.e., the triangular inequality is not needed.

Example 1 (continued). Let us now model the scenario provided in the introduction. We are given two agents 2 = {1, 2}, where 1 corresponds to Amy, 2 to Beniko. LP is the propositional language defined from the set of variables P = {s, e, n, f}, where s stands for "the park is located to the south", e stands for "the park is located to the east", n means "the park is near", and f means that "the park's entrance is free". Amy's (resp. Beniko's) prior beliefs are then represented as ϕ1 = ¬s∧¬n∧f (resp. ϕ2 = s∧n∧¬f). After getting information from the third person, Amy's (resp. Beniko's) revised beliefs are represented as γ1 = e ∧ (n ⇔ ¬s) ∧ f (resp. γ2 = s ∧ e ∧ n ∧ ¬f). Thus, we consider the IP pair IP = {〈ϕ1, ϕ2〉, 〈γ1, γ2〉}. We assume that there are two KM revision operators ◦1, ◦2 such that ϕ1 ◦1 µ = γ1, ϕ2 ◦2 µ = γ2, although nothing is known about ◦1 and ◦2 apart from the fact that they satisfy all KM postulates. The issue of interest is to identify, or at least approximate as much as possible, the frame fr(IP), i.e., the set of possible candidates for µ.

Let us first observe that:

where ⊔ denotes the concatenation of vectors. This means that the more agents in an IP pair, the better the approximation of the change formula.

We show below that the frame of an IP pair can be simply characterized:

Proposition 2. Let IP be an IP pair. Then fr(IP) is precisely the set of formulae given by

Proof. (⊆) Let δ ∈ fr(IP). By definition of fr(IP), we know that for each agent i ∈ n, there is a revision operator ◦i satisfying (R1-R6) such that ϕi ◦i δ ≡ γi. Since for each i ∈ n, ◦i satisfies (R1), we get that for each γi ∈ Γ, γi |= δ. Hence, ∨γi∈Γ γi |= δ. Let us now prove that δ |= ∧ϕi∈Φ,γi∈Γ ¬ϕi ∨ γi. Let i ∈ n. In the case where ϕi ∧ δ is inconsistent, we get that δ |= ¬ϕi, so we trivially have that δ |= ¬ϕi ∨ γi. Otherwise ϕi ∧ δ is consistent, and since ◦i satisfies (R2) we know that γi ≡ ϕi ∧ δ, thus we also have that δ |= ¬ϕi ∨ γi. Therefore, δ |= ∧ϕi∈Φ,γi∈Γ ¬ϕi ∨ γi.

(⊇) Let δ ∈ LP such that ∨γi∈Γ γi |= δ and δ |= ∧ϕi∈Φ,γi∈Γ ¬ϕi ∨ γi. To prove that δ ∈ fr(IP), we need to show that one can associate with each agent i ∈ n a revision operator ◦i satisfying (R1-R6) and such that ϕi ◦i δ ≡ γi. We proceed as follows. For each agent i ∈ n such that ϕi ∧ γi is consistent, let ◦i be the drastic revision operator, i.e., ◦i = ◦D, where ◦D is defined for all α, β ∈ LP as α◦D β = α∧β if α∧β is consistent, otherwise α◦D β = β. And for each remaining agent i ∈ n, since we know that ◦i can be represented by a faithful assignment, we associate with each ◦i the faithful assignment associating each formula ϕ with the total preoder ⪯iϕi , where ⪯iϕi is defined for all interpretations ω, ω′ ∈ W as ω ⪯iϕi ω′ if and only if (ω |= ϕi or ω′ |= ¬(ϕi ∨ γi)). Under these constructions, it can easily be verified that for each i ∈ n, ϕi ◦i δ ≡ γi. Therefore, δ ∈ fr(IP). This concludes the proof.

Proposition 2 above shows that the frame of an IP pair has the form of a logical interval that can be characterized succinctly and in polynomial time. A frame fr(IP) can simply be identified by a pair of propositional formulae, so that it can be denoted by (fr-(IP), fr+(IP)), where fr-(IP) = ∨γi∈Γ γi and fr+(IP) = ∧ϕi∈Φ,γi∈Γ ¬ϕi ∨ γi. On the one hand, fr+(IP) represents what has been said "at least" in the change formula µ given the information provided by the IP pair, i.e., for every formula α such that fr+(IP) |= α, we know that µ |= α. On the other hand, fr-(IP) characterizes what has been said "at most" in µ, i.e., for every formula α such that α ∧ fr-(IP) is consistent, we know that µ ̸|= ¬α.

A simple observation is that under the assumptions (i) (the change formula µ is consistent), and (ii) (no agent lies on her actual prior or revised belief base), we necessarily have fr-(IP) |= fr+(IP), which is equivalent to state that fr(IP) ̸= ∅. The set fr(IP) contains all the interpolants of fr-(IP) and fr+(IP) in the sense of Craig / Lyndon theorem [Craig, 1957], but it is not restricted to them in general since one does not ask the admissible δ to be such that Var (δ) ⊆ ⋃ni=1 Var (γi).

Clearly enough, Proposition 2 has an interesting consequence from the computational viewpoint. Indeed, deciding whether a given formula belongs to the frame of an IP pair is not harder than the inference problem in propositional logic:

Proposition 3. Given an IP pair IP and a formula α ∈ LP, the problem of deciding whether α ∈ fr(IP) is coNPcomplete.

Example 1 (continued). From Proposition 2, we get that fr(IP) = (fr-(IP), fr+(IP)), where

Hence, among what has been said by the person met by Amy and Beniko is that (cf. fr+(IP)) if the park's entrance is free, then it is not located far to the north; and if the park's entrance is not free, then it is not located near to the south west.

Note that in the above example, little is known about µ: since fr-(IP) admits three models and fr+(IP) admits 13 models, there is significant uncertainty about µ, which can be assessed by the ratio 10 16 = 58 given that for 10 interpretations out of 16 interpretations (the total number of interpretations over P = {s, e, n, f}) one ignores whether it is a model or a counter-model of µ.

Thus, our greatest interest lies in complete frames. Taking advantage of Proposition 2, we know that a frame fr(IP) is complete when fr-(IP) ≡ fr+(IP), and in such a case, fr(IP) is denoted by (δ), where δ is any formula from the frame. Interestingly, one can easily identify the cases when a frame is complete:

Proposition 4. Given an IP pair IP, fr(IP) is complete if and only if ∨ϕi∈Φ,γi∈Γ ϕi ∨ γi is a valid formula.

So this result means that if we have a varied enough set of bases, so that the disjunction of all these formulae is a valid formula, then we know that the announcement can be identified up to logical equivalence.

This result also tells us that the computational complexity of the frame completeness issue is at the first level of the polynomial hierarchy:

Proposition 5. The problem of deciding whether the frame of an IP pair is complete is coNP-complete.

4 Independence Assumptions

We now intend to show how the bounds of the logical interval representing a frame can be tightened in the case when the change formula µ is known to be independent from a given set of variables. We say that µ is independent of a set of propositional variables X ⊆ P if there exists a formula µ′ logically equivalent to µ and such that X ∩ V ar(µ′ ) = ∅ [Lang et al., 2003]. Equivalently, µ is independent of X ⊆ P if µ is equivalent to ∃X · µ, i.e., the formula µ obtained after forgetting X:

Definition 4 (Forgetting [Lang et al., 2003]). Let X ⊆ P and α ∈ LP. The forgetting of X in α is the formula ∃X · α defined inductively as

where αx←0 (resp. αx←1) is the formula α obtained by replacing each occurence of x in α by the constant ⊥ (resp. ⊤).

Given an IP pair IP and X ⊆ P, we are then interested in the frame of IP projected onto X = P \ X, denoted by fr(IP, X), defined as the subset of formulae from fr(IP) that are independent of X. For any formula α, let us denote by ∀X · α the formula ¬∃X · ¬α:

Proposition 6. Let IP be an IP pair and X ⊆ P. Then

Proof. (⊆) By definition of fr(IP,X), we know that µ ∈ fr(IP, X). And by assumption, µ ≡ ∃X · µ. So by Proposition 2, we get that fr-(IP) |= ∃X·µ. Yet we know that for all formulae α, β, if α |= ∃X·β, then ∃X·α |= ∃X·β. So we can write that ∃X·fr-(IP) |= ∃X·µ. Hence, ∃X·fr-(IP) |= µ. Similarly, we can prove that µ |= ∀X · fr+(IP). This shows that fr(IP, X) ⊆ (∃X · fr-(IP), ∀X · fr+(IP)) ∩ LX .

(⊇) Let δ ∈ (∃X · fr-(IP), ∀X · fr+(IP)) ∩ LX . Yet we know that for any formula α, we have that α |= ∃X · α and ∀X·α |= α. This means that (∃X·fr-(IP), ∀X·fr+(IP)) ⊆ (fr-(IP), fr+(IP)), so δ ∈ fr(IP). Since we also have that δ ∈ LX , we get that δ ∈ fr(IP,X) by definition of fr(IP,X). This concludes the proof.

Accordingly, the frame of an IP pair IP projected onto X is also represented as a logical interval (restricted to the propositional language LX ), denoted by fr(IP,X) = (f r-(IP, X), f r+(IP, X)) ∩ LX , where f r-(IP, X) = ∃X · fr-(IP) and fr+(IP, X) = ∀X · fr+(IP).

Example 1 (continued). Let us assume that in addition to their revised beliefs, Amy and Beniko have declared that the person they met did not mention anything about whether the park has a paid entrance or not. In this case, µ is independent of {f}. From Proposition 6, we get that fr(IP, {f}) = (fr-(IP, {f}), fr+(IP, {f})) ∩ L{f} , where

Accordingly, f does not appear in fr-(IP,X) and fr+(IP,X). Note that here, the logical interval obtained by fr(IP, {f}) is more restrained: among the total of eight interpretations, fr-(IP, {f}) admits three models and fr+(IP, {f}) admits five models, so there exist only two interpretations over {s, e, n} for which one ignores whether they are models or counter-models of µ. Thus the uncertainty on µ can be quantified this time as 28 = 14 .

With such additional independence assumptions, the frame completeness issue can be characterized as follows:

Proposition 7. Let IP be an IP pair and X ⊆ P. Then fr(IP, X) is complete if and only if ∃X · ∨ϕi∈Φ,γi∈Γ ϕi ∨ γi is a valid formula.

And as a consequence:

Proposition 8. The problem of deciding whether the frame of an IP pair is complete whenever µ is known to be independent of X ⊆ P is Πp2 -complete.

Tu sum up, using additional independence information, a better approximation of µ can be obtained, but identifying whether the resulting frame is complete is more demanding from a computational point of view. Interestingly, when the bases from the prior and revised profiles are all represented as terms (i.e., conjunctions of literals), the complexity of the frame completeness problem drops to coNP:

Proposition 9. The problem of deciding whether the frame of an IP pair is complete whenever µ is known to be independent of X ⊆ P is coNP-complete when all ϕi and γi are terms.

5 When the Revision Operators are Known

So far we have considered a setting when the prior and revised bases are known for each agent, and we have assumed that each agent uses a revision operator satisfying the KM postulates. We now intend to show how the bounds of the logical interval representing a frame of the input IP pair can be tightened in the case when the revision operators used by the agents are known. One considers successively two scenarios: the case when each ◦i is known, and its subcase when each ◦i is a distance-based revision operator.

EachKMRevisionOperator ◦i is Provided Formally, we are now given an IP pair IP and a set Θ = 〈◦1, . . . , ◦n〉, where each ◦i is the KM revision operator used by agent i. We are then interested in the frame of IP given Θ, denoted by fr(IP,Θ), which is defined as the subset of formulae δ from fr(IP) such that for each agent i ∈ n, ϕi ◦i δ ≡ γi, where ◦i is specified by Θ. This frame can be characterized as follows:

Proposition 10. Let IP be an IP pair and Θ = 〈◦1, . . . , ◦n〉. Then

where for each i ∈ n, αi is any formula such that

and ⪯iϕi is the total preorder corresponding to ◦i and associated with ϕi through its faithful assignment.

So we also obtain a better approximation in this case, and the frame of an IP pair IP given Θ is also represented as a logical interval, denoted by fr(IP,Θ) = (fr-(IP,Θ), fr+(IP,Θ)), where fr-(IP,Θ) = fr-(IP) and f r+(IP, Θ) = f r+(IP) ∧ ∧i∈n αi.

Propositions 6 and 10 state that the frame of an IP pair IP can be tightened in two different ways. Let us denote by fr(IP,X,Θ) the frame of an IP pair IP projected onto X given Θ, i.e., fr(IP,X,Θ) is the subset of formulae from fr(IP) that are independent of X and such that for each agent i ∈ n, ϕi ◦i δ ≡ γi, where ◦i is given by Θ. Interestingly, one can combine both results to strengthen the frame of IP:

Corollary 1. Let IP be an IP pair, Θ = 〈◦1, . . . , ◦n〉, and assume that µ is independent of X ⊆ P. Then

Each ◦i is a Distance-Based Revision Operator Exploiting Proposition 10 requires to consider a representation of each ⪯iϕi (i ∈ n) in order to compute a corresponding αi. Such representations are not always available. Things are easier when each ◦i ∈ 〈◦1, . . . , ◦n〉 is a distance-based revision operator characterized by a distance di since in this case, whatever ϕi, the corresponding preorder ⪯iϕi is induced from the underlying distance di. Indeed, with k = minω∈[γi] di(ω, ϕi), let Di(ϕi,> k) be any formula which is satisfied by the interpretations ω satisfying di(ω, ϕi) > k. Then Proposition 10 can be specialized by replacing αi by Di(ϕi, > k).

Example 1 (continued). Assume that in addition to the assumption that µ is independent of {f}, one knows that Θ = {◦1, ◦2}, where ◦1 = ◦2 = ◦Dal, i.e., both Amy and Beniko use Dalal's operator for revising their beliefs. From Corollary 1, we get that fr(IP, {f},Θ) = (fr-(IP, {f},Θ), fr+(IP, {f},Θ)). On the one hand, we have that

On the other hand, we have that fr+(IP, {f},Θ) = fr+(IP, {f}) ∧ fr+(IP, Θ); yet fr+(IP, {f}) = (s ∨ n) ∧ (¬s ∨ ¬n ∨ e), and it can be verified that fr+(IP,Θ) = fr+(IP) ∧ ∧i∈n αi (from Proposition 10), which is equivalent to (s ∨n) ∧ (s ∨ e ∨¬n∨¬f) ∧ (¬s ∨ e ∨n∨¬f) ∧ (¬s ∨ e ∨ ¬n ∨ f). Overall, we get that

Therefore, we get that

which means that fr(IP, {f},Θ) is complete, with fr(IP, {f},Θ) ≡ (e ∧ (s ∨ n)). We can deduce that what has been said to Amy and Beniko is precisely that the park is located to the south east, or near to the north east.

6 Some Experimental Results

This section reports experimental results about the number of agents needed to identify the change formula µ (up to logical equivalence) when each agent takes advantage of Dalal's operator for revising her beliefs.

Computing such a number requires to generate instances consisting of a change formula µ, and IP pairs for this µ. To this end, we have taken advantage of a random CNF generator available at https://www.csc.kth. se/˜giraldez/. For a given number p ≥ 10, one creates a CNF instance containing ⌈0.5×p⌉ variables and ⌈1.75×p⌉ clauses; if this formula is unsatisfiable, then one removes clauses from it in a greedy fashion until getting a satisfiable formula µ. The sizes of the clauses that are generated depend on the number of communities which is expected (this number varies between 1 and ⌈ p3 ⌉). When ⌈ p3 ⌉ < 3, clauses of size 2 have been considered.

The bases ϕi (under the form of CNF formulae) are generated in the same way as µ considering ⌈0.8 × p⌉ variables and ⌈2.8 × p⌉ clauses. For each IP pair associated with µ, µ is identified whenever the upper bound of the logical interval associated with its frame implies the corresponding lower bound. Those implication tests are at the second level of the polynomial hierarchy (they correspond to instances of a Πp2 - complete problem). Indeed, in the CNF encodings associated with the upper bounds, some extra-variables (existentially quantified) are introduced. In our approach, those variables are eliminated (using the resolution principle) so that the complexity of the resulting implication tests falls down to coNP, and a SAT solver is used to solve them. Obviously enough, the variable elimination step is computationally expensive (the output can be exponential in the size of the input). This explains why the number of variables considered in the experiments has been kept small.

The following figures synthesize the results we got by considering a set of 100 change formulae µ over the same set of 10 propositional variables.

Figure 1 (a-b) makes precise for each interval of number of agents (on the x-axis) the number of additional change formulae out of 100 (on the y-axis) that have been characterized in comparison with the previous interval. Figure 1 (a) corresponds to the case one just knows that these operators are KM

(b) Dalal's revision operator

Figure 1: Number of agents required for identifying µ.

ones, and in Figure 1 (b), the reported results correspond to the case when we know that each agent uses Dalal's revision operator (leading to tighter logical intervals).

Figure 2 presents a scatter plot enabling to compare the corresponding numbers of agents at the instance level: each point corresponds to an instance, its x-coordinate indicates the number of agents required to identify µ in case (b), and its y-coordinate indicates the number of agents required to identify µ in case (a).

One can observe on the two figures that exploiting the information given by the revision operators used by the agents (here, Dalal's) leads to diminish significantly the number of agents required for the identification task. It is also interesting to note that the number of agents required to identify the announcement becomes quite reasonable when the revision operators are known (mostly around 20-30 agents).

7 Other RelatedWork

Several inverse problems of belief revision have been considered in the literature. [Booth and Nittka, 2008] considered a framework where one observes a sequence of belief states from a single agent that evolves over time. At each step we are given some formulae that hold and some formulae that do not hold in the belief state of the agent. The change formulae µi are also given, and a lexicographic revision (by µi) is assumed to be performed at each step. The main issue is to find the initial belief state. [Liberatore, 2015] considered a similar sequence-based framework, except that the belief base of the agent is fully known at each step. The focus is then given on the computational complexity of deciding whether the sequence allows for an initial epistemic state, given some assumption on the iterated revision operator that is used at each step. In both works, the unobservable component is on the agent's side. This clearly departs from our approach where the unknown is the change formula µ.

More closely related to our setting is [Hunter et al., 2017]: n agents are considered, and each agent i provides her belief base ϕi together with her revision operator ◦i. In addition, a goal ψi is given for each agent i. The issue of interest is to determine whether there exists a formula µ such that ϕi ◦i µ, the revised base of each agent, entails the goal ψi associated with it. Clearly, our contribution departs from [Hunter et al.,

2017], both in terms of setting and objective. Rather than manipulating the beliefs of a set of agents, one wants to find what has been said to them, so we are not given goals to be achieved for the agents, but their actual revised bases. But, on the same vain, it could be interesting to study if our results can be exported for multi-agent epistemic planning problems (see, e.g., [Muise et al., 2015]).

8 Conclusion and Perspectives

We have considered a belief revision scenario where an announcement (a propositional formula) µ is made to a group of agents. We assumed that we do not know µ, but we are given access for each agent to her prior beliefs and her beliefs after revision by µ. We proved that the set of µ satisfying those requirements has the form of a logical interval which can be characterized by compact bounds (i.e., formulae of size polynomial in the input size). We explained how this interval can be tightened under variable-independence assumptions or when the revision operator used by each agent is known. We also provided some experimental results about the identification issue, showing the benefits of taking into account such extra-information.

One of our findings is that the announcement µ can be completely characterized in the case when the disjunction of the agents' prior beliefs and revised beliefs is a valid formula. A direct consequence of this result is that whenever one can identify a subset of agents such that the disjunction of their prior beliefs is valid, we know that µ could be characterized, were the revised beliefs of these agents available. Thus, when the access to those revised (and prior) beliefs is not "for free", i.e., some underlying cost has to be paid to get them, the identification issue can be recast as a cost-minimization problem. Studying this optimization problem and designing algorithms can be interesting for studying causes for changes of opinion in social networks, allowing to complete the study of social networks opinion change using belief change tools [Schwind et al., 2015; 2016]. This will be a perspective for further research.

Acknowledgments

This work was supported by JSPS KAKENHI Grant Number JP17H00763 and JP17K12746.