How Hard is Safe Bribery?

NEW RESULT — discrete: hard → continuous: polynomial-time · adversarial review: proved

The anchor (named result in the paper)

statement extracted from the paper’s text layer; consult the paper for the exact wording

The continuous mirror question, as graded

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$.

Packaged proof task (what the prover saw — nothing else)

Definitions. Let $r$ be Borda with the given tie-breaking order. A society is an explicitly supported rational distribution $\mu$ over complete rankings of $C$. For a coupling $y$, define $\mu^y(v)=\mu(v)-\sum_u y_{v,u}+\sum_t y_{t,v}$. Let $w=r(\mu)$, and write $a\succeq_B b$ when $a=b$ or $a\succ_B b$.

Given $c$, $\succ_B$, and a rational coupling $x\geq0$ with $\sum_u x_{t,u}\leq\mu(t)$, decide whether $r(\mu^x)=c$ and $r(\mu^y)\succeq_B w$ for every $y$ satisfying $0\leq y_{t,u}\leq x_{t,u}$.

Target. Is this distributional Borda $\$Bribery Is Safe$ problem in $\mathrm P$, or is it NP-hard?

Nearest known results. For finite unweighted preference profiles, Borda $\$Bribery Is Safe$ is co-NP-complete.

Prover output (gpt-5.6-sol / xhigh, Bolzano prover prompt)

Classification

Theorem

Under the standard explicit encoding of the nonzero entries of the coupling $x$, distributional Borda $\$Bribery Is Safe$ is polynomial-time solvable. Consequently, it is not NP-hard unless $\mathrm P=\mathrm{NP}$.

Affine representation of Borda scores

Let $m=|C|$. For a ranking $v$, let $b_a(v)\in\{0,\ldots,m-1\}$ denote the Borda score assigned to candidate $a$.

For any distribution $z$, define the total score of $a$ by

$\operatorname{sc}_a(z)=\sum_v z(v)b_a(v)$.

Let $E=\{(t,u):x_{t,u}>0\}$. Entries outside $E$ can be discarded because every admissible $y$ satisfies $y_{t,u}=0$ there.

For every admissible $y$,

$\operatorname{sc}_a(\mu^y)=\operatorname{sc}_a(\mu)+\sum_{(t,u)\in E}y_{t,u}\bigl(b_a(u)-b_a(t)\bigr)$.

Indeed, substituting the definition of $\mu^y$ and relabelling the incoming terms gives

$\sum_v b_a(v)\mu^y(v)=\sum_v b_a(v)\mu(v)-\sum_{v,u}b_a(v)y_{v,u}+\sum_{t,v}b_a(v)y_{t,v}$,

which is exactly the claimed formula.

Every admissible $y$ also defines a valid distribution. For each ranking $v$,

$\mu^y(v)\geq\mu(v)-\sum_u y_{v,u}\geq\mu(v)-\sum_u x_{v,u}\geq0$,

and the total outgoing and incoming masses cancel, so $\sum_v\mu^y(v)=\sum_v\mu(v)=1$.

Thus every candidate score is an affine rational function of the variables $y_{t,u}$.

Encoding the tie-breaking rule

Write $a\triangleright d$ if the given tie-breaking order selects $a$ ahead of $d$. Fix a candidate $d$, and define

$H_d=\{a\in C\setminus\{d\}:a\triangleright d\}$

and

$L_d=C\setminus(H_d\cup\{d\})$.

Candidate $d$ is the Borda winner at a distribution $z$ if and only if both of the following hold:

$\operatorname{sc}_d(z)>\operatorname{sc}_a(z)$ for every $a\in H_d$;

$\operatorname{sc}_d(z)\geq\operatorname{sc}_a(z)$ for every $a\in L_d$.

The strict inequalities are necessary precisely for candidates that defeat $d$ under a score tie.

Linear program for attaining a fixed winner

For each $d\in C$, consider the rational linear program with variables $y_{t,u}$, for $(t,u)\in E$, and one additional variable $\delta$:

$0\leq y_{t,u}\leq x_{t,u}$ for every $(t,u)\in E$;

$0\leq\delta\leq1$;

$\operatorname{sc}_d(\mu^y)-\operatorname{sc}_a(\mu^y)\geq\delta$ for every $a\in H_d$;

$\operatorname{sc}_d(\mu^y)-\operatorname{sc}_a(\mu^y)\geq0$ for every $a\in L_d$.

The objective is to maximize $\delta$. Denote the optimum by $\delta_d^\star$, treating an infeasible program separately.

Lemma

There exists an admissible coupling $y$ such that $r(\mu^y)=d$ if and only if the program for $d$ is feasible and $\delta_d^\star>0$.

Proof

Suppose first that $r(\mu^y)=d$. If $H_d\neq\varnothing$, every difference

$\operatorname{sc}_d(\mu^y)-\operatorname{sc}_a(\mu^y)$, for $a\in H_d$,

is strictly positive. Hence their finite minimum is positive, and choosing $\delta$ to be the smaller of this minimum and $1$ gives a feasible solution with $\delta>0$.

If $H_d=\varnothing$, the winner condition consists only of the weak inequalities indexed by $L_d$. The same $y$, together with $\delta=1$, is feasible. Thus $\delta_d^\star>0$.

Conversely, suppose that the program has a feasible solution with $\delta>0$. Then $d$ strictly outscores every candidate in $H_d$ and weakly outscores every candidate in $L_d$. By the characterization of the tie-breaking rule, $r(\mu^y)=d$. This proves the equivalence.

Because all coefficients are rational, the equivalence is unchanged if couplings are required to be rational: whenever the optimum is positive, rational linear programming has a rational optimal solution.

Algorithm

Compute $w=r(\mu)$ using exact rational arithmetic.

Compute $r(\mu^x)$. If $r(\mu^x)\neq c$, reject.

Form the set of unacceptable winners

$D=\{d\in C:d\not\succeq_B w\}$.

For every $d\in D$, solve the linear program above exactly. If some program is feasible with $\delta_d^\star>0$, reject.

If no such candidate exists, accept.

Correctness

If the algorithm accepts, then $r(\mu^x)=c$. Suppose safety nevertheless failed. Then there would exist an admissible $y$ whose winner $d=r(\mu^y)$ satisfies $d\not\succeq_B w$. Hence $d\in D$, and the lemma would give $\delta_d^\star>0$, causing the algorithm to reject. This is a contradiction.

Conversely, if the algorithm rejects during the linear-programming stage, then for some $d\in D$ there is an admissible $y$ with $r(\mu^y)=d$. Since $d\not\succeq_B w$, this $y$ witnesses that the plan is unsafe. Rejection at the first stage is exactly the failure of $r(\mu^x)=c$.

Therefore the algorithm accepts exactly the instances satisfying both conditions in the question.

Running time

Let $q=|E|$. Each linear program has $q+1$ variables and $O(q+m)$ rational inequalities. Its coefficients have polynomial encoding length: Borda-score changes lie between $-(m-1)$ and $m-1$, and all remaining coefficients come from the explicitly encoded rational input.

Exact rational linear programming is solvable in time polynomial in the number of variables, the number of constraints, and their encoding length. The algorithm solves at most $m$ such programs. Its total running time is therefore polynomial in the input length.

The contrast with the finite-profile co-NP-completeness result is explained by divisibility: discrete partial adherence selects whole voters and produces binary variables, whereas the distributional model allows every planned mass $x_{t,u}$ to be split continuously, leaving a rational polytope and affine Borda scores.

⟨structured verdict parsed — rendered above⟩

Adversarial review (gpt-5.6-sol / high, Bolzano verifier prompt)

Verification Report

Summary

The prover correctly classifies the distributional problem as polynomial-time solvable under an explicit rational encoding of the support of $x$. The argument converts the possible partial couplings into a rational polytope, expresses Borda scores affinely, and uses polynomially many linear programs to determine whether an unacceptable candidate can become the winner.

No substantive mathematical gaps or false statements were found.

Step-by-step audit

1. Affine Borda-score formula

The identity

\[ \operatorname{sc}_a(\mu^y) = \operatorname{sc}_a(\mu) + \sum_{(t,u)\in E}y_{t,u}\bigl(b_a(u)-b_a(t)\bigr) \]

follows correctly by expanding the outgoing and incoming mass terms. Discarding pairs outside $E$ is justified because $0\leq y_{t,u}\leq x_{t,u}=0$ forces $y_{t,u}=0$.

The proof that $\mu^y$ remains a distribution is also correct:

Nonnegativity follows from the row-capacity constraint on $x$.
Total mass remains $1$ because total outgoing mass equals total incoming mass.

No additional conservation constraint on $y$ is required by the definition given in the task.

2. Tie-breaking characterization

The sets $H_d$ and $L_d$ are defined consistently with the fixed tie-breaking order. Candidate $d$ wins exactly when it:

strictly outscores every candidate that would defeat it in a tie;
weakly outscores every candidate that it would defeat in a tie.

This is the correct characterization of a deterministic tie-broken Borda winner.

3. Linear-program formulation

The LP correctly represents all admissible partial couplings through the box constraints $0\leq y_{t,u}\leq x_{t,u}$.

The auxiliary variable $\delta$ correctly handles the strict score inequalities. Because $H_d$ is finite, if $d$ wins, the minimum positive score margin over $H_d$ is positive. Conversely, any feasible solution with $\delta>0$ satisfies all required strict inequalities.

The special case $H_d=\varnothing$ is explicitly and correctly handled by taking $\delta=1$.

Thus the stated equivalence between attainability of winner $d$ and $\delta_d^\star>0$ is valid.

4. Rationality

The feasible region and objective have rational coefficients and are bounded in $\delta$. Therefore a positive rational optimum has a rational optimal solution. This adequately covers either interpretation in which admissible couplings are rational or real.

5. Algorithmic correctness

The unacceptable-winner set

\[ D=\{d\in C:d\not\succeq_B w\} \]

matches the safety condition exactly. Testing whether any $d\in D$ is attainable is sufficient because every admissible $y$ has exactly one tie-broken Borda winner.

Both rejection cases are correct:

rejection in the first stage detects failure of $r(\mu^x)=c$;
rejection from an LP supplies an admissible coupling whose winner is worse than $w$.

The acceptance argument correctly proves the universal safety condition.

6. Complexity

With $q=|E|$, each LP has $q+1$ variables and $O(q+m)$ constraints. All coefficients have polynomial bit length in the explicitly encoded rational input. Solving at most $m$ rational linear programs is polynomial in the total input length.

The qualification concerning explicit encoding is appropriate for the supplied input model.

Verdict

The proof fully resolves the target. Its explanation of the distinction from the discrete finite-profile result is informal but accurate and is not needed for correctness.