| paper | How Hard is Safe Bribery? |
| authors | — |
| venue | AAMAS 2022 |
| filed under | voting · bribery-control |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c22r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 3.10
statement extracted from the paper’s text layer
Given candidates \(C\), an explicitly supported rational distribution \(\mu\) over complete ranking types, target \(c\), briber order \(\succ_B\), tie-breaking order, and a proposed mass coupling \(x_{t,u}\) with \(x_{t,u}\ge0\) and \(\sum_u x_{t,u}\le\mu_t\), decide whether \(c\) wins after full adherence and, for every partial coupling \(y\) satisfying \(0\le y_{t,u}\le x_{t,u}\), every winner of the induced society \(\mu^y\) is at least as preferred as \(w=r(\mu)\) under \(\succ_B\).
Types are complete rankings, \(\mu\) gives their rational masses, \(x\) is a proposed recommendation coupling, and \(y\) records partial adherence. The Boolean objective is robust safety recognition; under Borda, scores are affine in \(\mu^y\), so an unsafe realization for each bad candidate is tested by linear feasibility under explicit support.
The LP tractability is conditional on explicitly represented type and recommendation support; it remains open whether the mirror is efficient when the ranking space of size \(m!\) is represented implicitly.
fatal: False
Covers the fixed-plan safety-recognition results for Borda, \(k\)-approval, and Borda shift bribery corresponding to Theorems 3.10, 3.9, and 3.11; it leaves budgeted safe-plan design, tournament-rule results, and parameterized results untreated.
The strongest positive case is a genuine Class A mirror of the paper’s safety-recognition results, with Theorem 3.10 as my lead. The paper proves three relevant hardness results itself: Theorem 3.9, Theorem 3.10, and Theorem 3.11. All are coNP-completeness theorems, so they directly test whether discrete hardness dissolves when voter multiplicity becomes divisible.
The natural population regime is a large election with many voters in a small number of stable blocs. A type consists of a complete ranking together with all intrinsic parameters relevant to bribery: susceptibility, price, and any other cost data. A national or platform-scale electorate may contain millions of voters but only tens or hundreds of such preference-cost types. This is not a claim that every election is high-multiplicity; it is a plausible campaigning regime, and the paper’s own campaigning interpretation makes it recognizable to its authors.
Let \(C\) be the candidates and \(T\) a finite set of ranking types. The society is a rational distribution \(\mu\in\mathbb{Q}_{\ge 0}^{T}\) with \(\sum_t\mu_t=1\). A proposed bribery plan is a mass coupling \(x=(x_{t,u})\), where \(x_{t,u}\) is the mass originally of type \(t\) that is recommended to change to ranking \(u\), with \(\sum_u x_{t,u}\le \mu_t\). Its fully executed profile is
\[ \mu^x_v=\mu_v-\sum_u x_{v,u}+\sum_t x_{t,v}. \]
The continuum version of the paper’s arbitrary subset of bribed voters is exactly a partial-adherence vector \(y\) satisfying \(0\le y_{t,u}\le x_{t,u}\). The resulting society is \(\mu^y\). Thus any measurable submass of a bribed cohort may follow the recommendation, while the rest retains its original vote.
Let \(w=r(\mu)\) be the original winner, let \(\succ_B\) be the briber’s preference, and call a candidate good if it is at least as preferred as \(w\). The continuous safety-recognition problem asks whether
Because the source results are “Is Safe” results, the objective here is Boolean recognition: decide whether a proposed plan is safe. A natural optimization companion would minimize \(\sum_{t,u}p_{t,u}x_{t,u}\) subject to the same conditions, but I do not claim that the paper already establishes that optimization problem.
My lead is the following.
Borda-Safe-\(\infty\). Given \(C\), a rational type distribution \(\mu\), a proposed mass coupling \(x\), a briber preference \(\succ_B\), a target \(c\), and a fixed tie-breaking order, decide whether \(c\) wins under full adherence and every partial-adherence society \(\mu^y\) has a winner at least as preferred as the original winner \(w\).
This is a faithful continuization of the problem in Theorem 3.10, which the paper proves here: for Borda, \(\$Bribery\) Is Safe is coNP-complete. It retains the original candidates, complete rankings, Borda rule, original winner, briber preference, target, and the exact success-versus-safety distinction. The only change is replacing a finite subset of named voters by a measurable submass of a type cohort.
I expect Borda-Safe-\(\infty\) to be in Class A, at least when the type and recommendation support are explicit. For every candidate \(a\), the Borda score \(S_a(\mu^y)\) is affine in \(y\). To test whether a bad candidate \(b\) can win, introduce variables \(y_{t,u}\), impose \(0\le y_{t,u}\le x_{t,u}\), and impose the linear inequalities expressing that \(b\) wins under the fixed tie-breaking order. This is a rational linear-feasibility problem. Solving one such LP for each bad candidate decides safety.
The exact-cover combinatorics in the paper’s reduction are precisely what should disappear: an integral subset of bribed voters becomes a fractional mass allocation. “Choose \(t\) sets whose incidence covers every element” becomes a linear mass-balancing question. The continuum is therefore doing substantive work, rather than merely renaming \(n\) voters as percentages. The remaining questions are whether the minimum-cost safe-plan problem is also tractable, how much can be gained when the ranking space is represented implicitly rather than by explicit types, and what finite-\(n\) approximation guarantees follow from the continuum solution.
A second, independently useful mirror is \(k\)-Approval-Safe-\(\infty\). Its input and safety question are identical, with \(r\) replaced by \(k\)-approval for fixed \(k\ge 3\). This is the direct population version of Theorem 3.9, proved in the paper: for every constant \(k\ge3\), \(\$Bribery\) Is Safe is coNP-complete.
I again expect Class A. A candidate’s \(k\)-approval score is linear in the population masses: it is simply the mass of voters placing that candidate in their top \(k\) positions. For each bad candidate \(b\), the existence of a partial adherence state in which \(b\) wins is an LP over the box \(0\le y\le x\). The reduction in Theorem 3.9 relies on selecting whole bribed voters corresponding to sets in an exact cover. In the continuum, those voters become divisible mass, so the exact-cover obstruction becomes a fractional-cover feasibility problem. This mirror is especially persuasive because the source hardness is not an artefact of complicated Borda scores; it is the integrality of the population perturbation that is being relaxed.
The third mirror preserves the paper’s more specific shift action.
Borda-Shift-Safe-\(\infty\). Let \(t\) be an original ranking and let \(j\) denote a requested shift of \(c\) by \(j\) positions. The action variable is \(x_{t,j}\), the mass of type \(t\) instructed to shift by \(j\), with \(\sum_jx_{t,j}=\mu_t\). Under partial adherence, that mass may shift by any \(q\in\{0,\ldots,j\}\). Thus a realization is a collection \(z_{t,j,q}\ge0\) satisfying \(\sum_{q=0}^{j}z_{t,j,q}=x_{t,j}\). Full adherence puts all \(x_{t,j}\) at \(q=j\); partial adherence may distribute it among smaller shifts. The question is whether full adherence makes \(c\) win and every such partial realization leaves only good winners.
This is a direct continuous analogue of Theorem 3.11, proved here: for Borda, Shift Bribery Is Safe is coNP-complete. It is not a generic redefinition of bribery, since the only permitted action remains shifting the briber’s candidate leftward. For each \(t,j,q\), the resulting ranking is fixed, so every candidate’s Borda score is affine in \(z\). Again, an unsafe realization for a specified bad candidate is found by LP. The expected classification is therefore Class A for explicit type and shift support.
This third mirror generates a useful boundary question: does the tractability survive when the briber must choose \(x\) under type-dependent shift prices \(\pi_t(j)\), rather than merely check a proposed shift plan? It also asks whether the same phenomenon holds for other scoring rules and where non-linear rules such as Copeland or maximin cease to admit this LP formulation.
The bridge to the discrete problems is exact in the intended high-multiplicity sense. A rational \(\mu\) can be expanded into a finite election by clearing denominators. Every finite subset of bribed voters gives a valid continuum partial-adherence state, while every rational continuum witness can be realized after sufficiently many replications. The continuum is stricter than one particular finite denominator because it admits every mass fraction, but it is the natural limit of repeated electorates. No outcome is fractional: candidates remain discrete, rankings remain complete, and only the population is continuized.
The weakest point is that this case covers the paper’s fixed-plan recognition problems, not automatically the budgeted search problems \(Safe\ \$Bribery\) and \(Safe\ Shift Bribery\). A referee could reasonably say that choosing a safe plan may retain non-convex robust-design difficulty even though checking a given plan is an LP. There is also a representation issue when all \(m!\) rankings are implicit. Those are real limitations. They do not invalidate the mirror: the paper explicitly studies the recognition variants, and its coNP-hardness is exactly what the continuous population turns into a finite family of linear feasibility checks. I would therefore claim a strong Class A mirror for Theorems 3.9–3.11, while making no claim here about Theorems 3.13–3.15 or the full cost-minimization problems.
The strongest negative case is that all three anchors reduce to the same generic observation: once a bribery plan is fixed, partial adherence under an additive scoring rule is a linear feasibility problem. That is a valid relaxation, but it is not yet a substantial mirror of the paper’s safe-bribery programme.
For Theorem 3.10, the exact-cover reduction encodes each set \(S_i\) as a different bribed voter with a different ranking. In a genuinely compressed high-multiplicity society, one would want many voters sharing a small number of complete types. If the set voters remain distinct, then the number of types grows with the reduction and the continuum is mainly fractionalizing individually encoded choices. If they are merged into a small number of types, the set-incidence information that drives the theorem disappears. The proposed Borda LP is therefore a relaxation of the reduction, but not obviously a population-level version of the phenomenon the theorem studies.
The better formulation would be continuous Safe \(\$\)Bribery itself: choose a mass transfer under type-dependent costs, requiring the fully executed society to elect \(c\) while every partial execution remains safe. The proponent’s LP only checks a previously chosen plan. Once the plan is also a decision variable, safety is a robust condition over all \(y\) with \(0\le y\le x\); it is not automatically one LP. Thus the proposed result does not yet cover the paper’s central search problem.
The same objection applies even more plainly to Theorem 3.9. For \(k\)-approval, the proposed safety test is simply a linear scan over top-\(k\) mass followed by LP feasibility. Nothing in it is specific to the coNP-complete theorem: the same argument applies to every scoring rule whose scores are affine in the population. The exact-cover obstruction has been removed by allowing the encoded voters to divide their mass. That may be an interesting relaxation, but without a costed design problem, rounding theorem, or implicit-type algorithm, it is close to a generic fractional verifier rather than a distinctive continuous safe-bribery result.
Theorem 3.11 adds no independent rescue. The variables \(z_{t,j,q}\) merely expand the same construction by recording how much mass performs each permitted partial shift. For Borda, all scores remain affine, so the argument is again the same LP. A stronger shift-bribery mirror would choose the shifts under prices and a budget, but that is precisely the robust optimization problem the proponent leaves open. The paper’s parameterized results also have no continuous counterpart in the proposed case.
These objections are not decisive under ChoCo’s rules. Replicating every set voter many times does produce a legitimate high-multiplicity instance, and a nonatomic population really does permit an arbitrary fraction of each repeated type to comply. The resulting LP is not merely a change from headcounts to percentages; it changes the integral subset quantifier into a mass quantifier. Nor can one object that the continuous answer is easy: a discrete coNP-complete recognition problem becoming an LP is exactly the sort of Class A phenomenon the programme seeks.
Consequently, I cannot honestly sustain the universal negative claim. The first anchor, Theorem 3.10, survives: it gives a faithful, computational, population-based question whose continuous version is plausibly tractable. The other two reinforce the same point. The fair negative conclusion is only that the proposed case overstates the result’s scope and novelty until it addresses costed safe-plan design and representation of large ranking spaces. It does not show that no worthwhile continuous mirror exists.
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.