| paper | d4-conf-atal-2018-0277 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
parameterized→P discrete result → its continuous mirror
Answer: Polynomial-time solvable exactly in \(L^{O(1)}\); consequently fixed-parameter tractable for \(r+\alpha\). · discrete side: parameterized · adjudication: proved
full proof & adversarial review →
Theorem 19
statement extracted from the paper’s text layer
Given a candidate set \(C\), its ranking types \(\mathcal T\), a rational distribution \(\mu\) supported on \(S\subseteq\mathcal T\), rational conversion costs \(\gamma(t,u)\), and a target condition \(\Psi\) given as a disjunction of systems of linear inequalities on type masses, find nonnegative transfers \(x_{t,u}\) minimizing \(\sum_{t\in S,u\in\mathcal T}\gamma(t,u)x_{t,u}\), subject to \(\sum_u x_{t,u}\leq\mu_t\) for each \(t\in S\) and \(\Psi(\mu')\). Here \(\mu'_u=\mu_u+\sum_{t\in S}x_{t,u}-\mathbf{1}_{u\in S}\sum_v x_{u,v}\); return an optimal transfer or report infeasibility.
Types are complete rankings \(t\in\mathcal T\), each carrying mass \(\mu_t\). Decision variables \(x_{t,u}\) transfer mass from supported rankings to destination rankings; the objective is total conversion cost, and the final mass vector must satisfy a quantifier-free linear winning condition. Each disjunct gives a rational LP; with all rankings explicit there are at most \(|S||\mathcal T|\) transfer variables.
The mirror covers the quantifier-free Minimum Move result of Theorem 19, including linear scoring-rule winner conditions. It leaves the paper’s quantified Dodgson and Young results, robust and resilient moves, and other applications unaddressed.
The cleanest positive case is the paper’s Theorem 19, proved in §5. The supplied paper has no numbered hardness result of its own, so an algorithmic anchor is the honest choice here. Theorem 19 says that if the winning condition \(\Psi\) is in the paper’s quantifier-free Presburger class—at most \(\delta\) disjuncts, each a conjunction of at most \(\gamma\) linear inequalities, with coefficients bounded by \(\alpha\) and constants by \(\beta\)—then Minimum Move with any linear objective \(f(\mathbf m)=\mathbf c^\top\mathbf m\) can be solved in time \(g(\gamma,\alpha)(\tau+\delta)^{O(1)}\log(\mathbf s)\), for computable \(g\). This is an algorithmic result proved in the paper, not a result merely cited from elsewhere.
A direct mass version is Continuous Minimum Mass Move. Let \(C\) be \(m\) candidates and let \(\mathcal T\) be their strict rankings. The input gives a rational distribution \(\mu\) over a supported set \(S\subseteq\mathcal T\), with \(|S|=\tau\) and total mass \(1\); nonnegative rational costs for changing one unit of mass from each ranking to another; and a winning predicate \(\Psi\) on the resulting ranking masses, expressed as the same kind of disjunction of linear systems. Choose nonnegative transfers \(x_{t,u}\), for \(t\in S\) and \(u\in\mathcal T\), with \(\sum_u x_{t,u}\leq\mu_t\). These produce \(\mu'_u=\mu_u+\sum_{t\in S}x_{t,u}-\mathbf 1_{u\in S}\sum_v x_{u,v}\). The task is to find a feasible transfer of minimum cost \(\sum_{t\in S,u\in\mathcal T}c_{t,u}x_{t,u}\) such that \(\Psi(\mu')\) holds. If \(\Psi\) is “the target wins under scoring rule \(s\),” it is the linear condition \(\sum_u\mu'_u s(u,c^\star)\geq\sum_u\mu'_u s(u,c)\) for every \(c\in C\). The solution is an optimal transfer vector and its resulting society; infeasible instances have no solution.
For swap bribery, a type is a complete ranking, since the anchor’s uniform-cost setting gives every voter the same swap tariff. Set \(c_{t,u}\) to the least cost of converting ranking \(t\) to \(u\) by adjacent swaps; with unit swap costs this is Kendall distance. Each ranking remains an ordinary complete ranking: the decision splits a type’s mass among rankings. In a large electorate with stable ballot categories, the number of voters can greatly exceed the number \(\tau\) of rankings actually present. The full universe has \(m!\) possible rankings, so this formulation is explicit about the potential type count as well as the support size.
This is close to the paper’s own abstraction: it defines societies by type counts, moves by transfers between types, and studies Minimum Move with linear objectives and winning conditions. The mirror changes integer counts and moves into rational masses and divisible transfers, while keeping rankings, swap costs, the winner condition, and the optimization objective recognizable. It continuizes the population; it does not fractionalize anyone’s ballot or the election’s outcome. The paper’s existing high-multiplicity framing supports the plausibility of this regime.
I expect this mirror to be Class A. For each disjunct of \(\Psi\), the constraints on \(x\) and \(\mu'\) form a rational linear program; solve each one and take the least-cost solution. With all rankings available as destinations, the formulation has at most \(\tau m!\) transfer variables, yielding a bound of the form \(f(m,\delta,\gamma,\alpha)\operatorname{poly}(\tau,L)\), where \(L\) is the input bit length. The open follow-up is whether useful cases can avoid enumerating the \(m!\) destinations by solving a pricing problem, and when the resulting mass optimum can be rounded into an efficient discrete preprocessing or approximation guarantee.
My weakest point is that this is a modest mirror: the paper already studies integer societies with types, and the continuous version of this quantifier-free case becomes an LP almost immediately. It therefore offers a plausible, tractable mass formulation, but it does not show discrete hardness dissolving, and it makes no claim about the paper’s quantified Dodgson and Young results.
Theorem 19 is the strongest anchor, and the best case against it is that its continuous version may contribute little new machinery. For an explicit finite type universe, each disjunct of the continuous Minimum Move problem is a rational linear program over transfer variables, with flow constraints and linear winning constraints. The integer theorem’s pre-\(n\)-fold machinery, integer feasibility, and dependence on \(\log(\mathbf{s})\) disappear; ordinary LP optimization gives the continuous answer.
That objection weakens sharply for the better mirror: rankings can be exponentially numerous, while the society is given by a small support and swap costs may be implicit. Avoiding an explicit LP then requires a pricing algorithm. For scoring constraints and swap distances, that can lead directly to the kind of permutation optimization the programme identifies as open. The paper’s high-multiplicity model also makes a society of ballot shares a natural regime, and the mirror preserves what its manipulation problem asks: moving mass between complete voter types at minimum cost.
So the negative case is weak. The finite explicit version may be routine, but that does not defeat the anchor under the stated standard: a well-posed continuous question remains worthwhile even if its answer is an LP. Theorem 19 survives, especially in the implicit-type setting where pricing becomes the real question.
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.