| paper | d4-conf-ijcai-2009-0087 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | unclear |
The paper makes computational claims, including an NP-completeness lemma and polynomial-time SSVM claims, but none appears as a numbered theorem, lemma, corollary, or proposition as the gate requires. Population SCP is a plausible statistic, but without a specified preference encoding it cannot provide a computational mirror anchored in a qualifying result.
fails bit a — no named computational result to mirror
The proposed mirror covers only the SCP subset-membership subproblem; it leaves SVMOS training, inference, and experiments untouched.
The paper has no numbered Theorem, Lemma, Corollary, or Proposition asserting a complexity result, so I can’t give a fully compliant numbered anchor without inventing one. Its strongest candidate is the unnumbered “Lemma. SCP is NP-complete.” The paper defines SCP as: given a ground set \(x\), a preference \(p\), and an item \(I\in x\), decide whether \(I\in p(x)\). It claims NP-completeness by reduction from binary knapsack, but omits the reduction details. This is asserted in the paper, not cited from elsewhere. I’ll use it as a provisional lead anchor.
A plausible continuous mirror is an item recommendation service for a large, stable audience. A type is a complete user preference \(p_t\) over subsets of the catalog; users of that type have the same relevant preferences and receive the same optimal subset. Let the society be a rational distribution \(\mu\) over \(\tau\) such types, with \(\sum_t\mu_t=1\), and let \(x\) be a shared catalog with target item \(I\). For each type, the choice remains the paper’s optimal subset \(y_t=p_t(x)\). The continuous decision problem, Population SCP, takes \(x,I\), the encoded preferences \(p_t\), their masses \(\mu_t\), and a rational threshold \(q\); it asks whether
\[
\sum_{t:I\in p_t(x)}\mu_t\ge q.
\]
Equivalently, it can return the exact mass of users whose optimal subset contains \(I\). Each person still gets an integral subset; the continuous quantity is the share of the audience.
The regime would be a platform serving millions of users in a market segment, grouped into relatively few behavioral types—say, hundreds of distinct set preferences over a large catalog. That is a plausible high-multiplicity setting if a type captures everything relevant to the choice. It also preserves the paper’s central feature of the underlying SCP: preferences over sets can express interactions among items, rather than independent item rankings.
I expect this mirror to be hard by direct hardness transfer. With one type of mass \(1\) and \(q=1\), Population SCP is exactly the paper’s SCP, so its NP-hardness survives even when \(\tau=1\). This is a weak test of whether continuity helps: the result’s combinatorics live in the preference and catalog, not in population multiplicity. The natural next questions are whether restricted preference families admit efficient pricing or optimization, and whether any guarantees depend on \(\tau\), catalog size, or the preference encoding length.
The scope is deliberately narrow: it mirrors the paper’s optimal-subset computation subproblem, not its central task of learning a predictor from labeled ground sets. The paper’s polynomial-time SSVM training and exact inference claims are in prose and algorithm discussion, not in a numbered named result, so they cannot serve as anchors under your rule.
The soft spot is whether the authors would recognize Population SCP as their problem’s continuous analogue. It is a natural population deployment question built directly from their SCP, but the paper studies learning for an implicit preference, not aggregating choices across a user population. Also, the excerpt does not spell out the encoding used in the knapsack reduction, so a prover would need that source representation specified before implementing the mirror. The strongest honest case is therefore for this one underlying subproblem, with a clear numbering defect in the paper and a real gap between the mirror and the paper’s main learning contribution.
The proponent has no compliant anchor. The paper’s only complexity claim is the unnumbered “Lemma. SCP is NP-complete,” and its proof is omitted. More seriously, the paper gives no binary encoding for the preference \(p\). Without one, it is unclear what the SCP input is or how NP membership is verified. A continuous version cannot repair that gap while still claiming to mirror a complexity result established by this paper.
Population SCP inherits the missing encoding. Once each \(p_t\) is specified, its output is just the mass-weighted sum of the types whose chosen subset contains \(I\). That is a coherent population statistic, but it is detached from the paper’s main contribution: learning a predictor from labeled ground sets. The mass does no work until after each type’s choice has been determined. Choosing a succinct preference language could make the resulting problem interesting, but its complexity would then be about that added language, not a named result here.
The better repair is to give users complete types \((x,y)\) and train one shared predictor to minimize expected set loss under a rational distribution over those types. That keeps the population in the objective and stays close to SVMOS. The strongest objection is that this turns the population into a distribution over training examples: the paper already frames learning as empirical risk minimization and supplies a structural SVM method. It is therefore a weak candidate for a distinct continuous-social-choice programme question. But it is close enough to the paper’s learning problem that I cannot honestly rule out the authors recognizing it as a worthwhile mirror.
So the negative case defeats the proposed anchor as a paper result, but it does not establish the universal claim. The paper’s missing formal complexity statement and preference encoding make the case against unusually strong; the population-risk learning variant is where that case remains vulnerable.
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.