| paper | d4-conf-atal-2013-0016 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→P discrete result → its continuous mirror
Answer: Polynomial-time solvable: every promised instance admits a feasible evolution preserving \(a\) as the unique Borda winner. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 4.7
statement extracted from the paper’s text layer
Given a finite support of paired rankings \(h=(r_0,r_1)\) with rational masses \(\eta_h\), where the initial and final marginal societies both have unique Borda winner \(a\), does there exist a piecewise-linear evolution of mass in which each history’s mass moves only along adjacent-swap paths of length \(\kappa(r_0,r_1)\), and \(a\) remains a Borda co-winner in the aggregate society at every point?
Types are paired rankings \(h=(r_0,r_1)\) with mass \(\eta_h\). Decision variables \(x_{h,r}(s)\) track how much mass of each history currently holds ranking \(r\); permitted transitions swap adjacent candidates and reduce the remaining Kendall distance to \(r_1\). The aggregate society is \(\rho_s(r)=\sum_h x_{h,r}(s)\), and feasibility requires \(a\) to maximize Borda score under \(\rho_s\) throughout the route.
The repaired input is a distribution over paired ballot histories, so the question applies most naturally to a longitudinal panel with stable voter correspondence; the paper’s evolution discussion supports that setting but does not make it a generic cross-sectional mirror.
fatal: False
The mirror covers the Borda case of Theorem 4.7; it leaves that theorem’s Maximin and Copeland cases, the connectivity and convexity results, and the consensus-class results aside.
The strongest mirror I see is the Borda case of Theorem 4.7. The theorem states that, for each of Borda, Maximin, and Copeland, \(F\)-ShortestPath is NP-complete. Its input is a candidate set and two profiles with the same unique winner \(a\); it asks whether there is a shortest path between the profiles on which \(a\) remains a winner throughout. This is presented as a result of this paper, not cited prior work; the supplied text states the theorem without showing its proof. I would mirror the Borda case alone.
Call the continuous problem Borda Mass-Geodesic. Fix candidates \(C\), and let a type be a complete ranking \(r\) of \(C\). An instance gives two societies \(\mu,\nu\): rational distributions over rankings, specified by their positive-mass supports and binary rational masses. Both societies must have the same unique Borda winner \(a\). For a society \(\rho\), define its Borda score by \(\mathrm{Borda}_{\rho}(c)=\sum_r \rho_r(m-\mathrm{pos}_r(c))\), where \(\mathrm{pos}_r(c)\) is \(c\)’s position in ranking \(r\).
Measure the distance between societies by minimum earth-mover cost, using Kendall distance \(\kappa(r,r')\) between rankings: \(D(\mu,\nu)=\min_{\pi}\sum_{r,r'}\pi_{r,r'}\kappa(r,r')\), where \(\pi\) ranges over couplings of \(\mu\) and \(\nu\). A solution is a path of societies \(\rho_s\), for \(s\in[0,1]\), from \(\mu\) to \(\nu\), implemented by moving mass only between rankings that differ by one adjacent swap. Its total moved mass, counted once per adjacent swap, must equal \(D(\mu,\nu)\); so the path uses a minimum-cost sequence of swaps. The question is whether such a path exists with \(a\) a Borda winner at every point. The parameter \(s\) marks progress along a route through society space; the continuous object is the population distribution.
A natural regime is a large election or public consultation with many thousands or millions of voters, where ballots fall into a relatively small set of recurring rankings. A type is a ranking because the model uses preferences and adjacent swaps; mass is the fraction of the electorate holding that ranking. A gradual shift in opinion gives a plausible interpretation for the route, while its mathematical question remains the paper’s: what shapes do winner regions have under swap distance?
I expect this problem to be tentatively tractable (Class A). The mass can divide, Borda scores are linear in the distribution, and the requirement that \(a\) remain a winner is a set of linear inequalities along the route. That makes a constrained minimum-cost flow or LP formulation plausible, even though the ranking graph has \(m!\) vertices. The main question is whether the resulting optimization has a polynomial pricing or separation method in \(m,\tau,L\). Theorem 4.7’s discrete NP-completeness makes this a meaningful relaxation question; it does not establish that the continuous problem is hard or easy.
The mirror covers only the Borda shortest-path result. It does not try to continuize the paper’s connectivity results, its other voting rules, or its consensus classes. Further questions include whether shortest winner-preserving mass routes have polynomial-size rational certificates, whether the ranking-space LP admits efficient pricing, and which parts of the discrete hardness survive when multiplicities are represented only by masses.
My weakest point is the change in geometry. The paper’s profiles have voter coordinates, and a shortest path acts on those coordinates; a distribution forgets voter identities and lets the transport choose how to pair endpoint ballots. It can therefore admit a minimum-cost route absent from the paper’s fixed-coordinate graph. That is a real change. I think the mirror is still recognizable because it preserves the ranking types, adjacent-swap moves, and winner-region question, while making the electorate itself the aggregate object. The authors may see that as a substantive continuous-population extension rather than the exact same graph question.
The anchor is real: Theorem 4.7 proves NP-completeness of \(F\)-ShortestPath for Borda, among other rules. The stated earth-mover mirror, though, loses information the theorem uses. The paper’s profiles are ordered tuples, and the distance pairs each voter’s starting ballot with that same voter’s ending ballot. For example, with two rankings \(ab\) and \(ba\), the endpoint pairs \(((ab,ba),(ab,ba))\) and \(((ab,ba),(ba,ab))\) have the same society distributions at both ends. Their profile distances are \(0\) and \(2\), respectively. Earth-mover distance between the distributions is \(0\) in both cases. So the proposed input can identify instances whose shortest-path questions differ.
The strongest repair is to make a type an ordered pair of endpoint rankings and give a distribution over those pair types. Then mass can follow minimum-swap routes, with Borda winner constraints along the way. This preserves the voter correspondence while allowing many voters to share a type. A large panel with recurring preference changes is a plausible setting, and the paper itself discusses preferences evolving over time. That is a recognizable continuous-population question, not a flaw that can be dismissed by saying the formalism changed.
The remaining negative case is that this repair changes the object being studied. The input is now a distribution over voter histories, not a society described by its current preferences; changing the endpoint pairing can change the answer without changing either endpoint society. That makes it a poor mirror for cross-sectional elections unless the application genuinely supplies stable voter correspondences. But a longitudinal panel can supply them, and the paper’s discussion of evolving preferences gives the authors a reason to recognize that version.
So I can defeat the earth-mover formulation, but I cannot honestly defeat the paired-type version in every plausible scenario. The negative case is weak at its hardest point: the paper has a named computational result, and its paired-type extension has a credible high-multiplicity interpretation. I would not claim that no worthwhile continuous 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.