| paper | d4-journals-jair-2003-0017 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: Polynomial-time solvable · discrete side: other · adjudication: proved
full proof & adversarial review →
Proposition 20
statement extracted from the paper’s text layer
Given a finite set of worlds \(\Omega\), finite ordered credibility ranks \(R\), and a distribution \(\mu\) with binary rational masses over \(\tau\) explicitly represented pedigreed agent types \(t=(\prec^t,\ell^t)\), compute the fused pedigreed state and its induced belief state. Put \((x,y)\) in the fused relation \(\prec\) if some \(t\in\operatorname{supp}(\mu)\) and \(r\in R\) have \((x,y)\in\prec^t_r\), and every supported type \(u\) is agnostic in both directions at every rank \(r'>r\). Set \(\ell(x,y)=\max\{r:(x,y)\in\prec^t_r\text{ for some }t\in\operatorname{supp}(\mu)\}\); return \((\prec,\ell)\) and the induced relation \(\prec^+\).
A continuum of agent mass over complete pedigreed belief-state types, with fusion applied once to each type in \(\operatorname{supp}(\mu)\), as in the paper’s set-based semantics. Mass values describe prevalence; the fused output depends on the supported types, not their proportions.
The mirror covers the pedigreed fusion computation in Proposition 20, including its induced belief state; it leaves the paper’s representation results, aggregation axioms, and other propositions aside.
The strongest case I see is narrow: the paper’s Proposition 20, proved here (its proof appears as Proposition 41 after the appendix resets the numbering), gives a constructive result for computing the fusion of agents from their pedigreed belief states. The paper has no named NP-hardness result or complexity-class theorem, so this is an algorithmic anchor rather than a hardness one.
Proposition 20 says that, when the agents share a total pre-order of source credibility, their fused pedigreed belief state can be computed from the agents’ pedigreed states alone. For a world pair \((x,y)\), the fused relation includes \((x,y)\) if some agent supports it at rank \(r\), and every agent is agnostic about that pair at every higher rank. The pair’s label is the highest rank at which any agent supports \((x,y)\). The resulting relation and labels are the pedigreed state of the agents’ fusion. This is the paper’s own result, not a citation.
A continuous version, Continuous Pedigreed Fusion, would take a finite set of possible worlds \(\Omega\), a finite ordered set of credibility ranks \(R\), and a distribution \(\mu\) over agent types. A type \(t\) is a complete pedigreed belief state: its pairwise likelihood relations, with each opinion labeled by its credibility rank. The input lists the \(\tau\) types with positive rational mass, where \(\mu_t\) is their fraction of the population. The task is to return the fused pedigreed state and its induced belief state. Concretely, put \((x,y)\) in the fused relation if there are a supported type \(t\) and rank \(r\) with \((x,y)\) at rank \(r\), and every supported type is agnostic about both directions at every rank above \(r\). Label the pair by the highest rank at which any supported type has \((x,y)\). The induced belief state is the transitive closure of that relation. This is a function problem, not an optimization problem: the fused state is the required output, with no separate objective.
A plausible regime is a large network of regional monitoring or operations centers reporting beliefs about a shared finite set of possible incidents. Standardized telemetry, reporting procedures, and credibility policies could produce millions of centers but relatively few distinct rank-labeled belief states. An agent type records everything this fusion rule uses, so grouping centers by type preserves the problem. The high-multiplicity question is whether one can compute the network’s fused belief state from that distribution over types.
I expect this mirror to be tractable when \(\Omega\) and each type’s relations are represented explicitly: scan the supported types and ranks to construct the relation and labels, then compute transitive closure. That gives a direct polynomial-time algorithm in \(|\Omega|\), \(\tau\), and \(|R|\); Proposition 20 supplies the computation rule, while the complexity bound is an inference from that explicit representation, not a classification proved in the paper. The mirror covers the pedigreed fusion computation, not the paper’s axiomatic results or its other aggregation claims.
The weakness is substantial: the fused state depends on which types have positive mass, not on their mass values. A type representing \(1\%\) of the centers and one representing \(90\%\) have the same effect if both are present. So the continuous problem is meaningful as a high-multiplicity description of a network, but it adds no quantity-sensitive aggregation and does not open a new complexity landscape by itself. That limits the case; it does not erase the narrow mirror of Proposition 20, which preserves the paper’s fusion rule and asks for its exact output in a high-multiplicity regime.
The only computational anchor is Proposition 20, and it gives an aggregation identity rather than a complexity result. The paper has no named theorem classifying the complexity of a computational problem. Its continuous mirror therefore starts from an explicit pairwise computation, not from a complexity landscape the programme could chart.
Under the proposed encoding, for each pair of worlds one scans the \(\tau\) supported pedigreed types and the credibility ranks, then computes transitive closure. With explicit relations, this is polynomial in \(|\Omega|,\tau,\) and \(|R|\); the mass bit lengths do no work. The output depends only on \(\operatorname{supp}(\mu)\): changing any positive mass leaves it unchanged. That follows from the paper’s set based fusion semantics, including its idempotence. Millions of standardized monitoring centers are a plausible high multiplicity regime, but their percentages have no bearing on this result. The mirror reduces to evaluating Proposition 20 on the distinct types present.
The strongest rescue would make the result quantity sensitive, as the conclusion’s proposed voting based extension suggests. But the paper gives no operator or result for that extension. Defining one would launch a new aggregation model, rather than continuize a computational result in this paper.
I would not claim that no plausible high multiplicity scenario exists; the monitoring center example is credible. The negative case is narrower: the paper’s only candidate is already an explicit, straightforward computation whose output ignores population mass. That makes the universal claim difficult to establish, while leaving little here that warrants a continuous complexity study.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.