Answer: \(\mathrm{NP}\text{-hard}\)
Theorem 5 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateBribery(Kemeny) is Σp 2-complete. More- over, hardness holds even when the input is restricted to unidimensionally aligned profiles and where |L| = 1.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given an agenda Φ, integrity constraint Γ, desired conclusions L, and a rational distribution μ over complete, Γ-consistent judgment sets, find the minimum total mass to transfer from types J to reports K ≠ J, subject to ∑ₖ xᵢₖ ≤ μᵢ for each J, such that every Kemeny winner under the resulting distribution ν contains L. Here Kemeny winners minimize ∑ᵢ νᵢ d(J, J⁺) over complete, Γ-consistent judgment sets J⁺.
Let \(\Phi=\{\varphi_1,\neg\varphi_1,\ldots,\varphi_m,\neg\varphi_m\}\) be a nonempty propositional agenda closed under complementation, with double negations identified, and let \(\Gamma\) be a propositional integrity constraint; auxiliary variables outside the agenda are allowed.
Let \(\mathcal J\) comprise the complete judgment sets choosing exactly one formula from each complementary pair whose conjunction with \(\Gamma\) is satisfiable. Input also includes desired conclusions \(\mathcal L\subseteq\Phi\).
A society is given by its support: the list of the \(\tau\) distinct types \(J_i\in\mathcal J\) with positive masses \(\mu_i\), each a binary rational, with \(\sum_i\mu_i=1\). Here \(\tau\) is the support size, not the number of possible types.
A transfer chooses real amounts \(x_{iK}\geq0\) for every \(K\in\mathcal J\setminus\{J_i\}\), subject to \(\sum_{K\ne J_i}x_{iK}\leq\mu_i\). Any feasible report is allowed, including reports outside the input support; transferred mass costs one per unit.
The resulting mass of \(K\in\mathcal J\) is \(\nu_K=\sum_{i:J_i=K}(\mu_i-\sum_{H\ne J_i}x_{iH})+\sum_{i:J_i\ne K}x_{iK}\), and total cost is \(c(x)=\sum_i\sum_{K\ne J_i}x_{iK}\).
Kemeny winners are all members of \(\operatorname*{arg\,min}_{A\in\mathcal J}\sum_{K\in\mathcal J}\nu_Kd(K,A)\), where \(d\) is Hamming distance on the \(m\) issues, counting each complementary pair once. Success requires every winner to contain \(\mathcal L\); no tie-breaking is applied.
Given a binary rational budget \(b\in[0,1]\), decide whether a successful transfer with \(c(x)\leq b\) exists. This asks for an attained feasible cost, rather than comparing an infimum with the budget. Let \(L\) be the total input bit length; state running times in \(m,\tau,L\).
Is this continuous Kemeny bribery decision problem in \(\mathrm P\), or is it \(\mathrm{NP}\)-hard?
Discrete unit-cost bribery requiring every Kemeny winner to contain the desired conclusions is \(\Sigma_2^p\)-complete, even for unidimensionally aligned input profiles and a single desired conclusion. [Source](https://aamas.csc.liv.ac.uk/Proceedings/aamas2017/pdfs/p1151.pdf)
A full treatment also establishes \(\Sigma_2^p\)-completeness for this discrete requirement under the name cautious exact bribery. [Source](https://arxiv.org/pdf/1608.02406) No result settling the mass-transfer problem above was located in the searches.
The problem is \(\mathrm{NP}\)-hard under polynomial-time many-one reductions. This holds even when:
Thus, a running time polynomial in \(m,\tau,L\) would imply \(\mathrm P=\mathrm{NP}\).
For a distribution \(\nu\), write its Kemeny score as
\(S_\nu(A)=\sum_{K\in\mathcal J}\nu_Kd(K,A)\).
Let \(\mu\) denote the initial distribution. From the definition of a transfer,
\(S_\nu(A)-S_\mu(A)=\sum_i\sum_{K\ne J_i}x_{iK}\bigl(d(K,A)-d(J_i,A)\bigr)\).
Every Hamming distance lies between \(0\) and \(m\). Consequently,
\(\lvert S_\nu(A)-S_\mu(A)\rvert\le m c(x)\).
Applying this bound to two reports \(A,B\) gives
\(S_\nu(A)-S_\nu(B)\ge S_\mu(A)-S_\mu(B)-2m c(x)\).
This bound applies to every allowed destination, including reports outside the input support, and to arbitrary real transfer amounts.
We reduce from propositional satisfiability, whose \(\mathrm{NP}\)-completeness is the Cook–Levin theorem. [Cook’s original paper](https://doi.org/10.1145/800157.805047).
Let \(F(x_1,\ldots,x_n)\) be the input formula. We may assume \(n\ge1\), adding an unused variable if necessary. Set
\(q=3(n+1)\).
The agenda has the following atomic issues, each together with its complement:
Thus,
\(m=1+2n+3q=11n+10\).
We describe complete judgment sets by their corresponding Boolean vectors.
The integrity constraint permits precisely the following reports.
Three baseline reports \(B_1,B_2,B_3\). In \(B_i\),
\(p=0,\qquad x_j=y_j=0\ \text{for every }j,\)
and
\(z_{r,k}=1\ \text{if }r=i,\qquad z_{r,k}=0\ \text{if }r\ne i.\)
One fallback report \(T\). In \(T\),
\(p=1,\qquad x_j=y_j=0\ \text{for every }j,\qquad z_{r,k}=1\ \text{for every }r,k.\)
Solution reports \(C(a)\). For each assignment \(a\in\{0,1\}^n\) satisfying \(F\), there is a report with
\(p=1,\qquad x_j=a_j,\qquad y_j=1-a_j,\qquad z_{r,k}=0\ \text{for every }r,k.\)
These conditions have a polynomial-size propositional encoding. Explicitly, let
\(Z=\bigwedge_{j=1}^n(\neg x_j\land\neg y_j)\),
let \(H_i\) assert that precisely block \(i\) of the \(z\)-variables is all \(1\), with the other blocks all \(0\), and let
\(H_*=\bigwedge_{r=1}^3\bigwedge_{k=1}^q z_{r,k}\).
Take
\(\Gamma=(\neg p\land Z\land(H_1\lor H_2\lor H_3))\lor(p\land Z\land H_*)\lor\left(p\land\bigwedge_{r,k}\neg z_{r,k}\land\bigwedge_{j=1}^n(y_j\leftrightarrow\neg x_j)\land F(x_1,\ldots,x_n)\right)\).
Because every variable belongs to the agenda, the three disjuncts characterize exactly the reports just described. In particular, checking whether a given complete report is feasible requires only evaluating \(\Gamma\), rather than solving an auxiliary satisfiability problem.
Give each \(B_i\) mass \(\frac13\), and set
\(\mathcal L=\{p\},\qquad b=\frac1{16}\).
The three support reports are distinct and feasible. The fallback \(T\) is always feasible and contains \(p\), independently of whether \(F\) is satisfiable.
Two different baseline reports disagree on precisely two blocks of \(q\) selector issues. Hence,
\(d(B_i,B_j)=2q\quad\text{for }i\ne j\),
and therefore
\(S_\mu(B_i)=\frac{4q}{3}=4(n+1)\).
Write this common score as \(D=4(n+1)\).
Every solution report \(C(a)\) differs from each \(B_i\) on:
Thus,
\(d(C(a),B_i)=1+n+q\),
so
\(S_\mu(C(a))=1+n+q=4(n+1)=D\).
Finally, \(T\) differs from each \(B_i\) on \(p\) and the two selector blocks other than block \(i\). Therefore,
\(S_\mu(T)=1+2q=6n+7=D+(2n+3)\).
It follows that every \(B_i\) is initially a Kemeny winner, whether or not solution reports exist. Since none contains \(p\), the initial society is always unsuccessful.
Suppose \(F\) has a satisfying assignment \(a\), and let \(A=C(a)\).
From each baseline report, transfer mass \(\frac{b}{3}\) to \(A\). This is feasible because \(\frac{b}{3}\le\frac13\), and \(A\) is distinct from every baseline report. Its total cost is exactly
\(c(x)=b=\frac1{16}\).
The resulting distribution is
\(\nu=(1-b)\mu+b\delta_A\).
For every feasible report \(Y\),
\(S_\nu(Y)-S_\nu(A)=(1-b)\bigl(S_\mu(Y)-S_\mu(A)\bigr)+b\,d(A,Y)\).
Section 3 shows that \(S_\mu(A)=D\) is a minimum initial score. Hence the first term is nonnegative. If \(Y\ne A\), then \(d(A,Y)\ge1\), making the second term strictly positive.
Consequently, \(A\) is the unique Kemeny winner. It contains \(p\), so the transfer succeeds at an attained cost equal to the budget.
Suppose \(F\) is unsatisfiable. Then
\(\mathcal J=\{B_1,B_2,B_3,T\}\),
and \(T\) is the only feasible report containing \(p\).
Consider any allowed transfer with \(c(x)\le b\). Applying Section 1 to \(T\) and \(B_1\),
\(S_\nu(T)-S_\nu(B_1)\ge (2n+3)-2mb\).
Using \(m=11n+10\) and \(b=\frac1{16}\), the right-hand side equals
\(2n+3-\frac{11n+10}{8}=\frac{5n+14}{8}>0\).
Thus \(T\) has strictly greater score than \(B_1\) after every transfer within budget. It cannot be a winner. Every winner therefore belongs to \(\{B_1,B_2,B_3\}\), and fails to contain \(p\).
We have proved the equivalence
\(F\text{ is satisfiable}\quad\Longleftrightarrow\quad\text{the constructed continuous bribery instance is successful within budget}.\)
If the input formula has bit length \(s\), the construction has
\(m=11n+10,\qquad \tau=3,\qquad L=O\bigl(s+n\log(n+2)\bigr)\),
using binary indices for variables. The constraint, agenda, and three support reports can all be constructed in polynomial time.
Therefore, an algorithm running in \(\operatorname{poly}(m,\tau,L)\) would solve satisfiability in polynomial time. The hardness uses constant masses and a constant positive budget; no small rational perturbation is hidden in the input.
For completeness, there is an exact finite LP characterization of the general problem. It explains how to handle the attained-budget requirement once the feasible reports are enumerated.
Let \(N=\lvert\mathcal J\rvert\le2^m\), and partition the reports into
\(\mathcal G=\{A\in\mathcal J:\mathcal L\subseteq A\},\qquad \mathcal B=\mathcal J\setminus\mathcal G\).
For each fixed \(A\in\mathcal G\), introduce variables \(y_{iK}\ge0\), representing the mass from original type \(i\) ultimately reporting \(K\). Impose
\(\sum_{K\in\mathcal J}y_{iK}=\mu_i\quad\text{for every }i,\)
and
\(\sum_i\sum_{K\ne J_i}y_{iK}\le b.\)
Introduce \(0\le\epsilon\le m+1\), impose
\(\sum_i\sum_{K\in\mathcal J}y_{iK}\bigl(d(K,B)-d(K,A)\bigr)\ge\epsilon\quad\text{for every }B\in\mathcal B,\)
and maximize \(\epsilon\).
The original instance is successful exactly when one of these LPs is feasible and has optimum strictly greater than \(0\):
The LP feasible region is closed and bounded: the mass equalities bound every \(y_{iK}\), and \(\epsilon\) has explicit bounds. Thus any feasible LP attains its optimum. All coefficients are rational, so standard exact rational linear programming decides whether the optimum is positive in polynomial time in the explicit LP encoding length.
Enumerating feasible reports by examining assignments to all propositional variables takes \(2^{O(L)}\) time, including auxiliary variables. There are at most \(2^m\) LPs, each with \(O(\tau2^m)\) variables and \(O(\tau+2^m)\) constraints. This gives an exact running-time bound
\(2^{O(L)}+2^m\operatorname{poly}(\tau2^m,m,L)\).
Finally, the reduction itself exhibits nonattainment of an infimum: for satisfiable \(F\), the same construction succeeds with every transfer proportion \(\epsilon>0\), while cost \(0\) leaves bad winners. Its successful-cost infimum is therefore \(0\), but \(0\) is not attained. The proof above uses an explicit successful transfer at the positive budget.
⟨structured verdict parsed — rendered above⟩
The output establishes that the continuous Kemeny bribery decision problem is \(\mathrm{NP}\)-hard under polynomial-time many-one reductions, with all the advertised restrictions. The reduction respects arbitrary real transfers, unrestricted feasible destinations, the requirement that every winner contain the desired conclusion, and attainment at the specified budget.
There is one minor quantifier issue in the supplementary nonattainment remark. It does not affect the hardness proof. No major issues or missing mathematical lemmas were found.
The score-change identity follows directly from removing \(x_{iK}\) mass from \(J_i\) and adding it to \(K\). It accounts for every permitted destination and does not assume that destinations belong to the initial support.
Since distances count complementary pairs once, each distance lies in \([0,m]\). Thus each difference \(d(K,A)-d(J_i,A)\) has absolute value at most \(m\). Nonnegativity of the transfer amounts justifies summing these bounds to obtain
\[ \lvert S_\nu(A)-S_\mu(A)\rvert\le mc(x). \]
Applying the bound separately to \(A\) and \(B\) gives the stated lower bound
\[ S_\nu(A)-S_\nu(B)\ge S_\mu(A)-S_\mu(B)-2mc(x). \]
The constants and inequality directions are correct. The argument applies to arbitrary real transfer amounts.
The source problem is propositional satisfiability under the standard Cook–Levin theorem: every language in \(\mathrm{NP}\) admits a polynomial-time many-one reduction to satisfiability. Cook’s construction explicitly produces a polynomial-size formula satisfiable exactly when the simulated nondeterministic computation accepts. The theorem is applicable here. [Cook’s original argument](https://www.inf.unibz.it/~calvanese/teaching/14-15-tc/material/cook-1971-NP-completeness-of-SAT.pdf).
Adding an unused variable preserves satisfiability, so the assumption \(n\ge1\) is legitimate. The issue count is correct:
\[ m=1+2n+3q=1+2n+9(n+1)=11n+10. \]
Every agenda issue is an atomic variable. Consequently, a complete judgment set determines a unique assignment to every variable occurring in \(\Gamma\).
The three disjuncts of \(\Gamma\) characterize precisely the claimed reports:
There are no unintended feasible reports. The report classes are distinct: \(p\) separates baselines from the other classes, and the selector coordinates separate \(T\) from solution reports.
The support consists of three distinct feasible reports with positive rational masses summing to one. The budget lies in the required interval. The desired set contains one positive literal, and \(T\) guarantees that a feasible report containing it always exists.
Here, binary rational encoding is understood in its standard sense of binary-encoded rational numerators and denominators; the mass \(\frac13\) is admissible under that interpretation.
All critical distance calculations are correct.
| Reports compared | Distance | Reason |
|---|---:|---|
| Distinct baselines | \(2q\) | Exactly two selector blocks differ |
| Solution and baseline | \(1+n+q\) | The \(p\) issue, one coordinate per assignment pair, and one selector block differ |
| Fallback and baseline | \(1+2q\) | The \(p\) issue and two selector blocks differ |
The resulting scores are therefore
\[ S_\mu(B_i)=\frac{4q}{3}=4(n+1)=D, \]
\[ S_\mu(C(a))=1+n+q=4(n+1)=D, \]
and
\[ S_\mu(T)=1+2q=6n+7=D+(2n+3). \]
These calculations cover every feasible report. Hence every baseline is initially a winner, regardless of satisfiability. Because each baseline excludes \(p\), the initial society is indeed always unsuccessful.
For a satisfying assignment \(a\), the destination \(A=C(a)\) is feasible and distinct from every baseline. Transferring \(\frac b3\) from each baseline respects the available masses and has total cost exactly \(b\).
The claimed resulting distribution,
\[ \nu=(1-b)\mu+b\delta_A, \]
is correct. Linearity of scores and \(d(A,A)=0\) give the stated comparison identity for every feasible \(Y\).
Section 3 establishes that \(A\) minimizes the initial score. Thus the first term in that identity is nonnegative. For \(Y\ne A\), distinct complete reports differ on at least one issue, so the second term is strictly positive.
Therefore \(A\) is the unique winner. This establishes the required success condition at an attained feasible cost equal to the budget. It does not depend on tie-breaking.
When \(F\) is unsatisfiable, the characterization of \(\Gamma\) leaves exactly the three baselines and \(T\). In particular, \(T\) is the only good report.
For every permitted transfer within budget, the general score bound gives
\[ S_\nu(T)-S_\nu(B_1)\ge (2n+3)-2mb. \]
Substitution yields
\[ (2n+3)-\frac{11n+10}{8}=\frac{5n+14}{8}>0. \]
The arithmetic and positivity are correct for every permitted \(n\).
Thus \(T\) cannot minimize the score. The feasible report set is finite and nonempty, so winners exist; every winner must be a baseline and therefore excludes \(p\). This proves impossibility for all allowed transfers within budget, including arbitrary real amounts and every feasible destination.
Both directions of the claimed reduction equivalence are established.
The construction contains linearly many issues and a constant number of explicitly described support reports. The integrity constraint contains \(F\) and only linearly many additional indexed variable occurrences. The stated bound
\[ L=O\bigl(s+n\log(n+2)\bigr) \]
is consistent with binary variable indices.
The construction does not enumerate satisfying assignments. Their reports are represented implicitly by the third disjunct of \(\Gamma\). Consequently, constructing the instance requires polynomial time even though its feasible report set may be exponentially large.
The reduction establishes \(\mathrm{NP}\)-hardness with constant support size and constant budget. The implication that a running time polynomial in \(m,\tau,L\) would give a polynomial-time satisfiability algorithm is valid. The output does not claim membership in \(\mathrm{NP}\), and no such membership result is needed.
The supplementary LP characterization is correct.
The variables \(y_{iK}\) describe a redistribution of each original mass. Nonnegativity and row-sum equalities enforce exactly the source-capacity conditions. Off-diagonal mass is exactly the original transfer cost, so the budget condition matches the task.
For a fixed good report \(A\), the score inequalities require \(A\) to beat every bad report by a positive margin when \(\epsilon>0\). Although \(A\) need not beat other good reports, this is sufficient: a bad report cannot be a global minimizer if \(A\) has a strictly smaller score.
Conversely, a successful distribution has a good winner, and every bad report has strictly larger score. Finiteness makes the minimum of these positive gaps positive. Score differences have absolute value at most \(m\), so the imposed upper bound on \(\epsilon\) does not obstruct this argument.
The edge cases are handled correctly:
The LP feasible region is closed and bounded whenever nonempty. Its optimum is therefore attained. All coefficients are rational. The invoked rational LP theorem gives polynomial running time in the explicit binary encoding length, rather than requiring a strongly polynomial algorithm; its hypotheses are satisfied. [Polynomial-time rational LP formulation](https://www.cs.princeton.edu/~smattw/Teaching/Fa19Lectures/lec5/lec5.pdf).
Enumerating assignments to all occurring propositional variables also handles auxiliary variables. The stated enumeration cost, LP dimensions, number of LPs, and overall exponential running-time bound are valid.
Minor — Section 6, final paragraph. The assertion that the construction succeeds with “every transfer proportion \(\epsilon>0\)” omits the upper bound required for a feasible transfer proportion. The proportional transfer previously described would remove \(\frac{\epsilon}{3}\) from each baseline, exceeding its available mass when \(\epsilon>1\). If the assertion concerns transfers within the specified budget, the budget supplies a stricter upper bound.
Minimum clarification: Explicitly restrict the quantified proportion to \(0<\epsilon\le1\), or to \(0<\epsilon\le b\) when discussing budget-feasible transfers.
The nonattainment conclusion survives this wording issue: the written comparison argument applies to arbitrarily small positive feasible proportions, while the initial-score calculation establishes failure at cost zero. No new mathematics is needed.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.