| paper | Controlling Elections through Social Influence |
| authors | Bryan Wilder, Yevgeniy Vorobeychik |
| venue | ATAL 2018 |
| filed under | voting · bribery-control |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\)-hard for every fixed \(\alpha\in(0,1]\), already with \(m=2\) and \(s=1\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 2
statement extracted from the paper’s text layer
Given two candidates \(c^\star,c_1\), a finite set \(T\) of complete voter-and-network-block types, a rational distribution \(\mu\in\mathbb{Q}_{\ge0}^{T}\) with \(\sum_t\mu_t=1\), a finite scenario distribution \(\rho\), typed kernels \(\lambda^\omega_{ut}\), and seed fraction \(\kappa\), choose \(x_t\in[0,\mu_t]\) with \(\sum_t x_t\le\kappa\) to maximize \(\Pr_{\omega\sim\rho}[2\sum_{t:\pi_t(2)=c^\star}r_t^\omega(x)>a_1-a_\star]\), where \(a_c=\sum_{t:\pi_t(1)=c}\mu_t\) and \(r^\omega(x)\) is the least fixed point of \(r_t=x_t+(\mu_t-x_t)(1-e^{-\sum_u\lambda^\omega_{ut}r_u})\); return an optimum or an \(\alpha\)-approximation.
A repeated-block stochastic-block ICM in which \(N\mu_t\) agents share complete type \(t\), edge probabilities scale as \(\lambda^\omega_{ut}/N\), seeding allocates mass \(x_t\), and victory is evaluated by continuous vote mass.
The proposed exponential cascade is not the limit of an arbitrary independent-cascade graph, so the prover must specify the \(1/N\) edge-probability scaling and establish finite-to-fluid convergence.
fatal: False
The mirror covers the two-candidate POV hardness result, including its deterministic one-scenario case, and suggests multicandidate extensions; it does not directly cover MOV guarantees, arbitrary-graph Theorem 4 instances, or the MILP formulations.
There is a credible continuous mirror here, and I would lead with the paper’s hardness result rather than its MILP formulations.
The lead anchor is Theorem 2, proved in this paper. It states that, for every constant \( \alpha>0 \), it is NP-hard to compute an \( \alpha \)-approximation to \( \max_{|S|\le k}\mathrm{POV}(S) \), even with only two candidates and even when the ICM instance is deterministic. The proof sets every propagation probability to \(0\) or \(1\), so there is one live-graph scenario and the POV objective is either \(0\) or \(1\). If an \( \alpha \)-approximation existed, one could enumerate the victory threshold \( \Delta \), use the algorithm to determine the largest reachable threshold, and thereby solve ordinary influence maximization, which is NP-hard. The citation to influence maximization supplies the source hardness, but Theorem 2 itself is established by the authors here.
I would mirror it as Continuous Typed Probability-of-Victory Control. The society has two candidates, \(c^\star\) and \(c_1\), and a finite set of complete voter/social types \(T\). A type records the voter’s ranking, community or network block, and all propagation parameters relevant to that block. The society is a rational distribution \( \mu\in\mathbb{Q}_{\ge0}^{T} \) with \( \sum_t\mu_t=1 \). Let \(T_2=\{t:\pi_t(2)=c^\star\}\), the types whose members can switch to \(c^\star\) after being influenced.
The attacker chooses seed mass \(x_t\in[0,\mu_t]\) for every type, subject to \( \sum_t x_t\le\kappa \), where \( \kappa \) is a population fraction rather than an integer number of named seeds. To make the continuum cascade precise, each scenario \( \omega \) supplies a finite typed influence kernel \( \lambda^\omega_{ut}\). The aggregate influenced mass is the least fixed point obtained from \(r_t^{\omega,0}=x_t\) and \(r_t^{\omega,j+1}=x_t+(\mu_t-x_t)\bigl(1-\exp(-\sum_{u\in T}\lambda^\omega_{ut}r_u^{\omega,j})\bigr)\). This is the fluid, block-replicated form of independent-cascade diffusion; a deterministic instance has a single scenario.
Write \(a_\star=\sum_{\pi_t(1)=c^\star}\mu_t\) and \(a_1=\sum_{\pi_t(1)=c_1}\mu_t\). The continuous target wins in scenario \( \omega \) exactly when \( \sum_{t\in T_2}r_t^\omega(x)>(a_1-a_\star)/2\). Thus the prover-facing problem is: maximize \( \mathrm{POV}_\infty(x)=\Pr_\omega[\sum_{t\in T_2}r_t^\omega(x)>(a_1-a_\star)/2] \) over all feasible seed-mass vectors \(x\), and return an optimal \(x\), or an \( \alpha \)-approximation to the optimum.
This is a genuine population continuization. In the intended regime, a platform has millions of users but only a moderate number of repeated preference-and-network types: for example, users with the same candidate ranking, community, exposure class, and propagation behaviour. For a common denominator \(N\), the rational mass \(N\mu_t\) gives a finite replicated population, while \(Nx_t\) gives the corresponding number of seeds. The normalized victory condition is exactly the finite condition up to the vanishing \(1/N\) tie-breaking term. The action variable is population mass itself; it is not merely a different encoding of a fixed finite graph.
My expectation is deliberately split by the type regime. With unrestricted numbers of social types, I expect Class B: Theorem 2’s hardness should transfer because the combinatorics can be placed in distinct network-role types, while voter multiplicity is irrelevant. With fixed or genuinely moderate \( \tau=|T| \), I would expect a possible Class A result—perhaps an FPT or approximation scheme in \( \tau \)—because the individual seed-selection obstruction has been replaced by a finite-dimensional mass-allocation problem. The interesting question is whether the POV threshold remains difficult after that collapse, or whether the typed cascade admits monotone optimization or a configuration-style formulation.
This mirror covers the paper’s constructive two-candidate POV problem, including its deterministic special case. It naturally generates follow-ups: exact winner-feasibility, additive \( \varepsilon \)-approximation, dependence on \( \tau \), finite-population rounding guarantees, and the multicandidate robust extension suggested by Theorem 4.
The weakest point is the network co-modification. The original paper permits an arbitrary graph of individually distinct nodes; my mirror requires exchangeable block structure and replaces edge-level randomness by a typed fluid cascade. If that structure is regarded as removing the essence of the paper, the case is weak. I think it remains defensible because the paper’s central object is still present—seed mass changes voter mass through social influence and is evaluated by probability of electoral victory—and the block/mean-field representation is forced by treating the population, rather than the list of named network nodes, as the continuous object.
The proponent has one serious anchor: Theorem 2. I would nevertheless reject the proposed model as a clean ChoCo mirror, for a structural reason. In this paper, a voter is not characterized merely by a preference ranking and a propagation parameter. The voter is a vertex in a particular graph, and its neighbourhood determines which other voters can be reached. That network position is part of the agent’s complete type.
If two vertices have the same ranking but different neighbourhoods, they are not the same type for this problem: seeding one may reach a large component while seeding the other reaches almost nothing. Grouping them into one mass therefore does not determine \(f(S,y)\), and hence does not determine \(\mathrm{POV}(S)\). To make the mass representation exact, the type must include the relevant network position and reachability structure. For an arbitrary graph, this produces essentially one type per vertex, so there is no high-multiplicity reduction.
The proposed fixed-point equation does not solve this problem; it changes it. The expression
\[ r_t^{\omega,j+1} = x_t+(\mu_t-x_t) \left(1-\exp\left(-\sum_u\lambda^\omega_{ut}r_u^{\omega,j}\right)\right) \]
assumes exchangeable, mean-field mixing between types. It is not the high-multiplicity limit of the paper’s independent-cascade model in general. Consider a block blow-up in which every member of type \(u\) has a live edge to every member of type \(t\). Any positive seed mass in \(u\) activates essentially all of \(t\) as the population grows; the limit is discontinuous, not the displayed exponential response. If instead the blow-up preserves sparse one-to-one edges, members of the same nominal type remain distinguishable by their matching partners. The intermediate exponential model is a new stochastic-block diffusion model, not a faithful continuization of the graph in Theorem 2.
The seed budget creates a second obstruction. With \(N\) replicated voters and a fixed discrete budget \(k\), the normalized seed mass is \(k/N\to0\), so the intervention disappears in the continuum. Keeping a nonzero \(\kappa\) requires scaling \(k\) with \(N\), thereby replacing the paper’s choice of \(k\) particular vertices by allocation of a positive fraction of a type. That is a legitimate new model, but it no longer represents the paper’s individual seed-selection problem. In particular, the continuum cannot express the effect of seeding one exceptional high-centrality vertex: a single point has zero mass.
The deterministic special case also exposes a degeneracy. Theorem 2 obtains its hardness with one live graph, so \(\mathrm{POV}\) is simply \(0\) or \(1\). In a deterministic fluid cascade, the probability objective disappears and becomes a threshold-feasibility question. Reintroducing a nontrivial probability requires random block kernels or externally sampled scenarios, which again defines a different model rather than the theorem’s deterministic ICM instance.
The strongest possible rescue is a graphon or typed stochastic-block formulation. But a graphon keeps a continuum of network positions \(z\), and the decision is then a measurable seed set \(x(z)\); agents remain distinguished by position. That is a continuum-network optimization problem, not a high-multiplicity society over interchangeable voter types. A finite block model does give interchangeable agents, but then either the number of blocks is fixed—removing the graph-specific structure—or it grows with the original graph, in which case the population has been replicated without being compressed.
The same objection applies to the suggested extension of Theorem 4: its robust objective depends on overlapping, candidate-specific reachable sets. Those overlaps are precisely vertex-level network information that a type-mass vector cannot recover unless the network is replaced by an additional exchangeability assumption.
Thus every faithful route faces the same fork: quotient by network position and lose the defining object of the paper, or retain network position and lose the high-multiplicity population model. This is a strong case against the proposed anchor as a worthwhile *mirror of this paper*. It is not, however, an airtight universal impossibility claim. A carefully specified stochastic-block version could be a worthwhile new continuous influence-control problem. The honest negative conclusion is that the proponent has not shown that this new problem is the paper’s continuous-population analogue rather than a separate mean-field network model.
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.