Research map / Multi-agent systems and games / Human-AI and goal-conditioned
BeliefFlow: A Framework for Logic-Based Belief Diffusion via Iterated Belief Change
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces Belief Flow Networks, where agents asynchronously update epistemic states via improvement operators, proving consensus under strong connectivity and polynomial-time optimal bribery.
Problem
Predicting whether logical beliefs in a network of asynchronously communicating agents converge to consensus, and how to influence collective beliefs, when agents use iterated belief change rather than one-step revision.
Approach
Model belief diffusion with epistemic states updated by iterated improvement operators under asynchronous random edge activation; show stability and unanimous consensus for strongly connected graphs and characterize stability via condensation of the acquaintance graph, enabling minimal-cost bribery computed in polynomial time.
Key results
- Under strong network connectivity, every BFN is stable and strongly consensual (Corollary 2), and the class of BFNs for a graph is stable iff its condensation is a tree (Corollary 3).
- Minimal-cost successful influence scheme for any formula can be computed in time polynomial in graph size by bribing one agent per source SCC (Proposition 8, Corollary 4).
- Simulations with 20 agents over 10,000 instances per graph type reached stable consensus within 500 steps in half of instances for complete, Barabasi-Albert and Kleinberg graphs.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use a strongly connected acquaintance graph | BeliefFlow Network · Strongly connected networks | stability and consensus | Helped |
| use a condensation graph that is a tree | BeliefFlow Network · Arbitrary network topology | stability | Helped |
| bribe at least one agent in each source strongly connected component with a belief implying the target formula | BeliefFlow Network · Bribed networks | unanimous acceptance | Helped |
| select a minimum-cost set of agents, one per source strongly connected component | BeliefFlow Network · Bribery strategy | computation time | Helped |
| use strongly connected social-network graph types in the simulations | BeliefFlow Network · Empirical study | steps to stable consensus | Helped |
Surprising findings
- BFNs do not satisfy the responsiveness property that BRGs satisfy, because improvement operators need not revise beliefs on receiving inconsistent information.
- Stability fails even in simple graphs: an SCC with two or more parent SCCs can be unstable for some BFN instances (Proposition 4).
Limitations
- Results are theoretical and experiments are only proof-of-concept with a fixed small setup (20 agents, 4 variables).
- Does not satisfy monotonicity or responsiveness properties.
- Bribery cost model assumes all agents have equal cost.
Experimental setup
Metrics: number of steps to reach stable consensus steps to unanimous acceptance under bribery
Baselines: Belief Revision Games
Builds on: Belief Revision Games improvement operators AGM theory Darwiche-Pearl iterated revision
Closest papers by meaning
- From Debate to Equilibrium: Belief‑Driven Multi‑Agent LLM Reasoning via Bayesian Nash Equilibrium (ICML 2025 · similarity 0.85)
- Differentiable Belief-based Opponent Shaping (NeurIPS 2026 · similarity 0.84)
- Reducing Belief Deviation in Reinforcement Learning for Active Reasoning (ICLR 2026 · similarity 0.84)
- Tools as Continuous Flow for Evolving Agentic Reasoning (NeurIPS 2026 · similarity 0.83)
- Systematic Failures in Collective Reasoning under Distributed Information in Multi-Agent LLMs (ICML 2026 · similarity 0.83)
- Martingale Score: An Unsupervised Metric for Bayesian Rationality in LLM Reasoning (NeurIPS 2025 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.