| paper | d4-conf-aaai-2007-0316 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | no |
Theorem 5 is a named NP-completeness result, so the computational gate passes. But the proposed mass distribution weights benchmark constraints; it does not continuize a voter population, and a voter distribution yields one tournament rather than the independent constraints TREE-SAT needs. Weighted tree fitting is well-posed and its zero-error hardness transfers, but that is outside the programme’s population mirror.
fails bit b-none — no population with multiplicity to relax
The cases are weighted training tasks, not masses of agents in a social-choice instance; a voter population cannot supply the independent tournament–winner constraints needed by TREE-SAT.
fatal: True
The proposed case-weighted fitting problem covers only Theorem 5. It leaves the PAC sample-complexity results in Theorems 3 and 4 aside; their distribution is over examples, not a continuous voter population.
The strongest case is a narrow mirror of TREE-SAT, where the population consists of rule-use cases rather than voters. Each case supplies a tournament and the winner the target rule is supposed to return. This uses the paper’s actual input and output objects.
The anchor is Theorem 5, stated in this paper as “TREE-SAT is NP-complete”; the authors say its proof is omitted for space. In TREE-SAT, the input is a binary-tree shape with some leaves already labeled by alternatives, plus a training set of tournament–winner pairs. The question is whether the unlabeled leaves can be assigned alternatives so that the tree returns the specified winner on every training tournament.
Here is a continuous version. A large federation of election services or rule-design clients uses one voting-tree structure \(B\). Each client contributes a benchmark case: a tournament \(\succ\) and the target rule’s required winner \(y\). Cases with the same pair \(t=(\succ,y)\) have the same type. Let \(\mu_t\) be the rational fraction of the client population with type \(t\), with \(\sum_t\mu_t=1\) and support size \(\tau\). Given \(B\), its preassigned leaves, and this distribution, assign alternatives to the remaining leaves to minimize
\[
\sum_{t=(\succ,y)} \mu_t\,\mathbf{1}\!\left[W_{B,\sigma}(\succ)\ne y\right],
\]
where \(\sigma\) is the leaf assignment and \(W_{B,\sigma}(\succ)\) is the tree’s winner. The zero-error decision version asks whether the minimum is \(0\). A solution is a leaf assignment attaining the minimum, or, for the decision version, one with zero error.
This is plausible as a high-multiplicity regime when many deployments reuse a smaller set of tournament-and-winner templates: the population \(N\) can be large while the number of distinct types \(\tau\) is much smaller. The type includes both the tournament and its required output, so the mass objective measures the fraction of use cases the shared tree serves correctly.
The zero-error problem is NP-complete: take any TREE-SAT instance with \(q\) examples and give each example mass \(1/q\). There is a zero-error assignment exactly when the original training set is consistent. Thus the hardness transfers from finite TREE-SAT; it does not depend on the mass granularity disappearing. The weighted optimization version is NP-hard as well. Further questions include whether the problem is fixed-parameter tractable in \(\tau\) or the number of unlabeled leaves, and what approximation guarantees are possible when some positive error is allowed.
This mirrors the paper’s computational question closely: the tree structure, the leaf-label decisions, and the correctness criterion are retained. It covers Theorem 5 specifically; it does not claim a new continuous interpretation of the paper’s PAC sample-complexity results, which already use a distribution over tournaments.
The weak point is that the population is a constructed population of benchmark cases or deployments, not the electorate in an ordinary election. Also, the paper treats examples as a training set, whereas this mirror supplies a known rational mass distribution over them. That makes this a credible but narrow continuous mirror: authors could recognize the same consistency problem with population-weighted error, though they may regard the population interpretation as less natural than the underlying TREE-SAT correspondence.
The only named anchor is Theorem 5, and it is a genuine computational result: TREE-SAT is NP-complete. The strongest objection is about what gets continuized.
TREE-SAT assigns labels to leaves so one tree matches a finite set of tournament–winner constraints. The proposed distribution \(\mu\) weights those constraints. That gives a natural weighted tree-fitting problem, but its mass measures the frequency of benchmark tasks. Each type contains a whole tournament and an externally specified label; the paper has no population of voters whose preferences are being aggregated. Its PAC model already has a distribution \(D\) over tournaments, so replacing the training set with weighted cases puts mass on the sample space, rather than on the society in ChoCo’s central model. A valid version would also require the labels to be consistent with one target rule: the same tournament cannot demand two different winners.
A genuine voter population does not supply TREE-SAT’s many constraints. A distribution over voter rankings induces one majority tournament, on which the tree returns one winner. To retain a training set of independent tournaments, one must put a voter distribution inside each election context and then put mass over those contexts. That is a coherent model for many jurisdictions or rule deployments, and it could make weighted tree fitting worth studying. Its population is the set of contexts or deployments, though; the voters’ population remains inside each type. The mirror therefore depends on ChoCo treating repeated tasks as an in-scope population.
This is a meaningful scope objection, not a technical refutation of the proposed optimization problem. If ChoCo accepts deployments as agents, the proponent has a credible mirror, and I cannot honestly argue that no worthwhile scenario exists. If the programme requires continuizing the electorate itself, the case for this anchor is weak: the submitted construction makes a distribution over tasks continuous, while a voter distribution collapses the many TREE-SAT inputs to a single tournament.
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.