pith. sign in

arxiv: 2605.02249 · v1 · submitted 2026-05-04 · 💻 cs.AI

A Study of Belief Revision Postulates in Multi-Agent Systems (Extended Version)

Michael Thielscher , Tran Cao Son This is my paper

Pith reviewed 2026-05-09 16:25 UTC · model grok-4.3

classification 💻 cs.AI
keywords belief revisionAGM postulatesmulti-agent systemsepistemic planningKripke modelsdynamic epistemic logiciterated revision
0
0 comments X

The pith

The classical AGM belief revision postulates can be generalized to multi-agent epistemic planning using Kripke models.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper examines how beliefs of all agents change when one agent acquires new information in a multi-agent system. It lifts the standard AGM postulates to this setting by representing collective beliefs in a single Kripke model. The generalization supplies criteria for judging whether operators that compute belief updates after actions behave rationally. A simple generalized full-meet revision operator is shown to meet every lifted postulate. The work also formulates postulates for iterated revision and identifies difficulties in constructing Kripke-model operators that satisfy all of them simultaneously.

Core claim

Based on the standard representation in epistemic planning of agents' beliefs via a single multi-agent Kripke model, the classical AGM belief revision postulates can be generalized to the multi-agent setting. This supplies a formal framework for evaluating dynamic epistemic reasoning frameworks. A generalized full-meet multi-agent belief revision operator satisfies all the new postulates. Generalizations of the standard postulates for iterated revision are defined, and issues are discussed in finding an epistemic operator on Kripke models that satisfies all of them.

What carries the argument

The single multi-agent Kripke model, which encodes the beliefs of every agent and permits the AGM postulates to be lifted so that post-action belief states can be checked for rationality.

Load-bearing premise

Agents' beliefs in epistemic planning are adequately captured by a single multi-agent Kripke model, allowing the AGM postulates to be lifted without loss of essential properties.

What would settle it

A concrete multi-agent scenario and action in which every intuitive belief-update operator violates at least one generalized AGM postulate, or an operator that obeys all the postulates yet produces belief changes that no reasonable agent would accept.

Figures

Figures reproduced from arXiv: 2605.02249 by Michael Thielscher, Tran Cao Son.

Figure 1
Figure 1. Figure 1: Two pointed Kripke structures (M1, s) and (M2, s) with the same “true” world s (marked with a double circle — so both structures agree that p is actually true) but which determine differ￾ent multi-agent belief sets K1 = K(M1,s) and K2 = K(M2,s). and Makinson (1985), a.k.a. AGM, proposed the following eight basic postulates for one-shot belief revision: • Closure: KM∗p = Cn(KM∗p) • Success: p ∈ KM∗p • Inclu… view at source ↗
Figure 2
Figure 2. Figure 2: The Kripke model resulting from expanding view at source ↗
Figure 3
Figure 3. Figure 3: A Kripke structure in which p is common belief among agents a, b is expanded by the new belief Ba¬p. Agent b’s first￾and higher-order beliefs remain unchanged thanks to the retained, b-reachable copy of the old structure (bottom) whereas there is no a-reachable world in the replica (top), hence Ba⊥ after expansion. Lemma 3. (M, s) + Baφ |= Baφ. Proof. By definion of the entailment of formulas from a pointe… view at source ↗
Figure 4
Figure 4. Figure 4: Revising with Baf is not the same as sensing f In the model (M, s) (left), simplified to consider only a sin￾gle agent, a does not believe f nor ¬f. The event model for sensing f is in the middle, whose update on (M, s) is (M′ , s′ ) (right), which indicates that a believes ¬f after sensing f. Such an update does not allow for the revision of (M, s) with Baf. To accommodate the discussion of the generalize… view at source ↗
Figure 5
Figure 5. Figure 5: Revision event model for Baφ where p, q are literals and, for each u and p, there is a unique u ′ = CR((u ∩ u ′ ) ∪ {p}), since this is sufficient for dealing with the DP1 and DP2 postulates. Consider a ∈ A and a set of literals φ. We define Σa (φ), called the event model for revision by Baφ, as the event model ⟨Σ, {Ea}a∈A, pre, eff ⟩ where • Σ = {σ, δ, σa, δa, ϵ}; • Ea = {(σ, σa),(σa, ϵ),(δ, δa),(δa, ϵ),(… view at source ↗
read the original abstract

We investigate the belief revision problem in epistemic planning, i.e., what will be the beliefs of all agents in a multi-agent system after an agent gains the belief in some state property. Based on the standard representation in epistemic planning of agents' beliefs via a single multi-agent Kripke model, we generalize the classical AGM belief revision postulates to the multi-agent setting, with the aim to provide a formal framework for evaluating dynamic epistemic reasoning frameworks in which the beliefs of all agents as the result of actions are computed. As an example of a simple operator that satisfies all of the generalized AGM postulates, we present generalized full-meet multi-agent belief revision. We moreover define a generalization of the standard postulates for iterated revision, present a more sophisticated, event model based revision operator, and discuss the potential issues in defining an epistemic operator on Kripke models that can satisfy all of the generalized postulates for iterated multi-agent belief revision.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

3 major / 2 minor

Summary. The paper generalizes the classical AGM belief revision postulates to multi-agent epistemic planning, where agents' beliefs are represented in a single shared Kripke model. It aims to create a formal framework for evaluating dynamic epistemic reasoning by defining lifted versions of the AGM postulates (success, consistency, minimality, etc.) that apply to the target agent's beliefs after revision. As a concrete example, it introduces a generalized full-meet multi-agent belief revision operator claimed to satisfy all the lifted postulates. The work also extends the approach to iterated revision by defining generalized iterated postulates, presenting an event-model-based operator, and discussing challenges in finding an operator that satisfies the full iterated set.

Significance. If the generalization can be shown to preserve independent per-agent belief updates without unintended cross-agent effects, the framework would provide a useful benchmark for assessing belief-change operators in multi-agent dynamic epistemic logic and epistemic planning. The explicit treatment of iterated revision is a positive step toward handling sequences of updates. The paper correctly identifies the tension between shared-model representations and per-agent independence as a key issue for future work.

major comments (3)
  1. [Abstract; definition of generalized full-meet operator] Abstract and the section defining the generalized full-meet operator: the claim that this operator satisfies all the generalized AGM postulates is stated without any formal proof, derivation, or exhaustive counter-example check. Because the central contribution is the generalization and its satisfaction by a concrete operator, the absence of verification makes the soundness of the main result unestablished.
  2. [Introduction; definition of generalized full-meet operator] The construction of the revision operator on a single multi-agent Kripke model (described in the introduction and the operator definition): no invariance lemma or explicit argument is given showing that a revision targeting one agent leaves the accessibility relations and belief sets of all other agents unchanged. This is load-bearing for the claim that the framework evaluates dynamic epistemic reasoning 'without loss of essential properties,' because entanglement of accessibility relations could alter non-target agents' beliefs even when the revision is intended to affect only one agent.
  3. [Section on iterated revision and event-model operator] The section on iterated revision and the event-model-based operator: the generalized iterated postulates are defined and an operator is presented, yet the text does not verify that the operator satisfies the full set of lifted iterated postulates (analogous to the basic case). The discussion of 'potential issues' is noted but does not substitute for a concrete check or counter-example.
minor comments (2)
  1. [Abstract] The abstract refers to 'sketches an iterated version' while the body provides a more detailed treatment; updating the abstract to reflect the actual content would improve accuracy.
  2. [Definitions of generalized postulates] Notation for the lifted postulates and the multi-agent Kripke model could be clarified by explicitly distinguishing the target agent's accessibility relation from those of other agents in the formal definitions.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for the detailed and constructive feedback. We address each major comment below and will revise the manuscript to include the requested formal verifications.

read point-by-point responses

  1. Referee: [Abstract; definition of generalized full-meet operator] Abstract and the section defining the generalized full-meet operator: the claim that this operator satisfies all the generalized AGM postulates is stated without any formal proof, derivation, or exhaustive counter-example check. Because the central contribution is the generalization and its satisfaction by a concrete operator, the absence of verification makes the soundness of the main result unestablished.

    Authors: We agree that the submitted manuscript omitted an explicit formal proof. The generalized full-meet operator was constructed to satisfy the lifted postulates by design, but the derivation was not detailed. In the revised version we will add a dedicated proof subsection (or appendix) establishing that the operator satisfies all generalized AGM postulates, including success, consistency, and minimality, via direct verification on the multi-agent Kripke model. revision: yes

  2. Referee: [Introduction; definition of generalized full-meet operator] The construction of the revision operator on a single multi-agent Kripke model (described in the introduction and the operator definition): no invariance lemma or explicit argument is given showing that a revision targeting one agent leaves the accessibility relations and belief sets of all other agents unchanged. This is load-bearing for the claim that the framework evaluates dynamic epistemic reasoning 'without loss of essential properties,' because entanglement of accessibility relations could alter non-target agents' beliefs even when the revision is intended to affect only one agent.

    Authors: We will add an invariance lemma in the revised manuscript. The lemma will show, by construction of the generalized full-meet operator, that updates are confined to the target agent's accessibility relations and worlds; the epistemic states of non-target agents remain unchanged because the operator modifies only the relevant equivalence classes for the target agent while preserving the shared model structure for others. revision: yes

  3. Referee: [Section on iterated revision and event-model operator] The section on iterated revision and the event-model-based operator: the generalized iterated postulates are defined and an operator is presented, yet the text does not verify that the operator satisfies the full set of lifted iterated postulates (analogous to the basic case). The discussion of 'potential issues' is noted but does not substitute for a concrete check or counter-example.

    Authors: We will augment the iterated-revision section with an explicit verification step or counter-example analysis for the event-model-based operator against the complete set of generalized iterated postulates. This will identify precisely which postulates hold and will expand the existing discussion of potential issues into a formal assessment of the remaining limitations. revision: partial

Circularity Check

0 steps flagged

Generalization of AGM postulates via standard Kripke semantics is self-contained and externally grounded

full rationale

The paper explicitly lifts the classical AGM postulates (external, 1985) to multi-agent Kripke models by requiring post-revision models to satisfy success, consistency, and minimality conditions only for the target agent; the generalized full-meet operator is then constructed to meet these lifted conditions by definition, which is a standard verification step rather than a reduction of the central claim to its own inputs. No self-citation chain, fitted parameters, or ansatz smuggling is used to justify the framework; the iterated-revision discussion openly flags open issues instead of claiming closure. The single-model representation is adopted from epistemic planning literature as an assumption, not derived inside the paper, so the derivation chain remains non-circular.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper relies on the prior AGM postulates and the standard semantics of multi-agent Kripke models; no new free parameters, ad-hoc axioms, or invented entities are introduced.

axioms (2)
  • domain assumption AGM postulates are the correct normative standard for single-agent belief revision
    Basis for the multi-agent generalization.
  • domain assumption A single multi-agent Kripke model suffices to represent all agents' beliefs and higher-order beliefs
    Central representational choice stated in the abstract.

pith-pipeline@v0.9.0 · 5453 in / 1212 out tokens · 43490 ms · 2026-05-09T16:25:40.454964+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

14 extracted references · 14 canonical work pages

  1. [1]

    Baral, G

    Proceedings of the 13th Workshop on Logic, Language, Information and Computation (WoLLIC 2006). Baltag, A., and Smets, S. 2008. A qualitative theory of dynamic interactive belief revision. InProc. of 7th LOFT, Texts in Logic and Games 3, 13–60. Amsterdam University Press. Baltag, A.; Moss, L.; and Solecki, S. 1998. The logic of pub- lic announcements, com...

    work page arXiv 2006

  2. [2]

    Technical report, Dagstuhl

    Epistemic planning. Technical report, Dagstuhl. Baral, C.; Gelfond, G.; Pontelli, E.; and Son, T. C. 2022. An action language for multi-agent domains.Artificial Intelli- gence302:103601. Bolander, T., and Andersen, M. 2011. Epistemic Planning for Single and Multi-Agent Systems.Journal of Applied Non-Classical Logics21(1). Bolander, T. 2017. A gentle intro...

    work page arXiv 2022

  3. [3]

    InProceedings of the International Conference on Principles of Knowledge Representation and Reasoning, 411–421

    Belief revision of logic programs under answer set semantics. InProceedings of the International Conference on Principles of Knowledge Representation and Reasoning, 411–421. Ditmarsch, H. v.; van der Hoek, W.; and Kooi, B. 2007. Dynamic Epistemic Logic. Springer Publishing Company, Incorporated, 1st edition. Dragoni, A. F., and Giorgini, P. 1996. Belief r...

    work page 2007

  4. [4]

    Fagin, R.; Halpern, J.; Moses, Y .; and Vardi, M

    IEEE Computer Society. Fagin, R.; Halpern, J.; Moses, Y .; and Vardi, M. 1995.Rea- soning about Knowledge. MIT Press. Herzig, A.; Lang, J.; and Marquis, P. 2005. Action Pro- gression and Revision in Multiagent Belief Structures. In Sixth Workshop on Nonmonotonic Reasoning, Action, and Change (NRAC). Hunter, A., and Delgrande, J. P. 2011. Iterated belief c...

    work page 1995

  5. [5]

    Tu, P.; Son, T.; Gelfond, M.; and Morales, R

    Springer. Tu, P.; Son, T.; Gelfond, M.; and Morales, R. 2011. Approx- imation of action theories and its application to conformant planning.Artificial Intelligence175(1):79–119. van Benthem, J.; van Eijck, J.; and Kooi, B. P. 2006. Logics of communication and change.Inf. Comput.204(11):1620– 1662. van Benthem, J. 2007. Dynamic logic of belief revision. Jo...

    work page 2011

  6. [6]

    Suppose thatB a¬φ̸∈K (M,s), then the definition of∗ fm implies thatK (M,s) ∗fm Baφ⊆K (M,s) +B aφ

    work page

  7. [7]

    Taken together,K (M∅,s) +B aφ⊆K (M,s) +B aφ, hence K(M,s) ∗fm Baφ⊆K (M,s) +B aφ

    IfB a¬φ∈K (M,s), then (a)R ′ a(s′) =∅where(M ′, s′) = (M, s) +B aφ, hence K+B aφ|=B a⊥by Lemma 3, which implies that K(M,s) +B aφ|=B aψfor any proposition formulaψ; (b) forx∈ A \ {a},(M ∅, s)|=B xψif, and only if,|=ψ; by Lemma 2 this holds for(M ∅, s) +B aφas well, henceK (M∅,s) +B aφ|=B bψonly for tautologiesψ. Taken together,K (M∅,s) +B aφ⊆K (M,s) +B aφ...

    work page

  8. [8]

    Hence, agentahas cosistent beliefs inK (M,s) ∗fm Baφ

    IfB a¬φ̸∈K (M,s), then(s ′, vr)∈R ′ a for somev r ∈W ′ such thatπ[v r]|=φ, where(M ′, s′) = (M, s) +B aφ. Hence, agentahas cosistent beliefs inK (M,s) ∗fm Baφ

    work page

  9. [9]

    Hence, agentahas cosistent beliefs inK (M,s) ∗fm Baφ

    IfB a¬φ∈K (M,s), then(s ′, vr)∈R ′ a for somev r ∈W ′ such thatπ[v r]|=φ, where(M ′, s′) = (M ∅, s) +B aφ. Hence, agentahas cosistent beliefs inK (M,s) ∗fm Baφ. Consistency 2IfB aφis consistent withKthen the be- liefs of any agent other thanado not change as a result of expanding(M, s)byB aφ. IfB aφis inconsistent, then any agent other thanahas tautologic...

    work page

  10. [10]

    SinceKis deductively closed, it follows thatB a¬φ̸∈K

    SupposeB a¬(φ∧ψ)̸∈K. SinceKis deductively closed, it follows thatB a¬φ̸∈K. Hence, agentahas consistent beliefs inK+B a(φ∧ψ), inK+B aφ, and in(K+B aφ) +B aψ. By Lemma 4 it follows that (M, s) +B a(φ∧ψ)|=B aχiffχ∈Cn({φ∧ψ} ∪ {ϕ∈ BA,P |B aϕ∈K}). This is equivalent toχ∈Cn({ψ} ∪ Cn({φ} ∪ {ϕ∈ B A,P |B aϕ∈K})), which in turn by Lemma 4 is equivalent to(K+B aφ)+B ...

    work page

  11. [11]

    By definition of(M ∅, s) + Ba(φ∧ψ)and Lemma 4 it follows that, for any first- degree belief,B aϕ∈K∗ fm Ba(φ∧ψ)iffϕ∈Cn(φ∧ψ), and forx∈ A \ {a},B xϕ∈K∗ fm Ba(φ∧ψ)iff|=ϕ

    SupposeB a¬(φ∧ψ)∈K. By definition of(M ∅, s) + Ba(φ∧ψ)and Lemma 4 it follows that, for any first- degree belief,B aϕ∈K∗ fm Ba(φ∧ψ)iffϕ∈Cn(φ∧ψ), and forx∈ A \ {a},B xϕ∈K∗ fm Ba(φ∧ψ)iff|=ϕ. (a) SupposeB a¬φ̸∈K, then(K∗ fm Baφ) +B aψ= (K+B aφ) +Baψ. FromB a¬(φ∧ψ)∈Kit follows thatB a¬ψ∈K+B aφ. Hence,ahas inconsistent beliefs in(K+B aφ) +B aψwhile the beliefs ...

    work page 2007

  12. [12]

    Conse- quently,(K∗ fm Baφ)∗ fm Bbψ⊆K∗ fm Bbψ

    Suppose|=φ↔ ⊥thenB a¬φ∈K, hence K∗ fm Baφ=K (M∅,s) +B a⊥, that is, there is noa- accessible world inswhile all other agents’ first-degree beliefs are tautological proposition formulas. Conse- quently,(K∗ fm Baφ)∗ fm Bbψ⊆K∗ fm Bbψ

    work page

  13. [13]

    It follows thatB bψ̸∈K∗ fm Baφ, hence (K∗ fm Baφ)∗ fm Bbψ=K (M∅,s) +B bψ, which implies (K∗ fm Baφ)∗ fm Bbψ⊆K∗ fm Bbψ

    Otherwise,|=B bψ→B aφimpliesa=bandψ|=¬φ, henceφ|=¬ψ. It follows thatB bψ̸∈K∗ fm Baφ, hence (K∗ fm Baφ)∗ fm Bbψ=K (M∅,s) +B bψ, which implies (K∗ fm Baφ)∗ fm Bbψ⊆K∗ fm Bbψ. DP3 – Consistency preservation across revisionsIf|= φ↔ ⊤then DP3 holds trivially. Otherwise,B aφ∈ K∗ fm Bbψimplies thatB bψis consistent withK∗B aφun- less|=ψ→ ⊥. But if the latter is t...

    work page

  14. [14]

    ClosureBy our definition, it is clear that K∗ ev Baφ=Cn(K∗ ev Baφ)

    IfR={p→ ¬q, q→ ¬p}then •if{p, q} ∩φ=∅thenu ⋆ φ= (u\ ¬φ)∪φ; •ifp∈φthenu ⋆ φ= (u\ ¬φ∪ {q})∪φ∪ {¬q}; and •ifq∈φthenu ⋆ φ= (u\ ¬φ∪ {p})∪φ∪ {¬p}. ClosureBy our definition, it is clear that K∗ ev Baφ=Cn(K∗ ev Baφ). SuccessWe show thatK∗ ev Baφ|=B aφ. Consider two cases: 1.(M, s)|=¬B a¬φ, i.e.,adoes not believe in¬φbefore the revision. This implies thats φ = (s,...

    work page