| paper | d4-conf-aaai-2018-0973 |
| 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: Polynomial-time solvable exactly: a deterministic algorithm outputs a feasible rational plan of cost \(K\) in \(\operatorname{poly}(m,\tau,L)\) time, with 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\), a qualifying scoring vector \(\alpha\), a target \(p\), and a rational distribution \(\mu\) supported on \(\tau\) rankings, compute a minimum-mass bribery plan \(x_{t,\pi}\ge 0\) that moves mass from each initial ranking \(t\) to a new ranking \(\pi\ne t\). Require \(\sum_{\pi\ne t}x_{t,\pi}\le\mu_t\) for each \(t\), and require \(p\) to be a co-winner under the resulting distribution.
A society is a distribution \(\mu\) over ranking types. The decision variables \(x_{t,\pi}\) specify mass transferred from type \(t\) to ranking \(\pi\); minimize \(\sum_{t,\pi\ne t}x_{t,\pi}\) subject to type-mass limits and the linear scoring inequalities that make \(p\) a co-winner. The objective and constraints give an LP with pricing over possible output rankings.
The mirror covers minimum-cost bribery for constant and non-concentrated scoring rules, including the stated Borda, \(t\)-approval, plurality, and veto cases. It leaves the UCM approximation results and their margin-minimization objectives aside.
The best lead is Theorem 1, proved in this paper. It says that for \(R_\alpha\)-Bribery under a constant scoring rule (\(\alpha_m=O(1)\)) or a non-concentrated one (\(\bar\alpha\le(1-\epsilon)\alpha_m\) for constant \(\epsilon>0\)), if the minimum number of voters to bribe is \(k\), a randomized polynomial-time algorithm finds a successful strategy using at most \(k+\widetilde O(\sqrt{k})\) voters, with exponentially small failure probability. I use this one anchor because it is the paper’s direct bribery result. The paper’s own numbered results do not give a hardness anchor; the hardness claims in its related work are cited from elsewhere.
A natural regime is a large electorate—say, millions of voters—with relatively few distinct complete rankings. A type is a ranking \(t\), and \(\mu_t\) is the fraction of the electorate holding it. Since the paper gives every voter the same unit bribe cost and uses no other voter-specific information, ranking is a complete type for this model. This matches the paper’s campaign-targeting motivation: the decision concerns what share of each group to persuade.
I would ask a prover to study Unit-Cost \(R_\alpha\)-Bribery\(_\infty\). Given candidates \(C\), a scoring vector \(\alpha\), a target \(p\), and a rational distribution \(\mu\) supported on \(\tau\) rankings \(T\), find the least mass whose ballots must change so that \(p\) is a co-winner. A solution is a mass-transfer plan \(x_{t,\pi}\ge0\), where \(x_{t,\pi}\) is the mass moved from an initial ranking \(t\) to a new ranking \(\pi\ne t\). Its exact optimization problem is
\[ \begin{aligned} \min \quad & \sum_{t\in T}\sum_{\pi\ne t}x_{t,\pi}\\ \text{subject to}\quad &\sum_{\pi\ne t}x_{t,\pi}\le \mu_t &&\forall t\in T,\\ &\sum_{t\in T}\mu_t s_\alpha(t,p) +\sum_{t\in T}\sum_{\pi\ne t}x_{t,\pi} \bigl(s_\alpha(\pi,p)-s_\alpha(t,p)\bigr)\\ &\qquad\ge \sum_{t\in T}\mu_t s_\alpha(t,c) +\sum_{t\in T}\sum_{\pi\ne t}x_{t,\pi} \bigl(s_\alpha(\pi,c)-s_\alpha(t,c)\bigr) &&\forall c\ne p. \end{aligned} \]
This asks for the minimum fraction of society to bribe and a plan attaining it. It preserves the paper’s candidates, ballots, scoring rule, target, co-winner condition, and objective; the decision to bribe a voter becomes a decision about how much mass to move.
I expect this mirror to be tractable. The formulation is a linear program with exponentially many possible output rankings, but its pricing step optimizes a linear score over rankings. That is a linear assignment problem: each candidate is assigned a position, with weight determined by its dual score coefficient and the score for that position. Assignment is polynomial-time solvable, so separation and the ellipsoid method give an exact algorithm polynomial in \(m,\tau,L\). The programme’s existing Score-\(\$Bribery_\infty\) result—polynomial time for every scoring protocol—appears to settle this unit-cost special case already. That is supporting evidence that the high-multiplicity version is a sensible problem; it also means this mirror’s tractability should be recorded as known within ChoCo, rather than presented as a new result.
For a finite election with \(n\) voters, an integer bribery plan becomes a feasible mass-transfer plan after dividing its counts by \(n\). Thus the continuous optimum is a lower bound on the discrete optimum normalized by \(n\). Theorem 1’s additive count error becomes \(\widetilde O(\sqrt{k})/n\) in mass, which is \(\widetilde O(n^{-1/2})\) when \(k\) grows proportionally to \(n\). Further questions include bounding the gap between the continuous optimum and the best integer plan, and identifying which type-dependent bribe costs keep the pricing step tractable.
The weakest point is that Theorem 1 addresses indivisible named voters and its stated polynomial runtime is for an explicit election; it does not establish a compact-support algorithm for rational masses. The continuous problem also permits fractional bribes that a finite election cannot carry out exactly, especially at a tie boundary. The mirror remains plausible because those are precisely the population and integrality choices the continuization programme studies, while the underlying bribery objective and winner condition remain intact.
The strongest case against Theorem 1 is that its guarantee measures a finite electorate’s indivisibility: voters must be bribed one at a time, and the additive \(\widetilde O(\sqrt{k})\) term is the rounding loss. In a continuous mirror, the natural decision is how much mass of each ranking to move. That is a different optimization problem from the theorem’s approximation problem.
But that distinction does not defeat the anchor under ChoCo’s scope. The continuous question—minimum mass to move so that \(p\) wins—is well posed, and the fact that its answer might be easier or its approximation error might vanish is exactly the kind of change continuization is meant to expose. Nor does the normalized cost necessarily vanish: with a macroscopic score deficit, a positive fraction of the electorate may need to change ballots.
The other grounds do not hold here. Theorem 1 is a named computational result. In its unit-cost model, a ranking captures everything relevant about a voter, so a large electorate with repeated rankings is a natural high-multiplicity regime. Scores aggregate across voters, and the objective does not depend on who is bribed. A continuous formulation over ranking types and replacement ballots is coherent; its exponentially many possible ballots make pricing part of the computational question, not a reason to dismiss it. The programme’s existing continuous bribery result is relevant prior knowledge, but the stated rules say that a known answer does not make a well-posed mirror unworthy.
So the honest case against is weak. I cannot defeat this anchor: the paper has a direct, plausible population mirror, and the continuum’s likely removal of voter-level rounding is not a valid objection under the brief.
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.