| paper | The Complexity of Probabilistic Lobbying |
| authors | Daniel Binkele-Raible, G. Erdélyi, H. Fernau, J. Goldsmith, Nicholas Mattei, J. Rothe |
| venue | ALDT 2009 |
| filed under | voting · bribery-control |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\)-complete, already for \(\tau=1\), \(k=0\), and \(t=1/2\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 4.6
statement extracted from the paper’s text layer
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\).
The model has a finite type set \(\Theta\), mass distribution \(\mu\), and issue-specific variables \(y_{\theta ja}\) assigning mass of type \(\theta\) to final confidence level \(a\). Microbribery permits these assignments independently across issues; costs are linear in mass, while passed issues contribute indivisible weights. The agenda-level selection therefore remains knapsack-like even though the population is divisible.
The strict \(>\) threshold can make a per-issue minimum unattained in the weighted construction, and the proponent only sketches rather than fully specifies the polynomially encoded rational-margin treatment.
fatal: False
The mirrors cover the principal voter-bribery and issue-weighted microbribery results, including their contrasting algorithmic and hardness behavior. They do not establish continuous counterparts for the full parameterized-complexity, approximation, inapproximability, or open-problem catalogue.
The strongest positive case is a qualified yes. The paper’s rows are not yet a continuous society: \(P\) has one row per named voter. But its rows already contain exactly the information needed for high multiplicity. Replace the voter index by a distribution over complete row-types, while retaining the internal probabilities, confidence levels, prices, equal-per-issue voter bribery, and binary referendum outcomes.
My lead anchor is Theorem 4.5, proved in this paper. It states that both VB-SM-PLP and VB-AM-PLP are NP-complete. VB-SM-PLP asks whether, given a probability matrix \(P\), cost matrix \(CP\), budget \(B\), and threshold \(t\), The Lobby can bribe voters—using voter bribery, so the payment to one voter is distributed equally over all issues—so that every issue passes the strict-majority criterion. VB-AM-PLP asks the same under average majority. The paper proves membership in NP and proves NP-hardness by reducing the earlier OPTIMAL LOBBYING problem of Christian et al. [CFRS07]. The reduction already works in the deterministic special case \(k=0\): \(P\) is a \(\{0,1\}\)-matrix, \(t=1/2\), changing a voter costs one unit per affected issue, and bribing a row costs \(n\) times the amount paid per issue. Thus an OL instance with budget \(b\) becomes a VB instance with budget \(B=bn\). The theorem itself is proved here; only the source hardness of OL is cited from [CFRS07].
The corresponding continuous problem is Continuous Voter-Bribery Probabilistic Lobbying.
An instance has a finite type set \(\Theta\), rational masses \(\mu_\theta\) with \(\sum_{\theta\in\Theta}\mu_\theta=1\), issues \(j\in\{1,\ldots,n\}\), a discretization grid \(D_k=\{0,1/(k+1),\ldots,1\}\), and, for every type \(\theta\), an initial probability vector \(p_{\theta j}\) and a complete cost table \(c_{\theta j}(a)\). The type includes the entire row of \(P\) and the entire row of \(CP\), so two agents have the same type only if they are identical for every purpose used by the problem.
Let \(g_{\theta j}(d)\) be the confidence level reached by a type-\(\theta\) voter on issue \(j\) after receiving a per-voter payment \(d\), with the payment divided equally over the \(n\) issues according to the paper’s voter-bribery rule. It is enough to consider the finitely many payment breakpoints at which some \(g_{\theta j}\) changes. The Lobby chooses variables \(x_{\theta d}\), where \(x_{\theta d}\) is the mass of type \(\theta\) receiving payment \(d\). Thus
\[ \sum_d x_{\theta d}=\mu_\theta \]
for every type, and the normalized total cost is
\[ \sum_{\theta,d} d\,x_{\theta d}. \]
Under average majority, issue \(j\) passes when
\[ \sum_{\theta,d} g_{\theta j}(d)x_{\theta d}>t. \]
Under strict majority, it passes when
\[ \sum_{\theta,d:\,g_{\theta j}(d)>t}x_{\theta d}>\frac12. \]
The continuous decision problem asks whether there is such an allocation with total cost at most \(B\) making every issue pass; its optimization version minimizes the total cost.
This is a faithful mirror. The society is continuous, but the probabilities are still probabilities of individual votes, not population masses. The voter-bribery restriction is preserved: one payment level must govern all issues for the same unit of mass. In a realistic regime, this could describe a large direct-democracy electorate, shareholder base, or membership organization in which millions of people fall into a few hundred repeated attitude-and-price profiles. The relevant comparison is \(N\gg|\Theta|\), not merely “many voters.”
The expected result is Class A. Once the type-action breakpoints are listed, the problem is a linear-programming feasibility problem. The average-majority constraints are linear directly; strict-majority constraints are also linear because each action level either places its mass above \(t\) or does not. Strict inequalities can be handled by maximizing a common rational slack. Hence the paper’s discrete NP-completeness disappears because the hard choice of whole rows is replaced by divisible mass.
This also gives the intended high-multiplicity bridge. A finite election with \(N\mu_\theta\) voters of each type is recovered by restricting the \(x_{\theta d}\) to multiples of \(1/N\). Conversely, the continuous problem is the divisible high-multiplicity relaxation of the finite one. The discrete OL reduction is therefore not contradicted: it exploits indivisible row selection, while the mirror permits a fraction of a repeated row-type to be bribed.
A second, useful boundary anchor is Theorem 4.6, also proved in this paper. It states that MB-SM-PLP-WIW and MB-AM-PLP-WIW are each NP-complete. These are the issue-weighted versions of microbribery: the input includes positive issue weights \(w_1,\ldots,w_n\) and an objective \(O\), and The Lobby need only make the total weight of passed issues at least \(O\). Membership in NP is proved by guessing edited matrix entries and their expenditures. NP-hardness is proved from KNAPSACK using one voter, \(k=0\), initial probability \(0\) on every issue, threshold \(t=1/2\), issue-edit cost equal to the object’s knapsack weight, and issue weight equal to its profit. Selecting issues of total cost at most \(W\) and total profit at least \(P\) is exactly the lobbying question. With one voter, strict and average majority coincide.
Its continuous mirror is Continuous Issue-Weighted Microbribery Lobbying. The population input is again \((\Theta,\mu)\) with complete probability-and-cost types. For each type \(\theta\), issue \(j\), and final confidence level \(a\), let \(y_{\theta ja}\) be the mass whose \(j\)-entry is changed to \(a\). Microbribery permits these choices independently across issues, exactly as in the paper. The constraints are
\[ \sum_a y_{\theta ja}=\mu_\theta \]
for every \(\theta,j\), and the total cost is
\[ \sum_{\theta,j,a}c_{\theta j}(a)y_{\theta ja}. \]
Issue \(j\) passes under average majority when
\[ \sum_{\theta,a}a\,y_{\theta ja}>t, \]
and under strict majority when
\[ \sum_{\theta,a>a_0}y_{\theta ja}>\frac12, \]
where \(a_0=t\). The question is whether the total cost is at most \(B\) and the sum of the weights of passed issues is at least \(O\).
Here I expect Class B rather than a collapse to P. The population has become divisible, but an issue still contributes its entire weight only after its threshold is crossed. The discrete combinatorics has moved from voters to the agenda. The one-type KNAPSACK reduction survives after a rational scaling: give the single type mass \(1\), start every issue at probability \(0\), let changing issue \(j\) to \(1\) cost \(2a_j\) per unit mass, and pass it by changing slightly more than half the mass. Its minimum cost is then essentially \(a_j\); a small rational margin handles the strict inequality. The problem still selects a subset of issues whose costs fit the budget and whose weights reach \(O\). Thus this hardness is not population-multiplicity hardness; it is agenda/issue-selection hardness.
The two mirrors generate different follow-up questions. For the lead problem: what are the exact finite-\(N\) rounding guarantees, how do strict thresholds and ties affect convergence, and what happens if bribes must be made to whole individuals rather than splittable mass? For the weighted microbribery problem: does the continuous per-issue optimization reduce the problem to an ordinary knapsack with an FPTAS, and which additional coupling constraints would make the hardness genuinely continuum-specific?
The weakest point is the lead mirror’s allowance for bribing a fraction of a type at one payment level. That is a genuine relaxation of the paper’s atomic voter action. I think it is nevertheless the correct high-multiplicity interpretation: an atomless population permits a measurable subpopulation of otherwise identical voters to be contacted, and the type records every feature relevant to cost and response. If the authors insist that all members of a type must always be bribed together, the LP collapse disappears—but that would preserve atomicity rather than continuize the population.
So I would defend a strong, bounded claim: Theorem 4.5 supports a natural and nontrivial Class A continuous mirror in which the paper’s voter-bribery hardness dissolves; Theorem 4.6 supplies a complementary Class B mirror showing that issue-weighted microbribery retains hardness. I would not claim that every parameterized or approximation result in the paper has been mirrored.
I cannot make a credible universal negative case here. Theorem 4.5 is a genuine computational anchor, and its best continuous interpretation survives the obvious objections.
The strongest attack is that the proposed \(x_{\theta,d}\) variables fractionalize an action that is atomic in the paper: the Lobby pays an individual voter one amount, not an arbitrary fraction of that voter. But that is precisely what high multiplicity means in this programme. If many voters share the complete type \(\theta\)—including their probability vector and every cost function—an atomless subpopulation can receive payment \(d\) while the rest receives payment \(d'\). The faithful continuum model is therefore
\[ \sum_d x_{\theta,d}=\mu_\theta, \qquad \sum_{\theta,d}d\,x_{\theta,d}\le B/N, \]
with average-majority constraints
\[ \sum_{\theta,d}g_{\theta j}(d)x_{\theta,d}>t \]
and strict-majority constraints obtained by summing the mass of actions with \(g_{\theta j}(d)>t\). Since the cost tables give only finitely many relevant payment breakpoints, this is an LP of polynomial size in the explicit type representation. A finite electorate with \(N\mu_\theta\) voters is recovered by restricting masses to multiples of \(1/N\). Large referendum electorates, shareholder bases, or membership organizations with repeated attitude-and-price profiles are entirely plausible high-multiplicity regimes.
Disallowing fractional subdivision of a type would not defeat this mirror; it would simply impose an additional atomicity constraint absent from the continuous-population programme. Nor does the fact that the resulting problem may be easy count against it: the disappearance of the row-selection hardness is exactly the kind of Class A phenomenon the programme seeks.
Theorem 4.6 is weaker as a population argument, since the paper’s KNAPSACK reduction uses one voter. The proponent’s literal construction therefore says little about population multiplicity. But the better construction does not rescue the negative case. Replicate that voter into an arbitrarily large population of identical types. Microbribery remains independently selectable by issue, while each issue contributes its full weight only if its threshold is crossed. The continuous problem still contains
\[ \min \sum_j q_j z_j \quad\text{subject to}\quad \sum_j w_jz_j\ge O,\qquad z_j\in\{0,1\}, \]
where \(q_j\) is the minimum mass-normalized cost of passing issue \(j\). Population divisibility does not remove this agenda-level selection. That is a valid Class B result, not a defect; hardness living in the agenda is explicitly within scope.
The only genuine reservations are about formulation quality: the authors would need to specify the normalization of budgets, the finite encoding of payment breakpoints, and finite-\(N\) rounding near strict thresholds. The one-type weighted construction also needs a careful treatment of strict-majority infima. None is fundamental, and each is repairable by a recognized mass-threshold convention or a small margin.
Thus the negative case can reject the claim that every theorem in the paper has a deep continuous counterpart, and can criticize the proponent’s exact formulation. It cannot defeat Theorem 4.5’s high-multiplicity LP mirror, nor Theorem 4.6’s agenda-hard continuous variant. The honest verdict is that the case against is weak.
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.