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

Nicolas Schwind, Katsumi Inoue, Sébastien Konieczny, Jean-Marie Lagniez, Pierre MarquisIJCAI 2019 · DOI

Introduction

In classical Artificial Intelligence, belief revision is typically studied as a forward-moving process: given an agent's initial beliefs and a new piece of information (an announcement), what is the resulting belief state? This paper investigates the "inverse problem": given the initial and revised beliefs of a group of agents, can we identify the announcement that caused the change? This scenario, termed "quasi-private announcements," is common in social contexts where we observe shifts in opinion but lack direct access to the underlying communication.

The Inverse Problem of Belief Revision

The authors formalize the challenge of identifying a change formula $\mu$ based on observed belief transitions. This is inherently difficult because multiple announcements can lead to identical revisions. To address this, the research utilizes the Katsuno-Mendelzon (KM) postulates for rational belief revision as a foundational framework.

Methodology

The identification process relies on several key theoretical contributions:

Logical Intervals

The set of candidate formulas for an announcement $\mu$ is shown to form a structured logical interval $[fr^-(IP), fr^+(IP)]$. The lower bound ($fr^-$) represents the most specific necessary information, while the upper bound ($fr^+$) represents the most general possible announcement.

Variable Independence and Forgetting

When the topic of the announcement is known to be restricted to certain variables, the technique of "forgetting" (existential quantification) can be applied. By eliminating irrelevant variables, the logical interval can be significantly tightened, reducing uncertainty about the message.

Operator Knowledge

The bounds of the logical interval can be further constrained if the specific revision operator used by the agents is known. For example, assuming agents use Dalal’s operator—which minimizes the Hamming distance between interpretations—provides additional constraints that aid in identification.

Experimental Evaluation

The approach was tested using synthetic benchmarks generated via a random CNF generator. The experiments involved 100 change formulas over 10 propositional variables to determine how many agents are required to uniquely identify an announcement under various conditions. Computational complexity analysis reveals that deciding if a formula is a candidate is coNP-complete, while checking for unique identification can reach $\Pi^p_2$-completeness.

Results and Discussion

The study reveals that the diversity of the agent pool is critical for identification. An announcement is uniquely identified if and only if the disjunction of the agents' prior and revised beliefs covers all logical possibilities (i.e., is a tautology).

Comparison of the number of agents required for identification using KM operators versus Dalal’s operator.

As shown in Figure 1, knowing the specific revision operator drastically reduces the data requirements. When the revision operator is unknown (general KM operators), identification typically requires 60 to 80 agents. However, if agents are known to use Dalal’s operator, the requirement drops to approximately 20 to 30 agents.

Distribution of the number of agents needed to uniquely identify the announcement for (a) KM revision operators and (b) Dalal’s revision operator.

Figure 3 illustrates the frequency distribution of the number of agents needed. The "Dalal advantage" is clear, with a sharp peak in the 20-30 agent range, whereas the general KM operators show a much broader distribution shifted toward higher agent counts.

Conclusion

This research provides a rigorous framework for solving the inverse problem of belief revision. By leveraging logical intervals and knowledge of revision operators, it is possible to reconstruct hidden announcements from observed behavior. Future work will address computational scalability and the potential for applying these methods to noisy, real-world social network data.

Summary updated

BibTeX
@inproceedings{schwind2019what,
  author = {Nicolas Schwind and Katsumi Inoue and Sébastien Konieczny and Jean-Marie Lagniez and Pierre Marquis},
  title = {{What Has Been Said? Identifying the Change Formula in a Belief Revision Scenario}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.24963/ijcai.2019/258},
}
Figure