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