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).
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.
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