On Consensus in Belief Merging

Nicolas Schwind, Pierre MarquisAAAI 2018 · DOI

Abstract

In multi-agent systems, belief merging often prioritizes global optimization, sometimes at the expense of individual agent acceptance. This paper introduces the "consensus" requirement, ensuring that merged results never contradict any agent's initial beliefs. We analyze the logical implications of this requirement, proving its incompatibility with several standard rationality axioms, and propose two new classes of operators—Pareto and $\nabla$—that successfully navigate this trade-off.

Introduction: The Challenge of Stubbornness

Belief merging is the process of aggregating diverse logical belief bases from multiple agents into a single, collective perspective. Traditional operators typically seek a "global optimum," which can lead to situations where the group's conclusion directly contradicts an individual agent's beliefs. In many real-world scenarios, such as legal or diplomatic negotiations, agents are "stubborn": if a group decision violates their internal logic, they will reject the outcome.

To address this, the authors propose the Consensus Postulate (CO). This axiom mandates that if an agent's beliefs are consistent with the overall constraints, the merged result must remain consistent with that agent's beliefs.

Axiomatic Conflicts and the Impossibility Result

A significant contribution of this work is the formal proof that the Consensus Postulate is fundamentally at odds with established "rationality" axioms in AI, specifically the IC (Integrity Constraint) postulates.

The paper demonstrates an impossibility result: no merging operator can satisfy (CO) while simultaneously satisfying both IC2 (Synergy)—which requires the merge to be the simple conjunction of beliefs if they are already compatible—and IC6 (Strong Pareto). This highlights a deep tension between reaching a consensus everyone can accept and maintaining certain types of group-level logical consistency.

New Families of Consensus Operators

To find a middle ground, the authors introduce two new families of operators:

  1. Pareto Consensus Operators: These utilize Pareto dominance. An interpretation (a possible state of the world) is included in the merged base only if no other interpretation is "closer" to every agent's belief base.
  2. $\nabla$ (Nabla) Operators: These are "meta-operators" that wrap around existing merging functions. A $\nabla$ operator considers how each agent would individually merge the beliefs of all other agents and then combines these individual perspectives. This approach acts as a form of logical arbitration.

Comparative Analysis and Inferential Power

A common pitfall for consensus-based methods is "weak inferential power"—the tendency to produce results so cautious that they contain almost no new information. The authors show that while simple Pareto methods often suffer from this, $\nabla$ operators provide a more robust solution.

Table 1: Comparison of interpretations selected by standard and consensus operators across different distance metrics.

As shown in the table above, different operators select different sets of interpretations ($\omega$). Standard operators like GMax and GMin (which do not necessarily satisfy consensus) are compared against the new $Par$ and $\nabla$ operators. The $\nabla$ construction is particularly effective because it allows agents to refine their beliefs through a structured arbitration process, leading to a more informative consensus than basic Pareto methods.

Conclusion and Future Directions

The introduction of the consensus requirement marks a shift from purely global optimization to a more agent-centric view of belief merging. While the incompatibility with certain IC postulates presents a theoretical hurdle, the $\nabla$ family of operators offers a practical path forward.

Future work remains in characterizing the computational complexity of these new operators and developing representation theorems to fully map the space of all possible consensus-satisfying functions. Additionally, exploring these concepts within specific logic fragments, such as Horn clauses, may reveal new properties and efficiencies.

Summary updated

BibTeX
@inproceedings{schwind2018consensus,
  author = {Nicolas Schwind and Pierre Marquis},
  title = {{On Consensus in Belief Merging}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.1609/aaai.v32i1.11543},
}

Loading related content...

Figure