| paper | d4-conf-atal-2017-0196 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: Exactly solvable in deterministic polynomial time, returning an allocation with \(T(x)=T^*\) and zero failure probability. · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given candidates \(C=\{p,c_1,\ldots,c_m\}\), rational nonmanipulator masses \(\mu_\pi\) on \(\tau\) rankings summing to \(1-\alpha\), and a coordinated bloc of mass \(\alpha\), compute the minimum possible maximum final Borda score among candidates \(c\ne p\). Each unit of bloc mass must report a complete ranking with \(p\) first. Also determine whether the minimum is at most \(b_p+m\alpha\), where \(b_p\) is the nonmanipulators’ Borda score mass for \(p\).
Represent the nonmanipulators by ranking types with masses \(\mu_\pi\), and the bloc’s reports by masses \(x_r\) over complete \(p\)-first rankings, with \(\sum_r x_r=\alpha\). Minimize \(\max_{c\ne p}\left(b_c+\sum_r x_r B_r(c)\right)\), where \(b_c=\sum_\pi\mu_\pi B_\pi(c)\) and \(B_r(c)\) is \(c\)’s Borda score under report \(r\).
The opponent’s strongest point is that dropping integrality from the paper’s initial IP yields the exact continuous feasible set, with Birkhoff decomposition turning it into mixtures of complete rankings. The proponent acknowledges that the finite-count error guarantee does not transfer, but does not address how little new LP machinery the mirror requires.
fatal: False
The mirror covers Theorem 1’s min-max objective and gives an exact algorithm for its mass version. It does not transfer Theorem 1’s finite-count \(O(k\sqrt{m\log m})\) guarantee, or resolve Claim 2’s lower bound for reverse.
My lead anchor is Theorem 1, proved in this paper. For Borda-UCM, let \(T^*=\min_S\max_{c\ne p}s(c)\): the least possible final score of the highest-scoring opponent, over all strategies for the \(k\) manipulators. The theorem gives a randomized Monte Carlo algorithm with an additive \(O(k\sqrt{m\log m})\) approximation to \(T^*\), with exponentially small failure probability. In particular, if some strategy lets \(p\) win by a margin of \(\Omega(k\sqrt{m\log m})\), the algorithm finds a winning strategy, possibly with a smaller margin. The paper’s introduction also reports that exact finite Borda-UCM is NP-hard, citing [4] and [7]; that is useful context, but it is not a numbered hardness result established here.
A plausible high-multiplicity regime is a large election with a coordinated bloc whose members share the same full preference ranking, with target \(p\) at the top, and can choose their reported ballots together. The rest of the electorate has a distribution over \(\tau\) recurring ranking types, with \(\tau\) small relative to the population. This is a population of many agents, not fractional ballots: every unit of mass receives a complete Borda ranking. The fractional quantities describe how much of the bloc uses each report.
The continuous problem I would hand to a prover is Continuous Borda Coalition Score Minimization (CBCSM). Let \(C=\{p,c_1,\ldots,c_m\}\), and normalize the total population mass to \(1\). The nonmanipulators have rational masses \(\mu_\pi\) on \(\tau\) rankings, summing to \(1-\alpha\); the coordinated bloc has mass \(\alpha\). For a ranking \(\pi\), write \(B_\pi(c)=m-\operatorname{pos}_\pi(c)\), using positions \(0,\ldots,m\), and let \(b_c=\sum_\pi\mu_\pi B_\pi(c)\) be the nonmanipulators’ score mass for \(c\). Let \(R_p\) be the complete rankings placing \(p\) first. Choose report masses \(x_r\ge 0\), one for each \(r\in R_p\), with \(\sum_r x_r=\alpha\). The question is to find \(x\) minimizing \(\max_{c\ne p}\bigl(b_c+\sum_{r\in R_p}x_rB_r(c)\bigr)\). A solution is a finite list of reports and their masses; \(p\) wins exactly when this minimum is at most \(b_p+m\alpha\), allowing ties.
This is the same min-max score objective as \(T^*\), with voter counts replaced by population proportions. Its expected classification is Class A, tractable. The problem is an LP with \(m!\) possible report columns. In the dual, pricing asks for a \(p\)-first ranking maximizing a weighted sum of Borda scores. For Borda, that is solved by sorting the remaining candidates by their dual weights, so the exponential set of columns has efficient separation. With rational input, this gives an exact polynomial-time LP algorithm in \(m,\tau,L\). This is a question the authors should recognize: it preserves the target, the Borda rule, the coalition’s strategic reports, and the objective they explicitly optimize. Their configuration-LP and separation-oracle approach is also closely aligned with the solution method.
The finite-to-continuous dictionary is direct. For \(N=n+k\), a finite instance has \(\alpha=k/N\), and feasible report masses are restricted to multiples of \(1/N\). CBCSM removes that count grid while retaining complete rankings and the fixed coalition mass. Its basic LP solutions need only \(O(m)\) reports, which also gives a route back to finite elections: rounding their masses to \(k\) report counts incurs at most \(O(m^2)\) raw score error, so for fixed \(m\) the per-capita discrepancy vanishes as \(N\) grows. A useful next question is how sharp that transfer is across growing \(m\) and \(k\), and how it compares with Theorem 1’s bound.
The soft spot is that Theorem 1’s main technical achievement handles finite-count rounding, while CBCSM allows divisible report mass. The paper’s \(O(k\sqrt{m\log m})\) guarantee, normalized by \(N\), becomes \(O(\alpha\sqrt{m\log m})\); it need not shrink as the population grows at fixed \(\alpha\) and \(m\). So the theorem’s quantitative guarantee does not carry over unchanged. The mirror still has a strong case because the underlying manipulation objective is intact, and population granularity is precisely the feature being continuized.
Theorem 1 is a genuine computational result, and a large coordinated bloc is a plausible high-multiplicity regime. So I would not argue that the paper lacks an anchor or that the population interpretation is nonsensical. My strongest case against is narrower: the proposed continuous question is already represented by the paper’s own LP relaxation.
Let \(x_{i,j}\) be the mass of manipulators who give opponent \(c_i\) Borda score \(j\). A continuous bloc of mass \(\alpha\) assigning every unit a complete ranking must satisfy
\[
\sum_i x_{i,j}=\alpha\quad\text{for each }j,
\qquad
\sum_j x_{i,j}=\alpha\quad\text{for each }i,
\qquad
x_{i,j}\ge 0.
\]
These are the scaled doubly stochastic constraints. By the Birkhoff–von Neumann theorem, every such matrix decomposes into a mixture of permutation matrices, each corresponding to a complete ranking with \(p\) first. Thus the exact continuous problem is the LP
\[
\min T
\quad\text{such that}\quad
\sigma_i+\sum_j jx_{i,j}\le T\quad\text{for every opponent }i,
\]
together with those mass constraints. It has polynomially many variables and constraints, and its solution can be turned into a finite mixture of full rankings.
That is precisely the paper’s initial integer program with its integrality requirement dropped. The authors set that relaxation aside because it does not necessarily yield \(k\) indivisible manipulators’ votes. In the continuous model, that limitation disappears: a mixture of full rankings is exactly the allowed report for divisible mass. The continuous version is therefore not just suggested by the paper’s method; its exact feasible set is already written down there, and its objective is a standard LP. The configuration LP and randomized rounding address the additional finite-count constraint.
Adding more nonmanipulator preference types does not make this mirror richer: for this objective, their rankings affect the problem only through the aggregate Borda scores \(\sigma_i\). A more complex continuous problem would need extra features such as type-specific report restrictions or costs, which would change the manipulation problem rather than strengthen this mirror.
So I can defeat the proposed anchor as a *new computational question*: the continuous analogue is already implicit in the paper’s relaxation. The negative case remains limited, though. The population interpretation could still be useful, and the paper does not present it as a continuous society. If that formalization itself counts as worthwhile programme work, I cannot rule it out; the case against rests on the lack of a new computational problem, not on a fundamental failure of the model.
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.