The Complexity of Probabilistic Lobbying (d4-conf-aldt-2009-0014)

Given complete voter types \(\Theta\) with rational masses \(\mu_\theta\) summing to \(1\), a probability grid \(D_k\), per-type issue probabilities and microbribery costs \(c_{\theta j}(a)\), issue weights \(w_j\), threshold \(t\), budget \(B\), and target weight \(O\), choose \(y_{\theta ja}\ge0\) with \(\sum_{a\in D_k}y_{\theta ja}=\mu_\theta\) and \(\sum_{\theta,j,a}c_{\theta j}(a)y_{\theta ja}\le B\), so that \(\sum_{j:\sum_{\theta,a}a y_{\theta ja}>t}w_j\ge O\).

There are \(m\ge1\) issues, all with desired outcome “yes.” A society is given by its support: the list \(\Theta\) of its \(\tau\ge1\) complete types with positive binary-rational masses \(\mu_\theta\), where \(\sum_\theta\mu_\theta=1\). Here \(\tau\) is the support size, not the number of possible types.
For an integer \(k\ge0\), let \(D_k=\{\ell/(k+1):\ell=0,\ldots,k+1\}\). Each type specifies initial probabilities \(p_{\theta j}\in D_k\) and explicit cost tables \(c_{\theta j}:D_k\to\mathbb Z_{\ge0}\). Costs vanish exactly at \(p_{\theta j}\) and are nondecreasing as probabilities move away from \(p_{\theta j}\) in either direction.
Inputs also include binary-encoded issue weights \(w_j\in\mathbb Z_{>0}\), target weight \(O\in\mathbb Z_{>0}\), budget \(B\in\mathbb Z_{\ge0}\), and rational threshold \(0\le t<1\). Costs are per unit mass; the budget measures total expenditure on the normalized society.
Microbribery may split each type's mass independently on each issue: choose real \(y_{\theta ja}\ge0\) with \(\sum_{a\in D_k}y_{\theta ja}=\mu_\theta\). Its cost is \(\sum_{\theta,j,a}c_{\theta j}(a)y_{\theta ja}\). Issue \(j\) is won exactly when \(\sum_{\theta,a}a y_{\theta ja}>t\); equality loses.
The decision problem asks whether such an allocation has cost at most \(B\) and satisfies \(\sum_{j:\sum_{\theta,a}a y_{\theta ja}>t}w_j\ge O\). Let \(L\) be the total binary input length; state running times in \(m,\tau,k,L\).

Is this divisible-mass, issue-weighted average-majority microbribery decision problem in \(\mathrm P\), or is it \(\mathrm{NP}\)-hard?

For finite lists of indivisible voters, issue-weighted microbribery is \(\mathrm{NP}\)-complete under average-majority evaluation, even with one voter and \(k=0\); requiring every issue to be won without issue weights is in \(\mathrm P\). [Discrete complexity results](https://arxiv.org/abs/0906.4431v4)
No classification of this exact divisible-mass variant was located in the literature search.

Classification

The problem is \(\mathrm{NP}\)-complete, already when \(\tau=1\), \(k=0\), \(t=1/2\), and every initial probability is zero.

Divisibility makes the cost of winning an individual issue computable by linear programming. The choice of which weighted issues to win remains computationally hard. The proof below handles the strict winning threshold explicitly.

1. Hardness with one support type

We reduce from the standard \(\mathrm{NP}\)-complete positive-integer Subset Sum problem: given binary-encoded integers \(a_1,\ldots,a_n,C>0\), determine whether some subset sums to \(C\). This is the classical numerical problem underlying [Karp’s completeness results](https://link.springer.com/chapter/10.1007/978-1-4684-2001-2_9).

Construct an instance with \(m=n\) issues and one type \(\theta\) of mass \(\mu_\theta=1\). Set

\[ \text{ } \]

For each issue \(j\), use \(k=0\), so \(D_0=\{0,1\}\), and define
\(p_{\theta j}=0\), \(c_{\theta j}(0)=0\), \(c_{\theta j}(1)=4a_j\), and \(w_j=a_j\).
Finally, set \(t=1/2\), \(O=C\), and \(B=2C+1\).

These cost tables satisfy all hypotheses: their costs are nonnegative integers, vanish exactly at the initial probability, and are nondecreasing away from that probability. The construction has binary encoding length linear in the Subset Sum input length.

Write \(x_j=y_{\theta j1}\). Mass conservation gives \(y_{\theta j0}=1-x_j\), with \(0\le x_j\le1\). Thus issue \(j\) is won exactly when \(x_j>1/2\), and its cost is \(4a_jx_j\).

Forward implication. Suppose \(S\subseteq\{1,\ldots,n\}\) satisfies \(\sum_{j\in S}a_j=C\). Choose

\(x_j=\frac12+\frac{1}{4C}\) for \(j\in S\), and \(x_j=0\) otherwise.

Because \(C\ge1\), these are valid probabilities, and precisely the issues in \(S\) are won. Their total weight is \(C=O\), and their total cost is

\(\sum_{j\in S}4a_j\left(\frac12+\frac{1}{4C}\right)=2C+1=B.\)

Reverse implication. Suppose a feasible allocation exists, and let \(S=\{j:x_j>1/2\}\). The objective requires \(\sum_{j\in S}a_j\ge C\), so \(S\) is nonempty. Nonnegative costs and strict winning imply

\(2\sum_{j\in S}a_j<\sum_{j\in S}4a_jx_j\le\sum_{j=1}^{n}4a_jx_j\le2C+1.\)

Since \(\sum_{j\in S}a_j\) is an integer, it follows that \(\sum_{j\in S}a_j\le C\). Combining the two bounds gives \(\sum_{j\in S}a_j=C\).

This proves a polynomial-time many-one reduction and hence \(\mathrm{NP}\)-hardness. The additional unit in the budget accommodates strict victory without allowing the next integer subset sum.

2. Exact costs and the strict threshold

We now prove an exact feasibility criterion for general inputs.

Define the initial average of issue \(j\) by \(b_j=\sum_\theta\mu_\theta p_{\theta j}\). Let \(F=\{j:b_j>t\}\) be the initially won issues and \(J=\{1,\ldots,m\}\setminus F\).

For every \(j\in J\), let \(q_j\) be the optimum of the following weak-threshold linear program:

\(\displaystyle q_j=\min\left\{\sum_{\theta,a}c_{\theta j}(a)y_{\theta ja}:\ y_{\theta ja}\ge0,\ \sum_a y_{\theta ja}=\mu_\theta\text{ for every }\theta,\ \sum_{\theta,a}a y_{\theta ja}\ge t\right\}.\)

The feasible region is compact: each variable lies between zero and its type’s mass. It is nonempty because assigning all mass to probability one yields average one, which exceeds \(t\). Therefore the minimum exists.

Lemma. For \(j\in J\), every allocation strictly winning issue \(j\) has cost greater than \(q_j\). Conversely, for every \(\eta>0\), there is a strictly winning allocation with cost less than \(q_j+\eta\).

Proof. Consider a strictly winning allocation with average \(v>t\) and cost \(K\). Necessarily \(K>0\): because costs vanish exactly at the initial probabilities, a zero-cost allocation must be the initial allocation, whose average is \(b_j\le t\).

Mix this allocation with the initial allocation, using proportion

\(\lambda=(t-b_j)/(v-b_j)\)

of the winning allocation. Here \(0\le\lambda<1\). The resulting average is exactly \(t\), and its cost is \(\lambda K<K\). Consequently \(q_j\le\lambda K<K\).

For the converse, take an optimal weak-threshold allocation and mix it with the allocation assigning all mass to probability one. Any positive mixing proportion gives average strictly greater than \(t\). Its cost converges to \(q_j\) as that proportion tends to zero. Thus its cost can be made less than \(q_j+\eta\). This proves the lemma.

The lemma shows that \(q_j\) is the infimum, rather than an attainable minimum, of the strict winning costs.

3. Feasibility criterion and membership in \(\mathrm{NP}\)

Let \(W_F=\sum_{j\in F}w_j\). If \(W_F\ge O\), the initial allocation already succeeds at cost zero.

Otherwise, the instance is feasible exactly when there is a nonempty subset \(S\subseteq J\) satisfying

\(W_F+\sum_{j\in S}w_j\ge O\quad\text{and}\quad\sum_{j\in S}q_j<B.\)

Necessity. Given a successful allocation, let \(S\) be its won issues belonging to \(J\). Its total winning weight is at most \(W_F+\sum_{j\in S}w_j\), so the weight inequality holds. Since \(W_F<O\), the set \(S\) is nonempty. By the lemma and nonnegative costs,

\(\sum_{j\in S}q_j<\sum_{j\in S}\text{cost on issue }j\le B.\)

Sufficiency. Suppose such an \(S\) exists. Put \(\Delta=B-\sum_{j\in S}q_j>0\). For each \(j\in S\), the lemma supplies a strictly winning allocation of cost less than \(q_j+\Delta/|S|\). Use these allocations on \(S\) and retain the initial allocation on every other issue. Independent splitting on different issues makes this a valid allocation. Its total cost is less than \(B\), and its winning weight meets the target.

For membership in \(\mathrm{NP}\), a certificate needs only specify \(S\), using at most \(m\) bits. A deterministic verifier computes the \(q_j\) by exact rational linear programming and checks the two inequalities.

The standard rational linear-programming theorem computes an optimum in polynomial bit time when the coefficients are explicitly encoded rationals; finite optimum values have polynomial binary encoding length. Its hypotheses hold here: all coefficients are rational, and each feasible region is nonempty and compact. Thus exact comparison with \(B\), including equality cases, is polynomial-time computable. No real-valued allocation needs to be included in the certificate.

Together with Section 1, this proves \(\mathrm{NP}\)-completeness.

4. Running times

Each issue’s linear program has \(N=\tau(k+2)\) variables, \(\tau\) mass-conservation equations, one threshold inequality, and nonnegativity constraints. Its rational encoding length is polynomial in \(N+L\). Hence all required costs and any proposed subset can be verified in bit time

\(m\bigl(\tau(k+2)+L\bigr)^{O(1)}.\)

Enumerating subsets after computing these costs gives a deterministic exact algorithm with running time

\(2^m\bigl(m+\tau(k+2)+L\bigr)^{O(1)}.\)

Because the tables are explicit, \(m\tau(k+2)\) is bounded by the total input length up to encoding constants. The verifier is therefore polynomial in \(L\).

Requiring every issue to be won is polynomial-time solvable: if \(J\) is empty, accept; otherwise, accept exactly when \(\sum_{j\in J}q_j<B\). This confirms that the hardness comes from weighted issue selection despite polynomial-time computation of individual issue costs.

⟨structured verdict parsed — rendered above⟩

The prover resolves the task correctly: the divisible-mass decision problem is \(\mathrm{NP}\)-complete, including the stated restriction to one support type and two probability levels. No substantive gap or false mathematical statement was found.

1. Reduction and input validity.

The source problem is correctly specified as positive-integer, binary-encoded Subset Sum. Its \(\mathrm{NP}\)-completeness is the standard numerical complexity result attributed to [Karp’s completeness results](https://link.springer.com/chapter/10.1007/978-1-4684-2001-2_9).

Every constructed parameter satisfies the task’s restrictions:

• The single mass is positive and sums to one.
• With \(k=0\), the probability domain is exactly \(D_0=\{0,1\}\).
• Since \(a_j>0\), the costs vanish exactly at the initial probability and satisfy the required monotonicity.
• The weights and target are positive integers; the budget is a nonnegative integer.
• The threshold \(t=1/2\) satisfies \(0\le t<1\).

Multiplication by four and the construction of \(2C+1\) increase binary lengths by only a constant per number. The polynomial-size construction claim is valid.

2. Forward implication.

For a subset summing to \(C\), the proposed winning probability is
\(x_j=1/2+1/(4C)\). Since \(C\ge1\), it lies strictly above \(1/2\) and at most \(3/4\). Unselected issues have probability zero and lose.

The weight is exactly \(C\), and the stated cost calculation is correct:
\(\sum_{j\in S}4a_j(1/2+1/(4C))=2C+1\).
The budget permits equality, so this allocation is feasible.

3. Reverse implication.

The winning set is nonempty because its weight must reach \(C>0\). Each won issue has cost strictly greater than \(2a_j\). Consequently, the displayed strict inequality remains strict after summing over the winning set.

The resulting integer bound is valid: an integer sum at least \(C+1\) would have twice that sum at least \(2C+2\), contradicting the bound strictly below \(2C+1\). Thus the winning set sums exactly to \(C\).

This establishes the claimed many-one reduction. Divisibility and expenditure on losing issues introduce no loophole: the reverse argument explicitly includes all expenditure and uses its nonnegativity.

4. Weak-threshold optimum and strict-threshold lemma.

The LP feasible set is closed and bounded, and the all-one allocation makes it nonempty because \(t<1\). Its linear objective therefore attains a finite minimum.

The first direction of the lemma is correct. Zero cost forces all mass to remain at the unique zero-cost probabilities, giving average \(b_j\le t\). A strictly winning allocation therefore has positive cost \(K\).

The mixing coefficient \(\lambda=(t-b_j)/(v-b_j)\) has a positive denominator and satisfies \(0\le\lambda<1\). Mixing preserves every mass constraint, gives average exactly \(t\), and costs \(\lambda K<K\). This verifies \(q_j<K\).

The converse also holds as written. Mixing an optimal weak-threshold allocation with the all-one allocation gives average strictly above \(t\) for every positive mixing proportion. Its cost converges to \(q_j\), establishing the claim for every \(\eta>0\). This argument also covers an optimum whose average already exceeds the threshold.

The boundary case \(b_j=t\) is handled by \(\lambda=0\); no division-by-zero or strictness issue occurs.

5. Global feasibility criterion.

Both directions are valid.

For necessity, a successful allocation may lose some initially won issues. The prover correctly uses an upper bound on its winning weight, rather than assuming all initially won issues remain won. The selected set must be nonempty when \(W_F<O\), permitting the strict summed cost inequality.

For sufficiency, \(\Delta>0\) and the finite, nonempty set \(S\) justify allocating the stated positive cost allowance to each selected issue. Independent splitting across issues makes the combined allocation admissible. Keeping all other issues at their initial allocations preserves the initially won weight at zero additional cost.

The criterion correctly rejects an exact budget equality for any nonempty selection. It also handles \(B=0\), \(t=0\), and targets exceeding the total issue weight.

6. Membership in \(\mathrm{NP}\) and running times.

The rational LP theorem is stated sufficiently precisely: explicitly encoded rational LPs can be optimized in polynomial bit time, with polynomial-length finite optimum values. Its hypotheses are verified here. The exactness and bit-complexity claims agree with standard [linear-programming references](https://ocw.mit.edu/courses/6-854j-advanced-algorithms-fall-2008/c61e649bf05c7123da984519955da0bd_lec9.pdf).

The initial-success branch requires no subset certificate. Otherwise, an \(m\)-bit subset certificate suffices because the proven criterion replaces real-allocation verification with exact rational comparisons.

The LP dimensions, verification bound \(m(\tau(k+2)+L)^{O(1)}\), and enumeration bound \(2^m(m+\tau(k+2)+L)^{O(1)}\) are valid. Explicit cost tables ensure the relevant dimensions are bounded polynomially in \(L\).

The additional claim about requiring every issue to be won follows directly from the same criterion.

7. Issue and minimum feedback.

Minor, cosmetic: Section 1 contains a dangling “Set” followed by an empty display. Delete that fragment. All construction parameters are specified immediately afterward, so it creates no mathematical ambiguity or missing assumption.

No mathematical repair or additional lemma is needed.

⟨structured verdict parsed — rendered above⟩