| paper | d4-conf-atal-2011-0098 |
| 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; both the minimum radius and a witnessing reassignment can be computed. · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Proposition 4.8
statement extracted from the paper’s text layer
Given \(m\) candidates, a target \(c\), and a rational distribution \(\mu\) over \(\tau\) complete rankings with \(\sum_t\mu_t=1\), find the least integer \(r\) for which there are masses \(x_{t,u}\geq 0\) satisfying \(\sum_u x_{t,u}=\mu_t\), \(x_{t,u}=0\) whenever the Kendall swap distance \(d_{\mathrm{swap}}(t,u)>r\), and \(\sum_{t,u:\,c\succ_u d}x_{t,u}>1/2\) for every opponent \(d\neq c\). Return \(r\) and a witnessing reassignment.
Ranking types carry population mass \(\mu_t\); decision variables \(x_{t,u}\) reassign that mass to rankings within radius \(r\). Minimize the maximum per-agent number of adjacent swaps needed to make \(c\) a Condorcet winner.
The mirror covers the candidate-score computation underlying Dodgson-\(\ell_\infty\). It leaves the paper’s homogeneity and monotonicity results and its characterization of majority-variant scoring rules untouched.
The strongest mirror is the paper’s Dodgson\(_\infty\) candidate-score computation.
Anchor. Proposition 4.8, proved in this paper, says that computing a candidate’s \((C,\widehat d^\infty_{\mathrm{swap}})\)-score is in P. That score is the minimum, over elections in which the candidate is a Condorcet winner, of the largest number of adjacent swaps made to any one voter’s ranking. The paper’s algorithm repeatedly moves the candidate up one position in every vote where they are not first, stopping when they become a Condorcet winner. This is specifically the \(\ell_\infty\)-based Dodgson variant, not the classic Dodgson score. The paper gives no numbered hardness result to anchor a continuous hardness mirror.
Here is the continuous problem I would put to a prover: Continuous Dodgson\(_\infty\) Score. An instance consists of \(m\) candidates, a target \(c\), and a society \(\mu\) supported on \(\tau\) complete rankings, with each mass \(\mu_t\) a binary rational and \(\sum_t\mu_t=1\). Find the smallest integer \(r\) for which there is a mass-preserving reassignment \(x_{t,u}\geq 0\) from original rankings \(t\) to new rankings \(u\), with \(\sum_u x_{t,u}=\mu_t\), such that \(x_{t,u}>0\) only when the Kendall swap distance from \(t\) to \(u\) is at most \(r\), and \(c\) is a Condorcet winner in the resulting society. Thus, for every other candidate \(d\), more than half the resulting mass ranks \(c\) above \(d\). A solution gives both the minimum \(r\) and a reassignment witnessing it. This preserves the paper’s bottleneck objective: it minimizes the greatest per-person change, not total campaign effort.
The type is a complete ranking because that is all the paper’s swap metric uses; mass is the fraction of society holding that ranking. A plausible regime is a very large membership vote with many ballots but relatively few distinct template or party-line rankings, so \(N\gg\tau\). Every member with the same ranking is identical for this problem. This makes the high-multiplicity input substantive: listing \(N\) people may be infeasible even when the \(\tau\) rational masses have short binary descriptions.
I expect this continuous score problem to be tractable in \(\mathrm{poly}(m,\tau,L)\), where \(L\) is the mass encoding length. The paper’s round-by-round algorithm lifts directly: in each round, move \(c\) up one place in every supported ranking where it is not first, carrying that ranking’s whole mass with it. Check the weighted pairwise contests after each round. There are at most \(m-1\) rounds, and each update and check uses only the supported rankings and rational arithmetic. For correctness, moving \(c\) up \(r\) places crosses as many candidates as any ranking reachable within \(r\) adjacent swaps can cross, and improves \(c\)’s pairwise position against each crossed candidate. Thus, if any reassignment with maximum cost \(r\) makes \(c\) Condorcet, this canonical movement does too. Repeating the score computation for each candidate also gives the induced winner rule. This is a tractable mirror, with the high-multiplicity algorithm as the concrete gain.
The scope is deliberately narrow: it mirrors Proposition 4.8’s Condorcet-consensus, \(\ell_\infty\)-swap score. It does not continuize the paper’s axiomatic results about homogeneity and monotonicity, or its characterization of majority-variant scoring rules.
The soft spot is that the discrete problem is already in P. This mirror does not show discrete hardness dissolving; its contribution is the compressed, mass-based input regime and the corresponding \(\mathrm{poly}(m,\tau,L)\) algorithm, rather than a new tractability phenomenon. Further questions include whether the lift survives weighted or type-dependent swap costs, and how continuous average-cost (\(\ell_1\)) versions compare with this bottleneck version.
Proposition 4.8 is the one serious computational anchor the proponent raises. Its continuous mirror is well posed, and the proposed membership-vote setting gives it a plausible high-multiplicity interpretation. The weakness is that the mass-transfer formulation immediately collapses to the paper’s existing procedure with weighted sums.
Fix a candidate \(c\) and an integer radius \(r\). For each supported ranking \(t\), move \(c\) up by \(\min(r,\operatorname{rank}_t(c)-1)\) positions. This gives \(c\) at least as much pairwise support against every opponent as any ranking reachable from \(t\) within \(r\) adjacent swaps. Consequently, if any fractional reassignment within radius \(r\) makes \(c\) a Condorcet winner, moving every type’s full mass this canonical way does too. The optimum is found by checking at most \(m\) radii and recomputing weighted pairwise contests over the \(\tau\) supported rankings. There is no mass-allocation optimization left to solve.
That gives a legitimate compressed-input algorithm in \(m,\tau,L\), but its content is narrow: the paper’s round-by-round proof carries over by replacing voter counts with rational weights. There is no new separation problem, continuous optimization method, or fractional structure to investigate. The mirror’s only distinct contribution is the high-multiplicity encoding. That encoding matters when masses are compact binary inputs, though here it makes an already polynomial-time computation faster in the population size.
A stronger practical framing might charge for total mass moved, so that changing a tiny fraction of voters costs less than changing everyone. That is a different objective from Proposition 4.8’s \(\ell_\infty\) score. It also leads toward the continuous Dodgson problem already listed among ChoCo’s worked results, rather than opening a new question from this paper. Keeping the \(\ell_\infty\) objective preserves the anchor but leaves the canonical algorithm; changing it yields a more substantial question but loses the specific result being mirrored.
This is the best negative case I can make, and it does not establish the universal claim. A researcher could reasonably value even this exact high-multiplicity formulation, especially as a simple validation of the population-as-distribution model. The case against rests on prioritization: this paper’s lone computational mirror appears to add little beyond weighted aggregation of a short existing algorithm.
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.