Abstract
Consensus extraction involves identifying the largest possible set of information that does not logically contradict any individual source within a multi-agent group. Unlike traditional merging, which may override minority views, consensus focuses on positions acceptable to all participants. This paper introduces a framework that transforms this computationally intensive problem into a Weighted Partial MaxSAT optimization task. By utilizing linking variables and preference-based weighting, the proposed method efficiently handles large-scale datasets with millions of variables and clauses. Empirical results on real-world benchmarks demonstrate the approach's effectiveness and its scalability across varying numbers of sources.
Introduction
In multi-agent systems, reconciling conflicting information is a fundamental challenge. While standard merging techniques often rely on majority rules or distance-based metrics that may contradict some sources, many applications—such as legal agreements or political negotiations—require a consensus. A consensus is defined as a set of beliefs that is consistent with every agent's individual knowledge base.
Extracting a maximal consensus is computationally difficult, residing in high complexity classes like $FP^{NP}[wit, log]$. Traditional iterative search methods fail to scale as the number of formulas and sources increases. This work addresses these challenges by providing a formal logic-based framework and a scalable transformation to MaxSAT.
Methodology
The core of the proposed approach is the transformation of the consensus problem into a single instance of Weighted Partial MaxSAT.
Formal Definition
A consensus $\Gamma$ is a subset of the union of all sources $\bigcup \Phi_i$ such that for every source $\Phi_i$, the set $\Gamma \cup \Phi_i$ is satisfiable. The goal is to find a $\Gamma$ that is maximal according to specific criteria.
MaxSAT Encoding
To check consistency across $n$ sources simultaneously, the framework creates $n$ copies of the problem. "Linking variables" ($\epsilon$) are introduced to represent the inclusion of a formula in the consensus. By renaming variables within each source's sub-problem while keeping the linking variables consistent, a single SAT solver can ensure global consistency.
Preference Handling
Weights are assigned to linking variables to enforce different maximality criteria. For instance, high weights can prioritize the inclusion of specific "concepts" or maximize the number of sources whose entire knowledge base is satisfied. This allows for stepwise prioritization, where the solver first optimizes for primary goals before considering secondary ones.
Experimental Evaluation
The framework was evaluated using 291 unsatisfiable instances from the 2011 MUS competition, representing complex real-world benchmarks with up to 15 million clauses and 4 million variables. Each instance was partitioned into $n$ sources, where $n \in \{3, 5, 7, 10\}$.
Performance and Scalability
The transformation-based approach proved highly efficient. As shown in Figure 1, the method successfully solved a significant portion of the benchmark instances. For simple maximality (Row 1), 235 out of 291 instances were solved for $n=3$.
As the number of sources ($n$) increases, the problem size grows linearly, leading to a gradual decrease in the number of solved instances (e.g., 207/291 for $n=10$ in Row 1). Furthermore, complex preference criteria (such as those in Rows 2 and 6) proved more challenging for the solver due to increased variable dependencies.
Discussion and Conclusion
The proposed MaxSAT-based framework enables the extraction of consensuses from massive, conflicting datasets that were previously intractable. It highlights that a consensus can contain information unique to a single source, provided it is not negated by others, and can even reveal implicit group knowledge.
However, limitations remain. The use of 64-bit weights in current MaxSAT solvers restricts the number of priority levels that can be handled. Additionally, the requirement for CNF input can be a hurdle for complex knowledge bases. Future work will explore applications in argumentation frameworks and further optimize multi-step optimization processes.
Summary updated