| paper | d4-conf-ecai-2008-0037 |
| 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: \(\mathrm{NP}\text{-hard}\), even for \(\tau=1\), \(\mu_1=1\), and indegree at most three; polynomial-time solvability would imply \(\mathrm{P}=\mathrm{NP}\). · discrete side: other · adjudication: proved
full proof & adversarial review →
Proposition 3
statement extracted from the paper’s text layer
Given τ complete CP-net types \(N_t\) with rational masses \(\mu_t\) summing to \(1\), and alternatives \(x,y\), compute \(M(x,y)=\sum_{t:\,x\succ_{N_t}y}\mu_t\) and \(M(y,x)\), and determine whether either exceeds \(1/2\).
A society is an explicitly listed distribution over complete CP-net types, each containing the user’s variables, conditional preference tables, and symbolic priority constraints. For each pair of alternatives, use the paper’s symbolic comparison to identify which types entail each direction, then sum their masses and apply strict majority.
The paper handles one user’s CP-net and does not define majority aggregation; the proponent acknowledges this, but the aggregation rule remains an added population-level question.
fatal: False
The mirror uses Proposition 3’s recovery of pairwise CP-net entailment for each type; it leaves the broader symbolic-priority framework and the paper’s other preference-ordering results aside.
My lead is a continuous pairwise-ranking problem for a population of people choosing among the same configurations. A type is a complete CP-net: the person’s attributes, conditional preference tables, and the symbolic priority constraints used to compare alternatives. The instance is a list of \(\tau\) such types with rational masses \(\mu_t\) summing to \(1\), plus two alternatives \(x,y\). For each type, count \(x\) as preferred to \(y\) only if that type’s CP-net entails \(x\succ y\), in the paper’s sense that the preference holds in every ranking consistent with the net. Define
\[
M(x,y)=\sum_{t:\,x\succ_{N_t}y}\mu_t.
\]
The task is to return the exact values \(M(x,y)\) and \(M(y,x)\), and say whether either exceeds \(1/2\). If neither does, the population has no strict majority comparison for that pair. The decision is the pairwise social ranking; as in the paper’s ranking problem, there is no separate optimization objective.
A plausible regime is a large platform whose users choose from configurations of the same product, using a limited catalogue of conditional-preference templates. Millions of users might share a few dozen or hundred complete CP-net types, so \(n\) is large relative to \(\tau\). Each person’s type includes their full conditional preferences and priority structure; the masses represent fractions of users. The alternatives remain finite. Only the population is continuous.
The anchor is Proposition 3, proved in this paper. In full: for a CP-net \(N\), form the associated symbolic formula base \(\Sigma\) and impose the paper’s priority constraints between levels; then, for any two alternatives \(\omega,\omega'\), the ordered-Pareto comparison \(v\succ_{OP}v'\) of their satisfaction vectors holds if and only if \(\omega\succ_N\omega'\). Thus the paper gives a way to recover the CP-net’s entailed pairwise preference relation by comparing symbolic violation vectors. Applying that comparison type by type and summing the corresponding masses gives the continuous query above. Proposition 3 is an algorithmic relation result, not a numbered P-versus-NP classification. The tractability claim comes from the paper’s unnumbered discussion of existing possibilistic-logic inference results, cited as [3], rather than from Proposition 3 itself.
I expect this mirror to be tractable for an explicitly listed support: evaluate the two alternatives against each type’s symbolic preference base, determine whether that type entails either comparison, and sum the binary rational masses. The expected running time is polynomial in the total explicit description of the \(\tau\) types and the mass bit lengths. This is a continuous pairwise query, not a claim that listing the ranking of all exponentially many alternatives takes polynomial time.
The authors could plausibly recognize this as a population version of their preference-ranking query: the individual comparison is exactly the one Proposition 3 recovers, and the high-multiplicity setting is credible when users reuse a small catalogue of complete preference types. The paper does not study collective aggregation, however. Strict majority is an added social choice rule, not a result of theirs. That is the weakest point, along with the fact that the paper gives no named complexity-classification theorem and no hardness anchor. I would not claim that this mirror demonstrates discrete hardness dissolving; it is a narrower, plausible Class A extension of the paper’s computable comparison.
The mirror covers the paper’s recovery of CP-net pairwise preferences, not its broader symbolic-priority framework or its database-querying suggestion. It also generates further questions: whether a target alternative beats every other alternative by strict majority; whether the resulting majority relation cycles; and how the complexity changes when types are generated succinctly instead of listed explicitly.
The strongest objection is that Proposition 3 is not a computational-complexity result. It proves an equivalence: the symbolic-vector relation recovers the pairwise relation entailed by a CP-net. The paper’s tractability claim comes from an existing possibilistic-logic inference procedure, not from a theorem classifying a computational problem. The paper studies one preference holder’s ordering of alternatives; it gives no result about a society or an aggregation rule.
The proposed \(M(x,y)\) query adds both. Proposition 3 can supply each type’s individual comparison, but the strict-majority threshold is a new social choice rule. For an explicitly listed support, the computation is to run the individual comparison for each type and sum its mass. That may be useful as a query, but the population creates no new optimization or complexity question here. Asking for majority winners, cycles, or robustness would make a richer problem; those questions would come from the added aggregation rule, not from a result in this paper.
A broader version does not fix the anchoring problem. Removing the majority threshold and asking for the mass of types that entail \(x\succ y\) leaves the same repeated-query-and-sum task. Asking how to change the population to make \(x\) win would require an intervention model and costs absent from the paper. Its database-query suggestion has a similar gap: aggregating violation information across people requires a new rule for comparing their symbolic priorities.
There is already a substantial finite-agent literature on Pareto and majority aggregation over CP-nets, including complexity analyses of majority voting. That literature does not constitute a continuous collision, and I would treat it as evidence that populations of CP-net users are a sensible regime. It does, however, underline that the proposed collective question belongs to an aggregation programme of its own, rather than mirroring a computational result here. [Lukasiewicz and Malizia, “Complexity Results for Preference Aggregation over (m)CP-nets: Pareto and Majority Voting”](https://arxiv.org/abs/1806.10018)
I cannot make a convincing case that no plausible high-multiplicity scenario exists: a large platform with users drawn from a small catalogue of complete CP-net types is credible. Nor is fractional mass a problem. So the negative case is limited: this is a weak *mirror of this paper*, because the paper supplies an individual comparison method rather than a computational social-choice result. If the programme accepts a new population-level aggregation problem merely inspired by an individual-level result, the proponent’s case survives.
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.