| paper | d4-conf-aaai-2026-3636 |
| 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→P discrete result → its continuous mirror
Answer: The problem is in \(\mathrm{P}\), with running time \(O(L)\). The answer is YES exactly when \(m=1\) and \(K\ge 0\); for every \(m\ge 2\), no componentwise inclusion-minimal sufficient support exists. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 3
Given a finite candidate set \(C\), a finite set \(T\) of complete pairwise-judgment types, a rational distribution \(\nu\) over \(T\), a target \(w\) in the weighted uncovered set of the induced society, and a rational threshold \(K\), let \(p(a,b)=\sum_{t\in T}\nu_t\mathbf{1}[t\text{ ranks }a\text{ above }b]\). Decide whether there is a componentwise inclusion-minimal matrix \(x\) satisfying \(0\leq x(a,b)\leq p(a,b)\) and \(x(a,b)+x(b,a)\leq1\), such that \(w\) is in the weighted uncovered set of every completion \(q\) with \(q(a,b)\geq x(a,b)\) and \(q(a,b)+q(b,a)=1\), and \(\sum_{a\ne b}x(a,b)\leq K\).
The society is a rational distribution \(\nu\) over complete pairwise-judgment types, with support size \(\tau\); types may be intransitive, as in the paper’s tournament model. The induced pairwise masses \(p(a,b)\) describe the consultation. A partial evidence matrix \(x\) records the mass of comparisons used, and its size is \(\sum_{a\ne b}x(a,b)\); it is an explanation when every completion consistent with that evidence keeps \(w\) in the weighted uncovered set.
The opponent’s three-candidate example shows that a fractional society can have certificates but no inclusion-minimal certificate at all; the proponent noted possible non-attainment of a minimum size but did not address this stronger failure of minimality.
fatal: False
The mirror covers only the weighted-uncovered-set minimal-support decision result in Theorem 3. It leaves the results for the other five tournament solutions, the size bounds, and the algorithms for selecting explanations unmirrored.
The strongest mirror is Fractional WUC Minimal Support. Picture a large online consultation on a fixed set of proposals, where many people answer pairwise questions and the same complete patterns of answers recur. A type is one complete pattern of pairwise judgments; its mass is the fraction of respondents with that pattern. The judgments need not be transitive, which matches the paper’s tournament model. The regime of interest has many respondents but relatively few distinct types.
My anchor is Theorem 3, the weighted uncovered set hardness result in §4.2, proved in this paper by reduction from Set Cover. It says: given \(n\geq 2\), a complete \(n\)-weighted tournament \(G=(C,\mu)\), a candidate \(w\in\wuc(G)\), and an integer \(k\), deciding whether there is a minimal support for \(w\) of size at most \(k\) is NP-complete. The reduction uses \(n=2\) and represents Set Cover elements and sets by candidates alongside the designated winner. The supplied text omits the numeral in this restatable theorem heading; I identify it as Theorem 3 from the sequence before the explicitly numbered Theorem 5.
Here is the continuous decision problem. The input is a finite candidate set \(C\), a rational distribution \(\nu\) over complete pairwise-judgment types, a target \(w\) that belongs to the weighted uncovered set of the induced society, and a rational threshold \(K\). Let \(p(a,b)\) be the mass of types reporting \(a\) above \(b\). A proposed explanation is a partial comparison-mass matrix \(x\), with \(0\leq x(a,b)\leq p(a,b)\) and \(x(a,b)+x(b,a)\leq 1\). It certifies \(w\) if \(w\) is in the weighted uncovered set in every completion \(q\) satisfying \(q(a,b)\geq x(a,b)\) and \(q(a,b)+q(b,a)=1\). It is a minimal support if no strictly smaller matrix \(y\leq x\) still certifies \(w\). Its size is \(\sum_{a\ne b}x(a,b)\), the total mass of pairwise comparisons used. Fractional WUC Minimal Support asks whether such a minimal certificate of size at most \(K\) exists; a solution is the matrix \(x\).
This preserves the paper’s underlying question: what least pairwise evidence guarantees that \(w\) remains a weighted uncovered-set winner under every completion? Candidates and the rule stay discrete; the population and the evidence mass become continuous. The result I expect is hardness transfer (Class B): Theorem 3’s reduction has its combinatorics in the candidate set, even with only two voters, which suggests population multiplicity is not the source of the hardness. A transfer proof must still handle fractional certificates; simply dividing the theorem’s integer weights by \(n\) does not establish it. In particular, the reduction’s witness choices among candidate pairs must remain hard when comparison mass can be fractional.
The scope here is only Theorem 3’s weighted uncovered set decision problem. It does not claim a mirror for all six rules in the paper. It also generates two useful follow-up questions: whether the discrete and continuous decision variants admit a precise reduction in both directions, and whether a minimum-mass certificate is always attained. The latter deserves care because the necessary-winner condition can depend on strict inequalities; the threshold decision form above avoids assuming an attained minimum.
The weakest point is the agent-level interpretation. The paper works directly with weighted tournaments and indivisible voter-comparison counts; it does not establish that its results extend to fractional evidence from a typed population. The mirror is most plausible for repeated pairwise-judgment settings like large consultations. Requiring every type to be a transitive ranking would impose additional constraints and would define a different mirror.
The weighted uncovered-set NP-completeness result in §4.2 is the right anchor. The problem is that its continuous version can lose the object the theorem computes: an inclusion-minimal support. This is more than the possibility that a minimum total size is unattained. The proposed threshold question still requires an inclusion-minimal certificate to exist.
Consider three candidates \(w,a,b\) and a population of complete pairwise-judgment types with pairwise masses \(p(w,a)=3/5\), \(p(a,b)=1/2\), and \(p(w,b)=1/2\). Such a population exists with support on the eight possible tournaments. By the paper’s path characterization, \(w\) is in the weighted uncovered set: it beats \(a\) by a strict majority and reaches \(b\) through \(a\).
For a partial mass matrix \(x\) to certify \(w\) in every completion, it must have \(x(w,a)>1/2\) and \(x(w,a)+x(a,b)>1\). The other routes cannot work: \(x(w,b)\) and \(x(b,a)\) are each at most \(1/2\). But any certificate can reduce \(x(a,b)\) by a sufficiently small positive amount and still satisfy both strict inequalities. Thus no certificate is inclusion-minimal, even though certificates exist with total mass arbitrarily close to \(1\). The proposed “exists a minimal support of size at most \(K\)” question answers no for every \(K\) on this valid continuous instance. Its threshold form avoids assuming a minimum total size exists; it does not ensure that a minimal support exists.
One can repair this by asking for the infimum certificate mass, or by requiring a fixed positive margin \(\varepsilon\) in the relevant comparisons. The infimum need not be attained, so it does not supply the paper’s promised certified explanation at that size. A margin requirement restores attainment, but adds a precision parameter absent from the paper’s exact “necessary winner under every completion” question. That may define a useful follow-up on survey precision, but it is a different explanatory target, and the choice of \(\varepsilon\) needs its own justification.
This is the strongest objection to this anchor: fractional evidence can make the exact minimal-support output vanish. It does not establish the requested universal negative. An infimum-mass or margin-qualified problem over typed populations is coherent and could be worth studying. So the case against this particular mirror is substantial; the case that no worthwhile continuous mirror exists in any scenario remains weak.
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.