| paper | d4-journals-mss-2016-0006 |
| 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: Polynomial-time solvable, including the binary count and the complete list of value tables. · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 18
Given \(m\) alternatives, a rational distribution \(\mu\) supported on \(\tau\) rankings, and an explicitly listed subgroup \(U\le S_m\) of alternative relabelings, let \(U\mu=\{\psi\mu:\psi\in U\}\) and \(B(\nu)=\arg\max_{c}\sum_q\nu_q(m-\operatorname{rank}_q(c))\). Count and compactly describe the deterministic rules \(f:U\mu\to C\) satisfying \(f(\nu)\in B(\nu)\) and \(f(\psi\nu)=\psi f(\nu)\) for every \(\nu\in U\mu\) and \(\psi\in U\).
Society types are complete rankings \(q\), with rational masses \(\mu_q\); the input is one such distribution and an explicitly listed relabeling group \(U\). The decision is a winner choice at each society in \(U\mu\), constrained to be a Borda winner and equivariant under \(U\). The count is \(\left|B(\mu)\cap\operatorname{Fix}(\operatorname{Stab}_U(\mu))\right|\).
The paper counts refinements across all finite-profile orbits, while the proposed problem counts choices on only one society orbit, so it captures a local factor rather than the global count.
fatal: False
Covers the constructive choice and exact count on one \(U\)-orbit; leaves the global product over finite-profile orbits, the arithmetic existence conditions, and reversal-bias refinements aside.
The best positive case is narrow. This paper has no named NP-hardness or polynomial-time result. Its closest computational anchor is Theorem 18, proved here: for a regular subgroup \(U\leq S_h\times S_n\times\{id\}\), a \(U\)-consistent correspondence \(C\), and representatives \(p^j\) of the \(U\)-orbits, every \(U\)-consistent resolute refinement is uniquely determined by choosing one winner \(x_j\in C(p^j)\) per representative. In particular, the paper gives the exact count
\[
|\mathfrak F_C^U|=\prod_{j\in\mathcal P^U}|C(p^j)|
\]
and proves that this set is nonempty. This is a counting and construction result, not a complexity classification, but it is the paper’s clearest computational foothold.
A plausible regime is a large membership association whose members vote on a small policy agenda. Members fall into a small number \(\tau\) of ballot types, even as the total population grows; ballot frequencies are given as binary rational masses. Alternatives may also come in categories, such as policy options within several domains. A type is a complete ranking, and \(\mu_q\) is the fraction of society with ranking \(q\). The society is the distribution \(\mu\), rather than a named list of voters. This is credible when the association has many members but only a modest number of distinct ballots.
The mirror I would put forward is Mass-Orbit Refinement Counting. For a concrete version, take the continuous Borda correspondence
\[
B(\nu)=\arg\max_{c\in C}\sum_q \nu_q\bigl(m-\operatorname{rank}_q(c)\bigr).
\]
An instance consists of the alternatives, a rational mass distribution \(\mu\) over its supported rankings, and an explicitly listed group \(U\) of allowed alternative relabelings, such as permutations within the specified subclasses. Ask for the number of deterministic tie-breaking rules on the finite orbit \(U\mu\) that always choose from \(B(\nu)\) and satisfy \(f(\psi\nu)=\psi f(\nu)\) for every \(\psi\in U\). A solution is the exact count, with a compact description of the rules.
This mirrors the paper’s orbit-by-orbit construction: the population distribution replaces a finite profile, and a valid winner choice at one orbit representative determines choices throughout its orbit. For this Borda version, the count is
\[
\left|B(\mu)\cap\operatorname{Fix}\bigl(\operatorname{Stab}_U(\mu)\bigr)\right|.
\]
A winner at \(\mu\) extends consistently across the orbit exactly when it is fixed by every relabeling that leaves \(\mu\) unchanged. With \(U\) explicitly listed, the stabilizer and Borda winners can be computed in time polynomial in \(m,\tau,L,\lvert U\rvert\). I expect this stated version to be tractable; extensions to succinctly represented groups and other correspondences are further questions.
The authors would likely recognize the underlying question: choose a unique winner from a correspondence while preserving the permitted symmetry. The population is genuinely continuous here, even though a rational mass vector can also be realized by a sufficiently large finite electorate. The useful computational parameters are the number of alternatives, the support size \(\tau\), and the mass bit length \(L\), rather than the electorate size.
The weakest point is that Theorem 18 counts refinements over the paper’s full finite profile space, whereas my problem counts consistent choices on one population’s orbit. Extending the count to *all* rational societies creates an infinite domain, and the paper supplies no complexity result for that task. Also, mass distributions can have exact symmetries that obstruct a unique neutral choice, so the discrete theorem’s regularity guarantee does not carry over automatically. This is therefore a defensible, limited computational mirror of the paper’s refinement construction—not a claim that the paper already contains a continuous complexity result, or that its arithmetic existence theorems transfer unchanged.
The association scenario is sound: many members can share a small set of rankings, and rational masses are a natural way to describe them. I would not object that this is “already high multiplicity”; that supports the regime. The problem is the computational anchor.
Theorem 18 counts refinements by making one choice at each orbit representative in the paper’s finite profile space. It gives a structural count, but no running-time result, and it treats the correspondence abstractly rather than as an encoded computational input. For the proposed Borda question, the fixed-winner formula is correct. But on a single orbit, the entire task reduces to computing Borda winners and checking which are fixed by the stabilizer. That is a small symmetry check on one society, not a computational mirror of Theorem 18’s global count of refinements.
The more faithful version would ask for refinements over all continuous societies. That domain has infinitely many mass vectors, so counting all global rules has no finite count in the sense of the paper’s theorem. Restricting it to mass vectors below a denominator or bit-length bound makes a finite problem, but the cutoff then defines the task; it is not supplied by the refinement result. Asking only whether a global rule exists also changes the question: it becomes a condition on stabilizers across the domain, rather than a computation of the paper’s count.
So I do not think the proposed anchor establishes a worthwhile ChoCo mirror: its well-defined local version is an elementary orbit calculation, while the global version needs a new computational question and a domain encoding. The negative case is not airtight. A carefully chosen, succinctly represented family of societies might yield a meaningful global counting or construction problem, and the paper’s group-action framework could help. The paper itself, however, does not point to that problem or supply a complexity result to 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.