| paper | d4-conf-aaai-2026-2001 |
| 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: \(\mathsf{NP}\)-complete, even for \(b=3\), \(\tau\leq14\), \(\alpha=1/8\), and dyadic masses with denominator \(128\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 4.6
Given candidates \(C\), a finite support \(T\) of strict rankings with positive binary-rational masses \(\mu_t\) summing to \(1\), and bounds \(b\), \(k\), and rational threshold \(\alpha\), is there a partition of \(C\) into at most \(k\) nonempty parts \(X_i\), each of size at most \(b\), such that for every part, \(\sum_{t\in T:\,t\text{ ranks }X_i\text{ consecutively}}\mu_t\ge\alpha\)?
A distribution \(\mu\) over complete ranking types; the decision variable is a partition \(\Pi\) of candidates. Feasibility requires \(|\Pi|\le k\), each part to have size at most \(b\), and each part to be ranked consecutively by types of total mass at least \(\alpha\).
Covers the Independent-Clone Partition hardness result at \(b=3\), recognition threshold \(w=2\), and \(n=14\); it leaves the paper's approximate-clone, subelection-clone, and other parameterized results aside.
The strongest mirror is for the independent-clone partition problem. Theorem 4.6, proved in the paper, states that Independent-Clone Partition is NP-complete even when every clone has size at most \(3\), each clone must be recognized by at least \(2\) voters, and the election has only \(14\) voters. “Recognized” means that a voter ranks the clone’s members consecutively; different clones may be recognized by different voters. The paper proves the result by reduction from RX3C.
Here is a continuous version that keeps those requirements intact. An instance consists of candidates \(C\), a support \(T\) of complete rankings, binary-rational masses \(\mu_t>0\) summing to \(1\), a clone-size bound \(b\), a partition bound \(k\), and a rational threshold \(\alpha\). Ask whether \(C\) can be partitioned into at most \(k\) nonempty sets \(X_i\), each of size at most \(b\), such that for every part,
\[ \sum_{\substack{t\in T:\\ \text{ranking }t\text{ places }X_i\text{ consecutively}}}\mu_t \ge \alpha. \]
A solution is the candidate partition. This is a decision problem, not an optimization problem. Its exact mirror of the theorem sets \(b=3\) and \(\alpha=1/7\): represent each of the theorem’s \(14\) voters by mass \(1/14\), combining masses if two voters have the same ranking. A clone then meets the mass threshold exactly when at least two original voters recognize it.
The regime could be a large population of evaluators ranking the same candidates under standardized rubrics, with many evaluators sharing complete ranking patterns. For example, a public benchmarking exercise might rank universities or services using a small collection of recurring evaluation profiles. The type is the complete ranking; its mass is the fraction of evaluators with that ranking. The theorem’s hard instances need at most \(14\) types, while the population can contain arbitrarily many people by repeating those types.
I expect hardness to transfer. The continuous problem is in NP: a proposed partition is a polynomial-size witness, and each mass sum can be checked using the input rationals. The theorem’s reduction embeds directly using masses \(1/14\), so the continuous problem remains NP-hard even with \(b=3\), \(\alpha=1/7\), and support size at most \(14\). The reduction’s combinatorics are in how candidates can be grouped, not in a large population of individually distinct voters. The authors should recognize this as their problem with the natural population-share version of their “at least \(w\) voters” condition.
This case covers the independent-clone partition result, not the paper’s other clone notions. It also raises follow-up questions: how does the complexity change when \(\alpha\) varies, or when the goal is to minimize the number of parts for a given \(b\) and \(\alpha\)?
My weakest point is that the paper’s hardness result already uses only \(14\) voters. The continuous model makes the large population and population shares explicit, but the mass threshold is a normalization of a small integer threshold in the anchor result. The scenario is most convincing where many people really do share a small set of ranking types; for a highly diverse electorate, that assumption is less natural.
The strongest case against this mirror is that the paper’s hard instances do not need a large population: their combinatorics are already present with 14 voters. Replacing “at least two voters” by “at least \(1/7\) of the population” leaves that structure intact. So the exact reduction gives no evidence that aggregation makes the problem easier or exposes new structure; its difficulty is in partitioning the candidates.
That is a limitation of the motivation, though, not a reason the mirror fails. The population-share version is well defined, and \(1/7\) is not an arbitrary repair: fourteen equally weighted ranking types reproduce the theorem’s threshold exactly. A more general version with rational masses and threshold \(\alpha\) is also natural. Standardized evaluators who share recurring ranking profiles are a plausible high-multiplicity regime, and the partition condition depends only on those profiles. Neither candidate identity nor the finite ranking type space undermines the model.
I can’t honestly turn the fixed-population reduction into a decisive objection. The proposed problem survives the strongest test: it is a sensible computational question about a continuous population, even if the first known hardness result transfers unchanged and comes from a small support. My negative case is therefore weak; I do not see a defensible basis for claiming that this anchor has no worthwhile continuous mirror.
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.