Proportional Belief Merging

Adrian Haret, Martin Lackner, Andreas Pfandler, Johannes Peter WallnerAAAI 2020 · DOI

Introduction

Belief merging is a fundamental framework in artificial intelligence and multi-agent systems, designed to aggregate conflicting information from multiple sources into a single, consistent collective belief. Traditionally, merging operators have adhered to either utilitarian principles—maximizing total agreement—or egalitarian principles—minimizing the dissatisfaction of the most aggrieved agent. However, these approaches often fail to account for proportionality, a concept central to social choice theory. In scenarios like electing a representative body, proportionality ensures that a group of voters is represented in the outcome relative to its size. This paper bridges the gap between social choice and formal logic by introducing proportional belief merging operators.

Proportional Merging Operators

The challenge in belief merging lies in the complex logical interdependencies between issues, which makes defining "fair shares" more difficult than in simple voting. To address this, the authors shift from traditional distance-based merging to satisfaction-based operators. They introduce three primary novel operators:

  1. The PAV Operator ($\Delta^{PAV}$): Directly inspired by Proportional Approval Voting, this operator utilizes a harmonic weight system ($1, 1/2, 1/3, \dots$). This system provides diminishing returns for each additional point of satisfaction an agent receives, incentivizing the aggregation process to distribute satisfaction across a broader range of agents.
  2. The Bounded PAV Operator ($\Delta^{bPAV}$): A refinement of the PAV operator designed to penalize "inflationary" outcomes, preventing agents from gaining unfair influence by simply asserting more true atoms.
  3. The Harmonic Hamming Operator ($\Delta^{hH}$): A binary variant that treats positive and negative agreement (agreeing on truth vs. agreeing on falsehood) with equal weight.
Table illustrating the PAV operator's use of harmonic weights to determine collective outcomes.

Theoretical Analysis and Postulates

The researchers evaluated these operators against the IC-postulates, the standard "sanity checks" for logical merging. A key discovery is the Proportionality Split, which identifies two distinct and incompatible types of proportionality:

  • Classical Proportionality ($IC_{cp}$): Based on positive satisfaction (the number of desired items selected).
  • Binary Proportionality ($IC_{bp}$): Based on total agreement (closeness in terms of Hamming distance).

A significant theoretical contribution is the Fairness-Logic Trade-off. The authors prove that any operator satisfying classical proportionality must necessarily fail the $IC_2$ postulate (the Unanimity principle). This implies that to achieve true social-choice proportionality, one must occasionally exclude an outcome that all agents technically agree upon if that outcome undermines the fair representation of a specific sub-group.

Results and Complexity

The study identifies $\Delta^{bPAV}$ as a unique operator that successfully balances proportionality with specific logical fairness requirements, such as postulate $IC_4$. Furthermore, Theorem 7 establishes an incompatibility result: no merging operator can simultaneously satisfy basic logical consistency ($IC_1$) and both types of proportionality (Classical and Binary).

From a computational standpoint, the authors demonstrate that these new proportional operators are generally $\Theta^P_2$-complete or $\Delta^P_2$-complete. This finding is crucial as it indicates that incorporating proportionality does not significantly increase the computational burden compared to standard, non-proportional merging methods.

Summary of merging operators, their satisfaction of IC-postulates, and computational complexity.

Conclusion

This work introduces a novel dimension to belief merging by formalizing proportionality. While the current postulates are restricted to specific profile types, they lay the groundwork for more general fairness criteria in logical aggregation. Future research will focus on developing stronger proportionality postulates, investigating the susceptibility of these operators to strategic manipulation, and extending these concepts to the related field of Judgment Aggregation.

Summary updated

BibTeX
@inproceedings{haret2020proportional,
  author = {Adrian Haret and Martin Lackner and Andreas Pfandler and Johannes Peter Wallner},
  title = {{Proportional Belief Merging}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.1609/aaai.v34i03.5671},
}

Loading related content...

Figure