| paper | d4-conf-aaai-2010-0267 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→NP-hard discrete result → its continuous mirror
Answer: Exact computation of \(p\) is \(\mathrm{NP}\)-hard, and deciding \(p\ge q\) is \(\mathrm{NP}\)-hard, already for \(\tau=1\), binary domains, and no importance edges. · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 1
Given a common set of features \(V\), two outcomes \(\alpha,\beta\), a fixed TCP-net semantics, and a finite support of complete TCP-net types \((N_j,\mu_j)_{j=1}^{\tau}\) with rational masses summing to \(1\), compute \(p=\sum_{j:\,\alpha\text{ dominates }\beta\text{ under }N_j}\mu_j\), and decide whether \(p\ge q\) for a rational threshold \(q\).
Types are complete TCP-nets, including their conditional preferences and relative-importance statements, with rational population masses \(\mu_j\). Test \(\alpha\)-to-\(\beta\) dominance for each type, then compute the exact mass-weighted prevalence \(p\); the instance parameters include feature count \(m\), support size \(\tau\), and input bit length \(L\).
Theorem 1 remains pointwise and gives no population-level complexity or batching guarantee; the prevalence query adds weighted aggregation across types.
fatal: False
The mirror covers the paper's dominance test and its witness-producing use of the Kripke encoding; it leaves other preference-reasoning tasks and the experimental performance claims unmirrored.
I would mirror the paper’s dominance query as a population dominance prevalence problem. Imagine a large marketplace whose customers choose bundles described by the same set \(V\) of binary product features. Customers are grouped into a small number of standardized preference profiles. Each profile is a TCP-net \(N_j\), including its conditional preferences and relative-importance statements; its mass \(\mu_j\) is the fraction of customers with that complete profile. For example, millions of customers might fall into tens or hundreds of such cohorts.
An instance consists of the common feature set \(V\), the supported types \((N_j,\mu_j)_{j=1}^{\tau}\), two bundles \(\alpha,\beta\), a rational threshold \(q\), and a fixed choice of TCP-net semantics. The question is whether
\[ \sum_{j:\,\alpha\text{ dominates }\beta\text{ under }N_j}\mu_j \ge q. \]
A solution gives the exact prevalence \(p\), and thus the yes/no answer for \(q\); it can also give a worsening-flip sequence for each type counted in \(p\). The per-type decision variable is \(z_j\in\{0,1\}\), indicating whether that type’s network entails the dominance. Mass means fraction of customers, and the objective is to compute the mass-weighted prevalence. As with other high-multiplicity inputs, rational masses correspond to finite cohorts after scaling by a common denominator.
My anchor is Theorem 1, proved in this paper. It says, first, that every edge \((\alpha,\beta)\) in the induced preference graph has a transition \(s\to s'\) in the constructed Kripke structure whose projections onto the preference variables are \(\alpha\) and \(\beta\). Second, every transition \(s\to s'\) that changes those projected variables corresponds to an edge between the two projected outcomes in the induced preference graph. The theorem therefore establishes that the encoding preserves the preference-changing steps used to test dominance. The paper uses that encoding for model checking and for extracting a dominance witness. This prevalence problem asks about the underlying dominance relation for each type; it does not treat the Kripke encoding as the object of interest.
The expected classification is hardness transfers (Class B). With \(\tau=1\) and \(q=1\), the prevalence query is exactly ordinary dominance testing for that one network. The paper states, citing Goldsmith et al. (2008), that dominance testing is PSPACE-complete in the general case outside special CP-net structures such as trees and polytrees. That complexity statement is cited background, not a numbered result proved in this paper. The paper’s numbered anchor is Theorem 1, not a complexity theorem. Its experiments demonstrate practical model-checking performance on tested instances; they do not establish a complexity bound. For the population version, the natural complexity parameters would include the number \(m\) of features, support size \(\tau\), and the total bit length \(L\) of the networks and masses.
This is a plausible population extension because users with the same complete TCP-net are indistinguishable for the query, and the result answers a concrete collective question: what fraction of customers has a ceteris-paribus worsening path from one bundle to another? The weakest point is that the paper studies a dominance query for one preference network, while prevalence adds a population layer and weighted aggregation. The connection is strongest at the computational kernel, not at the paper’s original application. It is also a less direct fit to a model whose usual voter types are rankings over candidates: here a type is an entire conditional preference model. I would present it as one credible mirror of the dominance result, not as evidence that continuization makes dominance tractable.
Further questions follow naturally: how does exact prevalence scale with \(m,\tau,L\); can shared structure across the \(N_j\) networks make batches of dominance queries cheaper; and which restricted network classes admit efficient prevalence computation? The mirror covers the paper’s dominance-testing result and its witness-producing use, not every preference-reasoning task mentioned in its discussion.
Theorem 1 is a correctness result for an encoding, not a complexity result for a population problem. For one fixed TCP-net \(N\), it relates edges in the induced preference graph to transitions in its Kripke structure. The paper’s PSPACE-completeness statement is cited background; the experiments report performance but do not establish a complexity bound. So the proponent has anchored the mirror to a proof device rather than to a numbered complexity result of the kind this programme is meant to continuize.
The proposed prevalence query is coherent: given a distribution over complete TCP-net types, ask for the mass of types under which \(\alpha\) dominates \(\beta\). But Theorem 1 applies to each type separately. Applying it across a support of size \(\tau\) means constructing and checking \(\tau\) instances, then adding their masses. The theorem itself has no population variable, and its statement does not change when those instances are given weights. Listing a witness for each counted type likewise gives a collection of individual witnesses, not a population-level witness or encoding result.
A stronger mirror might first combine the agents’ preferences into a collective relation and then ask about dominance in that relation. That choice needs a new aggregation rule: conditional strict orders and relative-importance statements do not come with a canonical averaging operation that yields a TCP-net. Majority or consensus semantics could define a legitimate new problem, but their choice and analysis would supply the central contribution; they do not follow from this paper’s theorem.
The customer-cohort scenario is plausible, and a distribution over complete preference models can be a sensible high-multiplicity instance regime. That is evidence for the prevalence question as a possible research question. It does not make the paper’s pointwise encoding theorem a continuous-population result. My negative case is strongest against this anchor, not against every possible application: I cannot honestly rule out that researchers would value population dominance prevalence in its own right. A reader could accept that question as a mirror of the paper’s underlying dominance task, even though Theorem 1 does not itself establish a population result.
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.