| paper | d4-conf-ijcai-2016-0015 |
| 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}\)-complete, even with \(\tau=1\), evaluation values in \(\{0,1\}\), and exactly one strict statement. · discrete side: other · adjudication: proved
full proof & adversarial review →
Proposition 4.3
statement extracted from the paper’s text layer
Given a finite alternative set \(\mathcal A\), integer-valued evaluations \(\mathcal C\), addition, and a finitely supported rational distribution \(\mu\) over contributor types \(P\), where each \(P\) is a packet of strict and non-strict comparisons, decide whether there is a hierarchy \(H=(C_1,\ldots,C_k)\) with \(|C_i|\le 2\) that satisfies every comparison in every packet with \(\mu_P>0\).
Each type is a complete feedback packet \(P\), and \(\mu_P\) is its share of the population. The decision variable is an ordered partition \(H\) of evaluation functions into levels of size at most two; feasibility requires every positive-mass contributor’s comparisons to hold. The mass values do not affect the answer beyond determining the support.
The group-wide unanimity policy differs from the paper’s individual-user setting; the case offers a plausible shared-policy use, but does not establish that the authors would accept it.
fatal: False
Mirrors Proposition 4.3’s safe fixation of a maximal singleton prefix for \(C(2)\)-PCP and the consistency decision on the support union. It leaves the MILP formulation, runtime experiments, comparison of recursive variants, and preference-deduction results aside.
There is one limitation on the anchor: the paper has numbered computational results, but no numbered theorem, lemma, corollary, or proposition that classifies a problem as NP-hard, in P, or otherwise. The closest in-paper anchor is Proposition 4.3, proved here. It says: if \(H\) is a \(C(1)\) model satisfying the non-strict versions of \(\Gamma\), with a maximal number of singleton levels, and \(\Gamma\) is \(C(t)\)-consistent, then some \(C(t)\) model satisfying all of \(\Gamma\) has \(H\) as its initial sequence. The paper uses this property to avoid backtracking over that initial sequence. The NP-completeness hook appears in the discussion after Proposition 2.5: the paper attributes to Wilson et al. (2015) that, for each fixed \(t\ge2\), \(C(t)\)-PDP is coNP-complete, and infers that \(C(t)\)-PCP is NP-complete. That is a cited, unnumbered complexity claim here, rather than a qualifying numbered anchor.
A concrete mirror of Proposition 4.3 is Population \(C(2)\)-PCP. Consider an organization that collects pairwise judgments about a shared catalogue and wants one explainable hierarchy of evaluation criteria to respect every submitted judgment. The many agents are contributors to that shared policy. Their type is their complete feedback packet: the set of strict and non-strict comparisons they submit. Contributors with identical packets are indistinguishable for this problem. In a large, stable population, the number \(N\) of contributors could be much larger than the number \(\tau\) of distinct packets.
An instance consists of a finite alternative set \(\mathcal A\), integer-valued evaluation functions \(\mathcal C\) on \(\mathcal A\), addition as the combining operation, and a distribution \(\mu\) over feedback-packet types. Each positive mass \(\mu_P\) is a binary rational, and the masses sum to one. The question is whether there is a \(C(2)\) HCLP model \(H=(C_1,\ldots,C_k)\), with each level containing at most two evaluations, that satisfies every comparison in every packet \(P\) with \(\mu_P>0\). A “yes” solution is that ordered partition \(H\); the mass \(\mu_P\) means the fraction of the population with packet \(P\). This is a feasibility question, matching the paper’s PCP.
For this mirror, Proposition 4.3 says that a maximal singleton-level sequence satisfying the non-strict support constraints can be fixed as the beginning of a witness hierarchy whenever a witness exists. The remainder of the hierarchy can then be sought without reconsidering that prefix. It gives useful search structure; it does not itself establish polynomial-time solvability.
I expect this mirror to be Class B: hardness transfers. Given a discrete PCP instance \(\Gamma\), make one packet type \(\{\phi\}\) for each \(\phi\in\Gamma\), each with mass \(1/|\Gamma|\). The population instance is consistent exactly when \(\Gamma\) is \(C(2)\)-consistent. Thus the discrete hardness embeds directly. In fact, under the unanimity question above, the answer depends on the support of \(\mu\); the particular positive mass values do not affect it. This is a faithful population interpretation of PCP, but it does not make the problem easier.
The strongest part of the case is that the decision problem remains precisely the paper’s problem on the union of the population’s feedback packets. Authors could recognize it as PCP applied to a shared institutional preference model, even though their motivating examples focus on inferring one user’s preferences. The weakest point is that requiring one hierarchy to satisfy every positive-mass contributor is a strong group-policy assumption, and the multiplicities themselves have no effect once packet support is known. This mirror continues the population, while offering little of the continuous-optimization advantage that motivates the broader programme.
It raises two useful follow-up questions: whether \(C(t)\)-PCP admits parameterized algorithms in the support size \(\tau\), and whether the authors would regard a version that accepts a hierarchy satisfying at least a specified fraction of the population’s packets as a preference-consistency problem. The latter changes unanimity into a weighted fit objective, so it would need its own case for author acceptance.
The proposed anchor is weak before one even reaches the mirror: Proposition 4.3 is an algorithmic structural proposition, not a numbered complexity result. The NP-completeness statement is attributed to earlier work in the discussion after Proposition 2.5. Still, Proposition 4.3 is the strongest result the proposed case can point to, so it is worth testing directly.
The shared-catalogue scenario makes contributors look like a population, but the decision being asked remains the consistency of a set of statements. If contributor types are feedback packets \(P\), the relevant input is \(\Gamma_\mu=\bigcup_{P:\mu_P>0}P\). A hierarchy is acceptable exactly when it satisfies every statement in \(\Gamma_\mu\). Thus Proposition 4.3 applies to that union as written: its singleton prefix is determined by the combined constraints, not by contributor counts or proportions. The distribution supplies no population quantity that the proposition can use. This is not just a prediction that the continuous answer will be unexciting; it is a mismatch between the result’s object and the proposed population model. The result concerns how to order evaluation functions under a constraint set, not how to reason about a society.
The earlier NP-completeness claim has the same problem as a continuous anchor. Encoding each statement as a packet type makes a population story for the input, but does not give the claim a population-dependent question to classify. Repetition of a packet adds no new constraint, while even a very small positive mass packet contributes all its statements. A weighted version could make prevalence matter, but choosing a fraction of satisfied contributors, or a score for partially satisfied packets, adds an aggregation objective and a policy threshold that the paper’s PCP does not define.
That weighted extension is the strongest alternative mirror I can see, and it is also where this negative case is vulnerable. A group trying to infer a common preference model from many users’ reports is plausible and close to the authors’ subject. But it asks how to reconcile conflicting users, whereas the paper asks whether one user’s statements admit a common hierarchical explanation. Making that shift may be a worthwhile research question; the paper gives little basis for treating it as a continuous version of its consistency problem. I would therefore reject the proposed Proposition 4.3 mirror, while keeping the broader claim—no worthwhile population mirror in any scenario—less certain.
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.