| paper | d4-conf-atal-2018-0330 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\text{-hard}\) under polynomial-time one-query reductions, even for \(\tau=2\), equal masses, and dependency graphs of depth one and maximum indegree two; exact rationals are encoded by binary numerators and denominators. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Proposition 3.2
statement extracted from the paper’s text layer
Given a finite support of complete acyclic CP-net types \(N_t\) over a shared feature set \(F\), with binary-rational masses \(\mu_t\) summing to \(1\), compute the exact rational value of \(D(\mu)=\sum_{t,u}\mu_t\mu_u\,\mathrm{KTD}(N_t,N_u)\), using the paper’s normalized KTD with \(p=1/2\).
A society is a distribution \(\mu\) over complete CP-net types on common binary features; its disagreement is the mass-weighted mean pairwise KTD, and the task is to compute that value exactly.
The exact within-group mean is a new aggregate statistic; the paper’s group-disagreement motivation supports it, but does not establish that the authors would adopt this particular aggregation.
fatal: False
The mirror covers exact computation of expected pairwise KTD over CP-net types, anchored by Proposition 3.2; it leaves the O-CPD and I-CPD approximations, their error analysis, and the distance-rationalizability theorems aside.
My strongest case is for Continuous CP-net Disagreement. Let \(F\) be a shared set of \(m\) binary features, with outcomes \(U=\{0,1\}^m\). Each type \(t\) is a complete acyclic CP-net \(N_t\) over \(F\), including its dependency graph and conditional preference tables. A society is a finite support \(T\) of these types with positive binary-rational masses \(\mu_t\) summing to \(1\). Mass means the fraction of people with that exact CP-net. Fix the paper’s Kendall distance penalty at \(p=1/2\), and define the society’s expected pairwise disagreement by
\[
D(\mu)=\sum_{t,u\in T}\mu_t\mu_u\,\mathrm{KTD}(N_t,N_u).
\]
The problem is: given the support and masses, output the exact rational value of \(D(\mu)\); a solution is that value in binary. There is no intervention variable: the computed quantity is the society’s mean preference disagreement.
A plausible regime is a large group making choices over the same binary product or policy attributes, whose conditional preferences are elicited using a shared catalog of CP-net templates. For example, many thousands of users might fall into a few dozen such types, so the population size greatly exceeds \(\tau=|T|\). The CP-net is the complete description relevant to this measurement; other individual differences are outside the model. This keeps the outcomes discrete and makes the population itself the continuous object.
The anchor is Proposition 3.2. It states that, given two CP-nets \(A\) and \(B\) inducing partial orders over the same outcomes, deciding whether \(\mathrm{KTD}(A,B)=0\) cannot be done in polynomial time unless \(P=NP\). The paper gives the reduction, relying on the cited NP-completeness of CP-net equivalence from Santhanam et al. [36]. Zero distance here means the two CP-nets induce the same ordering.
This mirror preserves that difficulty even with only two population types. Set \(T=\{A,B\}\) and \(\mu_A=\mu_B=1/2\). Since each net has distance zero from itself and KTD is symmetric, \(D(\mu)=\tfrac12\mathrm{KTD}(A,B)\). Thus exact computation of the population statistic decides the Proposition 3.2 question. I expect hardness to transfer (Class B): the reduction’s combinatorics are in the CP-nets’ feature structure, and remain when the population has fixed support size \(\tau=2\). A decision version—whether \(D(\mu)=0\)—has the same lower bound.
The scope is deliberately narrow: this mirrors Proposition 3.2’s hardness for the exact KTD baseline. It does not claim to mirror the paper’s tractable O-CPD and I-CPD approximations or its distance-rationalizability theorems.
The weak point is that the paper defines distance between CP-nets and studies profiles, but does not itself define this population-wide mean. The mean is a natural extension of its stated aim to measure disagreement within groups, yet authors might regard it as a new aggregate statistic rather than their original problem. Also, the hardness survives with two types, so this is a useful boundary case for continuization rather than an example where continuous mass makes the problem easier.
The strongest objection is that the proposed statistic is a new population summary, not the paper’s stated pairwise distance problem. Proposition 3.2 compares two CP-nets. For a society with two types of mass \(1/2\), the proposed mean disagreement is exactly \(D(\mu)=\tfrac12\mathrm{KTD}(A,B)\); with more types, it is a weighted sum of pairwise distances. So the population supplies weights, while the hard computation remains the original two-net question. That makes this a peripheral extension rather than a case where population continuization changes the computational model.
But that objection does not defeat the mirror. The paper motivates measuring disagreement within groups, and a with-replacement mean pairwise distance is a natural way to do so. A type can be a complete CP-net, and rational masses can represent how many people share it. The fact that the hardness already appears at support size two limits what the mirror demonstrates about population size, but the programme explicitly allows hardness to transfer and does not require the population dimension itself to cause the difficulty.
A stronger mirror could put rational masses over the paper’s CP-net types, apply sequential plurality by weighted votes at each feature, and ask how much mass must change type to alter the winner, using the paper’s distance notions as costs. That adds modeling choices, especially the intervention costs, but they are recognizable extensions of the paper’s distance and voting questions. I see no fundamental obstacle in identity dependence, vanishing mass, or the need to restate ties and fractional masses.
So the best negative case is that the proposed mean disagreement is not central to the paper and does not showcase a population-specific algorithmic phenomenon. Under the stated standard, that is not enough: Proposition 3.2 gives it a direct computational anchor, and the aggregate is plausible. I cannot make a persuasive case that no worthwhile continuous mirror exists.
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.