| paper | d4-conf-aaai-2014-0049 |
| 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: For every fixed nonconstant \(p\), the promised problem is \(\mathrm{NP}\)-complete, even for \(\tau=1\). For every fixed constant \(p\), it is polynomial-time solvable. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 5
Given a common binary attribute set \(V\), outcomes \(x,y\in\{0,1\}^{V}\), a finite support \(\{(C_i,\mu_i)\}_{i=1}^{\tau}\) of complete GCP-net types \(C_i=(V,R_i)\) with positive binary-rational masses summing to \(1\), and a rational threshold \(q\), with \(\operatorname{diam}(C_i)\le p(|V|)\) for a fixed polynomial \(p\), compute \(M_\mu(y,x)=\sum_{i=1}^{\tau}\mu_i\mathbf{1}[y\succ_{C_i}x]\), or decide whether \(M_\mu(y,x)\ge q\); incomparable pairs contribute zero.
Agents are grouped by complete GCP-net type \(C_i=(V,R_i)\), with mass \(\mu_i\), and the society is queried on fixed outcomes \(x,y\). Each type contributes \(d_i=\mathbf{1}[y\succ_{C_i}x]\); the aggregate is \(M=\sum_i\mu_i d_i\), compared with threshold \(q\).
Once each type's dominance bit is computed, the remaining task is only a weighted sum, with no interaction or intervention among agents; the proponent acknowledges an added aggregation layer but does not answer this thinness concern.
fatal: False
The mirror lifts Theorem 5's GCP-DOMINANCE[poly] result to a population distribution; it leaves the diameter-computation results and the other parameterized results unaddressed.
My lead mirror is GCP-Dominance Mass\(_\infty\). Fix a common set \(V\) of binary attributes and two policy bundles \(x,y\in\{0,1\}^{V}\). An instance gives a finite support of GCP-net types \((C_i,\mu_i)\), where \(C_i=(V,R_i)\), each \(\mu_i\) is a positive binary rational, and \(\sum_i\mu_i=1\). A type is the complete conditional-preference rule set shared by all agents in that group. The input also gives a rational threshold \(q\) and promises that each type’s GCP-net has diameter bounded by a polynomial in \(|V|\), as in the paper’s restricted problem.
The quantity to compute is \(M_\mu(y,x)=\sum_i\mu_i\,\mathbf{1}[y\succ_{C_i}x]\): the fraction of society whose type says that \(y\) dominates \(x\). The decision version asks whether \(M_\mu(y,x)\ge q\); for example, \(q=1/2\) asks whether at least half the population supports that strict preference. A “no” for an agent type includes both the case where \(y\) is not preferred and the case where the two outcomes are incomparable. The solution is the exact mass, or yes/no for the chosen threshold. The outcomes and their binary domains remain exactly as in the paper; it is the society of agents that becomes a distribution.
The regime I find credible is a large consultation on a policy or product described by binary attributes, where preference elicitation uses a fixed library of complete conditional-preference templates. Millions of respondents could be represented by hundreds or thousands of distinct templates, so \(N\gg\tau\). Respondents in one type share the same rules and are indistinguishable for this query. This is a specific template-based regime, not a claim that every population of GCP-net users has low support.
My anchor is Theorem 5, proved in this paper. It states that GCP-DOMINANCE[poly] is NP-complete: given a GCP-net, two outcomes \(o_1,o_2\), and the restriction that the net’s diameter is polynomially bounded in its number of variables, deciding whether \(o_2\succ o_1\) is NP-complete. The paper proves this result here, reducing from 3-SAT; its constructed instances have diameter bounded by \(|R|\le |V|\). This is the right anchor because dominance is the predicate whose population prevalence the mirror aggregates.
The connection to the paper is direct but modest. Each agent’s contribution to \(M_\mu\) is exactly the paper’s dominance question on that agent’s GCP-net and the common pair of outcomes. The paper’s conclusion also identifies voting applied to CP-nets as an interesting direction for future work, which gives this collective query a plausible home in the authors’ research. I would expect hardness to transfer: with one support type of mass \(1\) and \(q=1/2\), the mass query is precisely the Theorem 5 dominance instance. Thus the continuous population version is already NP-hard at \(\tau=1\). That is a Class B case, not a proposed route to tractability.
The scope is the paper’s dominance question under polynomially bounded diameter. This does not mirror its diameter-computation results or the parameterized results as a whole. It raises useful follow-up questions: can one compute or approximate the pairwise preference margin for a low-support population when some types are easy to evaluate, and what happens under restrictions on the GCP-net types or when the queried policy bundle is chosen to maximize support?
The weakest point is that aggregation is an added social-choice layer around a single-agent problem. A referee could reasonably say that the paper studies whether one GCP-net entails a dominance relation, whereas this mirror studies the population share for which that relation holds. The paper’s stated interest in voting on CP-nets supports the bridge, but does not make the two problems identical. Also, exact repeated GCP-net templates are a narrower regime than a general electorate. I think the mirror is still worth asking in that regime because it preserves the paper’s computational core while making the population itself the continuous object.
The only anchor is Theorem 5, and it is a real computational result: GCP-DOMINANCE with polynomially bounded diameter is NP-complete. The proposed query uses that exact predicate for each type, so I cannot dismiss it as lacking an anchor or as continuizing the wrong thing.
The strongest negative point is that the population layer is passive. For fixed outcomes \(x,y\), write \(d_i=1\) if \(y\succ_{C_i}x\), and \(d_i=0\) otherwise. Then the proposed statistic is just
\[
M_\mu(y,x)=\sum_i \mu_i d_i.
\]
After evaluating the dominance predicate for each supported type, the rest is a weighted tally. The masses do not interact, and the query asks for neither a collective choice nor an intervention in the society. That makes it a defensible population statistic, but a thin continuous-computational problem: its continuous part adds no structure for the optimization tools ChoCo is trying to bring into reach. This is not an objection that hardness transfers or that continuity fails to help; it is a question about whether this particular aggregation is substantial enough to merit the programme’s attention.
The proposed consultation scenario is plausible: respondents could choose among a small library of preference templates, and a large population could share those templates. But it yields the prevalence of one pairwise judgment. A stronger social-choice version would aggregate dominance over many policy bundles and ask for a majority winner or a majority margin. That is more consequential, but its central modeling choices—how to handle incomparable outcomes, cycles, and the selection of a winner—are new ingredients. The paper itself names voting on CP-nets as future work, which supports that direction rather than ruling it out. I can argue that it has moved beyond Theorem 5’s single-pair task; I cannot honestly argue that it is therefore unworthy.
A robustness or manipulation version could ask how much mass must move before the majority relation changes. That would put mass transfer at the center, but it needs a model of which preference-network changes are allowed and what they cost. The paper supplies no natural transition cost between GCP-nets. A chosen edit cost could produce a proper optimization question, yet the choice would do much of the modeling work.
So the negative case is weak at its most important point. Theorem 5 has a direct mirror, and the fixed-template consultation gives it a sensible high-multiplicity setting. I can make a case that the stated mirror is narrow and analytically shallow, but I cannot defeat the stronger population-voting version with confidence. A universal claim that no worthwhile continuous mirror exists would overstate what this paper supports.
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.