| paper | d4-conf-aaai-2026-2238 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: The problem is in \(\mathrm{P}\): accept exactly when \(m\geq 7\). It is decidable in \(O(b)\) time, where \(b\) is the encoding length of \(m\). · discrete side: other · adjudication: proved
full proof & adversarial review →
Proposition 16
statement extracted from the paper’s text layer
Given \(m\), does there exist a rational distribution \(\mu\) over strict rankings \(\pi \in S_m\), with \(\sum_\pi \mu_\pi = 1\) and pairwise distinct margins \(\Delta_\mu(a,b)\) for distinct ordered pairs \((a,b)\), such that the unique SSV winner is defeated under Split Cycle?
Types are complete rankings \(\pi \in S_m\), with rational mass variables \(\mu_\pi \ge 0\) summing to \(1\). The feasibility witness must induce pairwise distinct margins and an SSV winner defeated under Split Cycle; there is no optimization objective.
The mirror covers the tie-free SAT counterexample-existence investigation and its outcomes in Theorems 17 and 18; it leaves tied-margin variants, the single-Split-Cycle-winner search, and supplied-society winner-computation complexity outside.
The strongest honest mirror is narrow: the paper’s tie-free search for a counterexample to “SSV always selects a Split Cycle winner.” I would not claim the paper proves a standard complexity classification for winner computation; its conclusion explicitly leaves the complexity of computing SSV and Stable Voting winners open.
A plausible regime is a large party or union election with seven candidates. Each voter’s type is their complete ranking of those candidates. Voters who submit the same ranking are indistinguishable to both rules; the society is a rational mass distribution \(\mu\) over the \(7!=5040\) possible rankings. A population of millions might have only hundreds of distinct rankings, so \(N\gg\tau\). Mass is the fraction of members with each ranking; the winner remains a discrete candidate.
My lead problem is Continuous SSV Counterexample Existence. Given \(m\), the variables are masses \(\mu_\pi\ge 0\) for rankings \(\pi\in S_m\), with \(\sum_\pi\mu_\pi=1\). Define the normalized margin
\[
\Delta_\mu(a,b)=\sum_{\pi\in S_m}\mu_\pi
\bigl(\mathbf 1[\pi:a>b]-\mathbf 1[\pi:b>a]\bigr).
\]
Require all margins between distinct ordered pairs to be unequal, as in the paper’s linear ordinal margin matrices. The question is whether there is such a society whose unique SSV winner is defeated under Split Cycle. A yes answer has a rational mass distribution as a witness; a no answer means every such distribution has an SSV winner among the Split Cycle winners. This is a feasibility question over the population distribution, not a continuization of the outcomes.
The eligible anchor is Proposition 16, proved in this paper. It states that, for the paper’s conjunction \(\phi\) of constraints encoding a linear ordinal margin matrix, SSV winners on its restrictions, and Split Cycle reachability, there is a linear ordinal margin matrix in which the SSV winner is not a Split Cycle winner if and only if
\[
\mathrm{SSV}_{[n],1}\wedge \neg\mathrm{SC}_1\wedge\phi
\]
is satisfiable. This is a SAT-formulation result, and the authors compute with that formulation. I would not describe it as an NP-hardness or polynomial-time theorem.
The computed outcomes are Theorem 17 (proved here): for every linear ordinal margin matrix with at most six alternatives, the SSV winner is a Split Cycle winner; and Theorem 18 (proved here): for every \(n\ge 7\), there is a linear ordinal margin matrix whose SSV winner is not a Split Cycle winner. The first includes the solver-backed six-alternative result; the second extends the seven-alternative counterexample to every larger \(n\).
This is a faithful population mirror because the margins come directly from ranking-type masses, and the paper’s Lemma 2 proves that every ordinal margin matrix it considers is realized by a finite preference profile. Conversely, any rational \(\mu\) can be converted to a finite profile by clearing denominators. Thus the continuous problem has the same answers: no counterexample for \(m\le 6\), and a counterexample for every \(m\ge 7\). For this decision question, the paper’s results give a tractable threshold in \(m\). If a society is supplied instead, its margins can be computed in time polynomial in \(m,\tau,L\); evaluating SSV by its recursive definition takes \(2^m\operatorname{poly}(m)\) time. The complexity of that supplied-society winner problem is a further question, not a result of this anchor.
The mirror covers the paper’s tie-free SAT investigation and its SSV–Split Cycle relation, not its treatment of tied margins or the broader use of SAT for other voting methods and axioms. Its weakest point is also clear: with rational masses, this question is exactly equivalent to one over finite profiles. It shows that population continuization gives a natural type-mass formulation and carries the paper’s result intact, but it does not uncover a new tractability gain or make discrete hardness dissolve.
The strongest objection is that the proposed anchor is not a computational result of the kind ChoCo is meant to mirror. Proposition 16 proves that a counterexample to a rule property exists exactly when a particular SAT encoding is satisfiable. Theorems 17 and 18 then settle that property for ordinal margin matrices: the conjecture holds through six alternatives and fails from seven onward. SAT is the proof method; the theorems do not classify the complexity of an algorithmic problem on a supplied society. The paper explicitly leaves winner-computation complexity open.
The proposed “Continuous SSV Counterexample Existence” does not fix that gap. Its input is essentially \(m\), not a society \(\mu\): it asks whether *some* distribution witnesses a rule property. That is a search over the same abstract margin matrices the paper already studies. Lemma 2 realizes every such matrix by a finite profile, and rational ranking masses can conversely be scaled to finite voter counts. This is not objectionable because the answers coincide; it is a mismatch of question type. The mirror remains a theorem about the rules, rather than a computational problem on a continuous population.
A more useful candidate would take a supplied rational distribution over ranking types and ask for the SSV winner, or whether that winner is also a Split Cycle winner. That is a sensible high-multiplicity voting problem, but it is not anchored by Proposition 16 or Theorems 17–18. The paper’s input is already an ordinal ordering of pairwise margins, and its rule depends only on that ordering. From \(\mu\), one can compute the margins and their order; the population masses then play no further role. Studying the complexity of that supplied-society problem could be worthwhile, especially since the paper names winner computation as open, but it would be a new question rather than a continuous mirror of a result established here.
Mass-robustness questions—such as the least transfer needed to change the SSV winner or make it disagree with Split Cycle—are also plausible extensions. They add a baseline society and an intervention objective that this paper does not study. So the negative case defeats the proponent’s stated anchor, but it cannot honestly establish that no worthwhile continuous question could be built around the paper. Its strongest conclusion is narrower: the paper supplies a rule-property theorem and a SAT proof technique, not a computational result on population instances to continuize.
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.