| paper | d4-conf-aaai-2026-1047 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
Answer: Polynomial-time solvable; designated-candidate membership belongs to \(\mathsf{P}\). · discrete side: polynomial · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 3.1
statement extracted from the paper’s text layer
Given a candidate set \(A\) and a support of \(\tau\) rankings \(t\), each with positive binary-rational mass \(\mu_t\) summing to \(1\), compute the set of alternatives selected by River under at least one descending tie-breaking order of the margin edges, where \(m_\mu(x,y)=\sum_{t:x\succ_t y}\mu_t-\sum_{t:y\succ_t x}\mu_t\).
Types are complete rankings of \(A\), carrying mass \(\mu_t\). The masses determine normalized pairwise margins and the margin graph; the output is the exact River-PUT winner set, optionally with a witnessing tie-breaking order for each winner.
The mirror covers the FUN computation in Theorem 3.1 and its correctness statement, Theorem 4.1. It does not cover the separate mass-change robustness proposal, the axiomatic study, or the finite-profile experiments.
My lead is the continuous high-multiplicity version of River-PUT winner computation. A type is a complete ranking of the alternatives, and its mass is the fraction of the electorate with that ranking. The intended regime is a large election or policy poll with \(n\) voters but only \(\tau\) distinct ballots, where \(\tau \ll n\). That is a credible regime for this paper: its voters are distinguished only by their preferences, so equal-ranking voters are indistinguishable for everything the rule uses.
The instance is a candidate set \(A\) and a list of \(\tau\) rankings \(t\), each with positive binary-rational mass \(\mu_t\), where \(\sum_t\mu_t=1\). For each pair \(x,y\), define the normalized margin
\[
m_\mu(x,y)=\sum_{t:x\succ_t y}\mu_t-\sum_{t:y\succ_t x}\mu_t.
\]
Form the margin graph using the paper’s convention: include \((x,y)\) when \(m_\mu(x,y)\ge 0\), with that margin as its weight. The problem, which I would call River-PUT\(_\infty\) Winner Computation, is to output
\[
W(\mu)=\{a\in A:\text{for some descending tie-breaking order of the margin edges, River selects }a\}.
\]
A solution is this exact winner set; a certificate tiebreaking order for each listed winner can accompany it.
The single lead anchor is Theorem 3.1, proved in this paper. It states that the FUN algorithm, run on a margin graph \(M=(A,E)\), has runtime polynomial in \(|A|\). Its correctness companion is Theorem 4.1, also proved here: an alternative belongs to RV-PUT exactly when it is cycle dominated or not dominated in the FUN diagram. Together they establish polynomial-time River-PUT winner computation on the paper’s margin-graph input. I treat Theorem 4.1 as the correctness statement needed to interpret the algorithmic anchor, rather than as a separate problem to mirror.
For the continuous instance, the margin graph can be built in polynomial time in \(m\), \(\tau\), and the total bit length \(L\) of the masses. Exact comparisons preserve ties between margins, which matter to PUT. Applying FUN then gives a Class A result, with runtime polynomial in \(m,\tau,L\). This is a close analogue of the paper’s actual problem: the population changes to a distribution over complete preference types, while River’s margin-based decision process and the question of which alternatives can win remain intact. The paper’s cited NP-completeness result for Ranked Pairs with PUT is not an anchor here; the paper’s own named computational anchor is its River algorithm.
This mirror covers the FUN winner-computation result and its correctness theorem. It does not continuize the candidate set, the tiebreaking orders, or an axiomatic question: only the voter population is represented by mass. Nor does it claim that the paper’s experimental comparisons are continuous-population results.
The honest weakness is that rational masses can be scaled by a common denominator to recover an ordinary finite profile, with the same margin order and the same River-PUT winners. So this is primarily a high-multiplicity, compressed representation, not a case where continuity creates new winner behavior or makes a hard discrete problem easy. That still makes it a sound mirror under the programme’s definition: it asks how the named computation behaves when the population is supplied as a compact distribution over types. A follow-on question is minimum-mass-change River-PUT robustness: given \(\mu\) and target \(a\), find a distribution \(\mu'\) minimizing \(\tfrac12\|\mu'-\mu\|_1\) subject to \(a\in W(\mu')\). I would leave its complexity open; changes in masses can reorder margins and cross tie boundaries.
The strongest case against is that Theorem 3.1 has already discarded the population before its computation begins. FUN takes a margin graph on \(m\) alternatives as input; the number and identities of voters no longer appear. Theorem 4.1 is its correctness statement on that same graph, not a separate population-level problem.
For a society supported on \(\tau\) rankings, computing the normalized margins takes \(O(\tau m^2)\) pairwise contributions, with exact rational arithmetic depending on \(L\). Then the existing algorithm applies. Scaling all margins by a common denominator gives the same edge order, ties, and winners as a finite profile. So River-PUT\(_\infty\) is well-defined, and the runtime bound follows, but the continuous formulation adds only a way to supply the graph. It does not expose a new population-dependent part of the decision problem or call for new algorithmic machinery. The paper’s result is already polynomial in the graph size, regardless of electorate size.
That is a case for low priority, not a decisive objection to the mirror. The proposed large-election regime is sensible, and the authors could recognize the distribution-input version as their winner-computation problem. The fact that the answer is unchanged under scaling cannot disqualify it under ChoCo’s stated standard.
The proposed minimum-mass-change robustness question is even harder to use against: it is a coherent population-level problem, since changing the distribution changes the margins. But it is not a result of this paper; it asks a new sensitivity question at a fixed rule. It might be worthwhile on its own, yet it cannot supply a reason that the paper’s named computation has no mirror.
So the negative case is weak at its central point. The best objection is that the mirror may be an easy re-encoding of an algorithm whose input already aggregates voters, rather than a rich new continuization result. I cannot honestly turn that into a claim that no worthwhile mirror exists.
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.