| paper | d4-conf-wine-2022-0026 |
| 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: Deterministic polynomial-time solvable. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given a finite support of complete rankings \(\rho\), with positive binary-rational masses \(\mu_\rho\) summing to \(1\), a target candidate \(a\), and a rational threshold \(q\), let \(p_\rho\) be the position of \(a\) in \(\rho\). For each supported type and each \(d\in\{0,\ldots,p_\rho-1\}\), choose mass \(x_{\rho,d}\) to move to the ranking obtained by moving \(a\) up \(d\) adjacent positions, subject to \(\sum_d x_{\rho,d}=\mu_\rho\), \(x_{\rho,d}\ge 0\), and \(\sum_{\rho,d:\,a\text{ ranks above }b}x_{\rho,d}\ge\tfrac12\) for every \(b\ne a\). Is the minimum per-capita swap cost \(\sum_{\rho,d}d\,x_{\rho,d}\) at most \(q\)? The weak pairwise inequalities give the infimum cost for making \(a\) strictly beat every opponent.
A continuous mass-transfer LP over \(\tau\) supported ranking types: each type has rational mass, decision variables move portions of that mass upward by adjacent swaps, and the objective minimizes total per-capita swap cost subject to the target’s Condorcet constraints.
Theorem 1’s distinctive hardness guarantee concerns independently sampled rankings from adversarially chosen preference laws, while the proposed problem takes a deterministic mass distribution as input.
fatal: False
The mirror covers the underlying Dodgson score problem in Theorem 1, but not its semi-random sampling guarantee or the results for Young, Kemeny, Chamberlin–Courant, and Monroe.
The strongest mirror I see is the Dodgson score problem in Theorem 1, proved in this paper using a reduction based on Bartholdi, Tovey, and Trick [5]. The theorem says that for any sequence of preference models that is polynomial-time samplable, neutral, and satisfies Assumption 1, there is no polynomial-time algorithm for SEMI-RANDOM-DODGSONSCORE unless \(\mathrm{NP}=\mathrm{ZPP}\). Assumption 1 requires that, for some constant \(d>1\), each sufficiently large agenda has a distribution under which a fixed top-\(K\) ranking is preserved with probability at least \(1-1/K\), where \(K=\lceil m^{1/d}\rceil\). The semi-random problem asks whether a designated candidate’s Dodgson score is at most \(t\) in a profile whose voters’ rankings are sampled independently from distributions chosen by an adversary; the algorithm must answer correctly with probability at least \(1-1/m\).
A plausible population regime is a large electorate ranking a shared slate of candidates or policies, with many people repeating the same complete ranking. A ranking is a complete voter type; its mass is the fraction of the electorate with that ranking. For instance, a survey or platform could have millions of respondents but only hundreds or thousands of recurring ballot types, so the population size \(n\) greatly exceeds the support size \(\tau\). The paper’s top-\(K\) randomization is a noise model over finite profiles; this mirror takes up the underlying Dodgson score question, not that randomization mechanism.
Call the continuous problem Continuous Dodgson Score. Its input is a finite support of complete rankings \(\rho\) with positive binary-rational masses \(\mu_\rho\) summing to \(1\), a target candidate \(a\), and a rational threshold \(q\). Let \(p_\rho\) be \(a\)’s position in \(\rho\). For each supported type and each \(d\in\{0,\ldots,p_\rho-1\}\), choose mass \(x_{\rho,d}\) to move from \(\rho\) to the ranking \(\rho^{(d)}\) obtained by moving \(a\) up \(d\) adjacent positions. The continuous score is the minimum per-capita swap cost subject to the resulting society making \(a\) a Condorcet winner:
\(\displaystyle D_\mu(a)=\min \sum_{\rho}\sum_{d=0}^{p_\rho-1}d\,x_{\rho,d},\quad \sum_d x_{\rho,d}=\mu_\rho,\quad x_{\rho,d}\ge0,\quad \sum_{\rho,d:\,a\succ_{\rho^{(d)}} b}x_{\rho,d}\ge\tfrac12\ \ \forall b\ne a.\)
The value is the infimum cost for making \(a\) strictly beat every opponent; the weak inequalities compute that infimum, since an arbitrarily small further upward move can make any tied contests strict without harming others. The problem asks whether \(D_\mu(a)\le q\), with the optimal mass shifts as a solution. Moving \(a\) upward suffices: swaps between other alternatives do not affect its pairwise contests, and moving \(a\) down cannot help. This leaves at most \(\tau m\) variables and polynomially many constraints, so exact rational linear programming solves it in time polynomial in \(m,\tau\), and the input bit length \(L\). I expect this mirror to be Class A.
The match to the authors’ problem is direct: the target, the Condorcet condition, and the adjacent-swap cost are all preserved. Only the electorate representation changes: a variable can move a fraction of a ranking type, while every individual represented still has a complete, integral ranking. The continuous score is the high-multiplicity relaxation of the discrete score. For a profile \(P\) of \(n\) voters, setting \(\mu_\rho\) to the fraction of voters with ranking \(\rho\) and \(q=t/n\) gives the corresponding normalized question; allowing arbitrary \(x_{\rho,d}\) removes the discrete indivisibility constraint. Theorem 1’s semi-random hardness does not settle whether this relaxation is hard or easy—that is the question this mirror makes concrete.
This case covers the underlying DODGSONSCORE object in Theorem 1, not its semi-random success-probability guarantee, and does not mirror the paper’s Kemeny, Young, Chamberlin–Courant, or Monroe results. Its weakest point is exactly that distinction: Theorem 1 concerns noisy finite profiles, whereas the proposed problem is a deterministic mass-transfer score problem. I think the mirror remains persuasive because it retains the score the theorem analyzes and places it in a credible large-population regime. It also opens useful follow-ups: how the normalized discrete score approaches the LP value under electorate replication, how large the integrality gap can be, and whether score gaps give useful winner-robustness guarantees.
The proposed LP is a sound continuous Dodgson score, and repeated ranking types are a credible large-population regime. I see no honest case that mass is meaningless here or that the score collapses in the limit.
The weakness is its link to Theorem 1. That theorem concerns SEMI-RANDOM-DODGSONSCORE: an adversary chooses a preference distribution for each voter, Nature samples rankings independently, and the algorithm must answer correctly with high probability. The hardness proof uses this sampling guarantee to preserve a constructed profile’s top-ranked alternatives with substantial probability. The proposed \(D_\mu(a)\) takes a deterministic distribution of rankings as input and allows fractional mass to move until \(a\) is a Condorcet winner. It removes the per-voter distributions, the random draw, and the success-probability requirement. It mirrors the Dodgson score the paper defines, but it does not capture the computational question Theorem 1 proves hard.
A closer mirror could group voters by their sampling law and retain the random profile question. That would require choosing how the population size, number of law types, agenda size, and noise level scale. If the number of law types grows with the electorate, the high-multiplicity compression can disappear; if the population tends to a limit, the finite-profile guarantee changes. The paper gives no particular limit or restriction that selects among these models. Such a formulation could be worth studying, but it would be a newly designed stochastic population problem.
The programme’s own prior work already treats continuous Dodgson score as a tractable mass-transfer problem. That fact alone does not invalidate a well-posed mirror under the programme’s rules. It does mean the proposed LP offers little new target; its value would need to come from a convincing bridge to the paper’s semi-random theorem, and the case presented supplies none. I would reject this anchor as a mirror of Theorem 1. The broader claim that no stochastic population version could be worthwhile remains weak: a carefully specified model over sampling-law types might survive.
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.