d4-conf-aaai-2007-0023

The strongest mirror I see is for the paper’s majority merging query. The paper treats a knowledge profile as a multiset, so repeated copies of the same knowledge base already contribute repeatedly to the majority objective. Replacing their counts with rational masses is a direct extension of that model.

My anchor is Corollary 2, proved in this paper using Proposition 11 and a cited result of Konieczny, Lang, and Marquis (2004). It says that for \(\Delta=\Delta_{\max}\) or \(\Delta_\Sigma\), the decision problem \(\mathrm{MERGE}(B_{E,\mu,\Delta})\)—given \(\langle E,\mu,(\phi,a),\Delta\rangle\), decide whether \(B_{E,\mu,\Delta}\vdash_\pi(\phi,a)\)—is in \(k\cdot\Theta_2^p\) when the threshold \(a\) lies at priority level \(k\). Here \(\Theta_2^p\) is deterministic polynomial time with logarithmically many NP-oracle calls. The paper writes the interval as \(a_{k-1}<a\le a_k\); its earlier algorithm orders the levels in the opposite direction, so the intended meaning is the position of \(a\) among the priority levels. This is an upper bound, not a hardness result. The paper gives no comparable named hardness result, so this is the algorithmic anchor I would use.

I would name the mirror Continuous Majority Possibilistic Merge Query. An instance has a finite propositional vocabulary, integrity constraints \(\kappa\), a query \((\phi,a)\), and a finite support \(T\) of source types. Each type \(t\) is a complete possibilistic knowledge base \(B_t\), including its formulas and certainty weights; its mass \(\rho_t\in\mathbb{Q}_{>0}\) is the fraction of sources of that type, with \(\sum_{t\in T}\rho_t=1\). The support size is \(\tau=|T|\). Take source bases whose relevant formula strata are consistent, so the model-based distances are defined.

Let \(\lambda_1>\cdots>\lambda_\ell\) be the distinct certainty levels. At level \(\lambda_r\), let \(K_t^r\) be the formulas of type \(t\) at that level, and let \(S_1=\operatorname{Mod}(\kappa)\). For each round, the merger selects the surviving worlds minimizing the mass-weighted majority distance:
\[ S_{r+1} =\arg\min_{\omega\in S_r} \sum_{t\in T}\rho_t\,d_H(\omega,K_t^r), \qquad d_H(\omega,K)=\min_{\nu\models\bigwedge K}d_H(\omega,\nu). \]
An empty stratum contributes distance zero. As in the paper’s Algorithm 1, worlds excluded by the integrity constraints get possibility zero, worlds removed at level \(\lambda_r\) get possibility \(1-\lambda_r\), and final survivors get possibility one. The decision question is whether the resulting canonical possibilistic base entails \((\phi,a)\) under the paper’s Definition 3, including its maximality condition at degree \(a\). Thus the changing object is the population of sources; the output remains the paper’s possibility distribution over propositional worlds.

A plausible regime is a large multi-agent system in which many deployed assistants or monitoring agents use one of a modest number of signed, prioritized knowledge-base templates about the same incident. For example, millions of agents might fall into a few dozen complete rule-and-confidence profiles. A type here means the entire weighted knowledge base, not merely a shared formula or a named individual’s partial description. Mass means the share of participating sources using that profile.

This is close to the authors’ problem: their agents are already knowledge sources, their profiles are multisets, and \(\Delta_\Sigma\) aggregates their distances. If a discrete profile has \(n_t\) copies of each type among \(N\) sources, setting \(\rho_t=n_t/N\) multiplies every majority objective by \(1/N\), leaving every set of minimizing worlds unchanged. The continuous question therefore contains the discrete one exactly, while also allowing arbitrary rational source shares.

I expect Class B, hardness transfers, in the sense that any lower bound for the corresponding discrete majority-merge query carries into this continuous problem: discrete profiles embed as rational frequency vectors, and the propositional model search remains. That is a prediction about the mirror, not a claim established by Corollary 2. The paper’s anchor supplies an upper bound only. A prover could ask whether arbitrary rational masses preserve the \(k\cdot\Theta_2^p\) upper bound, and whether the problem admits useful algorithms parameterized by \(\tau\) or the number of priority levels.

The main weakness is the regime: a population of repeated knowledge sources is less immediately compelling than a population of voters, and some applications may really have only a handful of stakeholders. The anchor also gives no hardness result whose dissolution could be measured. Still, the mirror survives those limits because it is a direct measure-based extension of the paper’s multiset model, rather than a simplification of what gets merged. It covers the computational complexity of the possibilistic consequence query for majority merging; it does not claim to continuize the paper’s other logical properties.