| paper | d4-conf-aaai-2026-0908 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\)-complete, and hence \(\mathrm{NP}\)-hard. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 1
Given \(m\) alternatives and a distribution \(\mu\) with positive binary-rational masses summing to \(1\) over supported ordered-pair comparison types \(r=(a\succ b)\), decide whether there are shared attribute sets \(H(a)\subseteq[3]\) for each alternative and care sets \(Q(r)\subseteq[3]\) for each supported type such that \(|H(a)\cap Q(r)|\ge |H(b)\cap Q(r)|+1\) for every \(r=(a\succ b)\) in the support.
A society is a distribution \(\mu\) over length-two comparison types. The alternatives share three Boolean attributes, each supported type receives a care set, and the question is whether every positive-mass type is explained; the mass values do not enter feasibility beyond determining support.
It covers Theorem 1’s exact feasibility and its \(k=3\), length-two NP-hardness; it leaves the variants with cares or attributes fixed and the parameterized algorithms unmirrored.
I’d make the lead mirror the Distributional BAM problem. Its anchor is Theorem 1, proved in this paper by a reduction from 3-Coloring (whose NP-completeness is cited): BAM is NP-complete, and remains NP-hard when \(k=3\) and every preference order has length two. The theorem’s hardness construction uses alternatives for graph vertices plus dummy alternatives that force the vertex alternatives to represent distinct single attributes; an edge comparison then rules out assigning its endpoints the same attribute.
In a plausible high-multiplicity setting, a large platform repeatedly asks users to compare pairs from a fixed catalog. A voter type is the user’s observed strict comparison, such as \(a\succ b\). The society is a distribution \(\mu\) over the \(\tau\) comparisons that occur, with \(\mu_r\) the fraction of users giving comparison \(r\). With \(m\) alternatives there are at most \(m(m-1)\) such types, so a population of millions can have far fewer distinct types.
Here is the continuous problem I would hand to a prover: 3-Distributional-BAM. An instance consists of a set \(C\) of \(m\) alternatives and a list of \(\tau\) length-two comparison types \(r\), each with a positive binary-rational mass \(\mu_r\), where \(\sum_r\mu_r=1\). Decide whether there are sets \(H(a)\subseteq[3]\) for every alternative \(a\), and \(Q(r)\subseteq[3]\) for every supported type \(r\), such that whenever type \(r\) reports \(a\succ b\),
\[
|H(a)\cap Q(r)|\ \ge\ |H(b)\cap Q(r)|+1.
\]
The \(H(a)\) are the alternatives’ shared Boolean attributes; \(Q(r)\) is the attribute set assigned to users of type \(r\). A solution is this assignment, and the objective is feasibility: does a 3-attribute model explain every positive-mass type? This states the question about the underlying BAM, rather than about an encoding of it.
This grouping preserves the paper’s problem. In ordinary BAM, two voters with the same ranking have identical constraints, and their care sets are independent choices. Any care set that explains that ranking can be assigned to every voter with that ranking. Thus merging duplicate rankings into one type loses no feasible models. Conversely, a rational distribution can be turned into a high-multiplicity profile by choosing a common denominator \(D\) and giving type \(r\) exactly \(D\mu_r\) voters. With counts encoded in binary, this dictionary is compact even when the corresponding explicit voter list is large.
The result should be hardness transfers, Class B. The paper’s reduction already uses length-two orders, so its instances give supported comparison types for this problem; assign each distinct type positive rational mass. The preference constraints depend on which types occur, not their weights, so merging duplicates and normalizing the masses preserves the answer. The hardness combinatorics live in the alternatives and their comparison pattern, not in the number of repeated voters. Continuous input therefore does not dissolve this anchor’s hardness. The natural complexity measures are \(m\), \(\tau\), and mass bit length \(L\); for this exact-fit question, the numerical mass values do not affect feasibility once the support is fixed.
The platform scenario also fits the paper’s explanatory aim: discover whether a small common feature model can explain a population’s revealed preferences. Since individual names, prices, and budgets do not enter the anchored BAM problem, a type need only record the preference information the problem uses. Users with the same comparison may have different real motivations, but that does not make the mirror a different feasibility question: the original model already asks whether a suitable care assignment exists for each voter, and identical comparisons can share one such assignment.
I would scope the claim to Theorem 1’s exact BAM feasibility result, especially its \(k=3\), length-two hardness restriction. I am not claiming a mirror of the paper’s variants with cares or attributes given, or of its parameterized algorithms.
The weak point is that this is a deliberately exact, support-based mirror. Any positive-mass comparison must be explained, even if its mass is tiny, while the masses themselves do not influence the answer. So this formulation does not create a new weighted optimization problem or show that continuous-optimization machinery helps; it gives an exact high-multiplicity formulation in which the paper’s hardness survives. That is still a useful boundary result. It also suggests follow-up questions: does the problem become tractable when parameterized by \(\tau\), and what happens in a weighted approximate-fit version that may leave an \(\epsilon\) fraction of the population unexplained?
The strongest objection is that the proposed exact problem gives the masses no computational role. Since the condition requires every positive-mass preference type to be explained, only the support matters: a type of mass \(10^{-9}\) imposes exactly the same constraint as one of mass \(1/2\). In the discrete BAM problem, duplicate rankings can likewise be removed without changing feasibility, because each voter’s care set is chosen independently. So this distributional formulation is the support version of BAM with rational weights attached; changing the population proportions never changes the answer.
That also makes the exact condition unstable as a population limit. Adding an arbitrarily small positive mass of a previously absent type can change a yes-instance to a no-instance. A continuous model could instead minimize the unexplained population mass,
\[
\min \sum_r \mu_r z_r,
\]
where \(z_r=1\) permits type \(r\) to go unexplained. This is a more meaningful distributional question: it asks what fraction of a preference population a shared attribute model can explain. But it requires choosing an approximation objective the paper does not analyze. The paper’s formal result concerns exact explanation, and its hardness theorem alone does not establish that a weighted fitting problem is its mirror.
That is a real limitation of the anchor, but it does not defeat it. The support-only question is still a well-posed high-multiplicity version: a platform or survey could collect repeated rankings over a fixed catalog, and the shared attribute model would be asked to explain every ranking type present. The result transfers to that setting. The programme explicitly treats high-multiplicity formulations as evidence in favor of a mirror, and it accepts hardness that survives continuization as a useful boundary result.
I can argue that the exact mirror adds little population-sensitive structure, and that the more compelling mass-weighted version needs a new objective. I cannot honestly rule out either formulation as a worthwhile question an author would recognize. The negative case against this anchor is weak; Theorem 1 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.