| paper | Manipulating Opinion Diffusion in Social Networks |
| authors | Robert Bredereck, Edith Elkind |
| venue | IJCAI 2017 |
| filed under | frontier · opinion-networks |
| 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}\text{-complete}\) · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Corollary 1
Given a finite type set \(T\), rational masses \(\mu_t\) summing to \(1\), initial opinions \(o_t\in\{0,1\}\), rational block-exposure coefficients \(a_{tu}\), a quota \(Q\), and a budget \(K\), can one choose bribe masses \(b_t\in[0,\mu_t]\) with \(\sum_t b_t\le K\) so that every stable endpoint reachable by finitely many asynchronous moves of positive eligible mass and maximizing \(\sum_t x_t\) has \(\sum_t x_t\ge Q\), where a type may move mass toward black exactly when \(B_t(x)>W_t(x)\) and toward white when \(W_t(x)>B_t(x)\)?
A finite-type block influence network in which type \(t\) carries mass \(\mu_t\), every member has the same exposure profile \(a_{tu}\), and \(x_t\) is the black mass of that type. Bribery converts initially white mass at a specified per-unit cost; diffusion transfers mass between opinions under strict block-majority eligibility; the objective is to force an optimistic black-mass quota.
The phrase 'flip a type-mass' does not specify the allowed mass increment or the treatment of equality and limiting update sequences, so different precise continuum dynamics could yield different reachable stable endpoints.
fatal: False
The mirror covers the bribery hardness component of Corollary 1 for optimistic outcomes and leaves pessimistic bribery, link control, update-sequence control, and the acyclic algorithms outside the proposed formulation.
The strongest positive case is a high-multiplicity, block-network version of the paper’s bribery problem. I would lead with the paper’s Corollary 1, rather than its tractable special cases, because it asks exactly whether a discrete hardness result survives when individual agents are replaced by population mass.
The continuous model would be a Mass-OPT-INFNET-BRIBERY problem. An instance contains a finite set of network types \(T\), rational masses \(\mu_t\ge 0\) with \(\sum_{t\in T}\mu_t=1\), an initial opinion \(o_t\in\{0,1\}\), and rational exposure coefficients \(a_{tu}\ge 0\). A type records everything relevant to diffusion: its initial opinion and the number or density of links it has to every other type. Thus agents of one type are interchangeable. The number of actual agents \(N\) is not part of the input; rational masses represent populations with \(N\mu_t\) agents for arbitrarily large common denominators.
Let \(x_t\in[0,\mu_t]\) be the current black mass of type \(t\). Its black and white exposure are
\[ B_t(x)=\sum_{u\in T}a_{tu}x_u, \qquad W_t(x)=\sum_{u\in T}a_{tu}(\mu_u-x_u). \]
A white mass of type \(t\) may turn black when \(B_t(x)>W_t(x)\); black mass may turn white when \(W_t(x)>B_t(x)\). An asynchronous update chooses one currently eligible type-mass and flips it. An endpoint is stable when no positive mass is eligible to change. The optimistic endpoints are the reachable stable endpoints maximizing \(\sum_t x_t\), exactly mirroring the paper’s optimistic update semantics.
The manipulator chooses bribe masses \(b_t\), where \(0\le b_t\le\mu_t\) for initially white types. After bribery,
\[ x_t^b=\mu_to_t+b_t \]
when \(o_t=0\), and \(x_t^b=\mu_t\) when \(o_t=1\). The objective is
\[ \min \sum_{t:o_t=0} b_t \]
subject to every optimistic stable endpoint reachable from \(x^b\) containing at least quota \(Q\) black mass. The decision version asks whether this can be achieved with total bribe mass at most \(K\). Type-dependent per-unit prices \(\gamma_t\) could be added without changing the model’s interpretation.
This is genuinely a population continuization. Individual opinions remain binary, and diffusion remains a discrete asynchronous majority process. Only the population is continuous: a type may contain a fractional mass of black agents, and bribery acts on mass rather than on named vertices. The exposure matrix is a necessary co-modification: once many indistinguishable agents share a role, their network position must be described by their common type-level exposure profile.
A natural regime is a large online platform with millions of accounts but perhaps tens or hundreds of stable exposure cohorts. Members of a cohort receive the same recommendation mix, occupy the same block of the influence network, share the same initial binary opinion, and have the same manipulation price. A campaign buys conversion of \(0.3\%\) of one cohort, not of a particular named account. This is a plausible high-multiplicity setting with \(N\gg |T|\). In the special case of equal masses and \(a_{tu}\in\{0,1\}\), the model is the population blow-up of an undirected role graph: every member of type \(t\) is linked to every member of an adjacent type \(u\). Thus the model retains the paper’s majority-network interpretation rather than replacing it with an unrelated voting or outcome-space model.
The anchor is Corollary 1, proved in this paper. Its full content is that both OPTIMISTIC INFNET BRIBERY and PESSIMISTIC INFNET BRIBERY are NP-complete; they are W[2]-hard when parameterized by the number \(k\) of vertices that may be bribed, even when the network has diameter at most \(8\); and they are W[1]-hard when parameterized by the treewidth of the input graph. The paper obtains these claims through its proved Proposition 2, which gives a polynomial reduction from TARGET SET SELECTION preserving yes-instances, setting \(k=h\) and the target quota to all vertices, while keeping treewidth within \(O(\operatorname{tw}(G))\) and increasing diameter by at most \(6\). The underlying TSS hardness is cited from Nichterlein et al. for the W[2] result and Ben-Zwi et al. for the W[1] result.
The continuous question above is therefore:
Given a finite rational type population, a type-level undirected influence structure, initial binary opinions, a target black mass \(Q\), and a bribe-mass budget \(K\), can one convert at most \(K\) mass of initially white agents so that every optimistic stable outcome contains at least \(Q\) black mass?
The authors should recognize this as their problem because all substantive ingredients remain: binary opinions, majority updates, stable outcomes, adversarial manipulation, and best-case or worst-case update behavior. The model merely replaces many interchangeable vertices by their population proportions and replaces vertex bribery by mass bribery.
My expectation is Class B, tentatively. The hardness in Corollary 1 is driven primarily by the interaction topology and the cascade structure of the role graph, not by the fact that one particular vertex has unit mass. The relevant reduction should therefore be sought with high-multiplicity role blocks and rational masses. In particular, the stabilizer gadgets from Proposition 2 suggest a route to making partial bribes ineffective or quantitatively controlled, so that the TSS choices remain encoded in the type-level topology. If that succeeds, the discrete hardness transfers. If fractional seeding cannot be blocked, the problem may instead become a genuinely continuum-specific hardness problem rather than becoming tractable.
The mirror also generates useful follow-up questions: whether the pessimistic version has the same complexity; whether acyclic type graphs admit a dynamic program analogous to the paper’s Theorem 1; whether the problem is fixed-parameter tractable in the number of types; and whether link deletion can be continuized by allowing the manipulator to remove a mass of cross-type exposure rather than individual edges.
The weakest point is that the original paper permits arbitrary vertex-level graphs and one-agent asynchronous updates, whereas this mirror imposes a block structure and naturally updates type masses. Moreover, the paper’s parameter \(k\) counts individuals, while the continuous parameter \(K\) is real-valued mass, so Corollary 1 does not transfer automatically. A referee would reasonably demand a careful fractional-bribe analysis and a reduction robust to partial investment. That is a genuine technical gap, but not a failure of the mirror: the proposed question preserves the paper’s underlying computational problem while exposing exactly where continuization may dissolve, preserve, or replace its discrete hardness.
The strongest negative case is that Corollary 1 is not being continuized; it is being replaced by a different dynamical system.
The paper’s agents are interchangeable only if their entire neighbourhood behaviour is interchangeable. The exposure coefficients \(a_{tu}\) do not ensure that: two agents can have the same average exposure to every type but different neighbours, and therefore different eligibility to update once opinions begin to diverge. In a generic graph, the complete dynamic type of a vertex includes its incidence pattern with individual vertices, so type classes are usually singletons. A genuine finite-type regime therefore requires a highly symmetric blow-up graph, not merely a population distribution over the paper’s networks.
That blow-up has a serious semantic problem. With \(N\) copies of each role, an asynchronous individual update changes a type’s mass by \(1/N\). In the limit, every single update has zero effect. To obtain nontrivial dynamics one must instead allow a positive mass of a type to update at once, or introduce a mean-field differential inclusion. Either choice changes the paper’s process. The paper’s strict-majority rule and its gadgets operate exactly at integer thresholds; the difference made by one vertex is often decisive. In a limit, the sign of
\[ B_t(x)-W_t(x) \]
can depend on \(O(1/N)\) microscopic perturbations and on the order of individual updates. There is no canonical continuum version of “reachable optimistic stable endpoint” without adding a convention about update rates, chunk sizes, or limits over \(N\). Those are substantive modelling choices, not harmless tie-breaking repairs.
This also breaks the specific anchor. Observation 1 and Proposition 2 work because a target-set choice is atomic: bribing one vertex makes that vertex black, and the dummy and stabilizer gadgets are calibrated to whole vertices crossing whole thresholds. In the proposed model, \(b_t\in[0,\mu_t]\) permits a campaign to split its bribe mass across many types. A gadget can be partially activated, and the correspondence \(k=h\) disappears. Requiring an entire type to be bribed restores the reduction only by replacing mass intervention with an indivisible type-selection action; that is a weighted target-set problem, not the proposed continuous bribery problem.
The best repair would be to define the continuum as the exact limit of finite block blow-ups and quantify over all sufficiently large denominators. But then one gets one of two outcomes. If individual updates are retained, the answer depends on microscopic schedules and threshold margins. If mass updates are adopted, the result is a new mean-field/block opinion-dynamics problem. It may be interesting, but Corollary 1 and Proposition 2 no longer provide its computational content. The same objection applies to the proposed continuous link-control follow-up: a “mass of edges” requires a new exposure-capacity model rather than a population version of deleting edges.
This is not an identity-based objection: total black mass is plainly a meaningful objective, and a platform with large exposure cohorts is a plausible application. A complete block network with rational masses could be a legitimate new ChoCo problem. That concession is important. It means the universal claim that no worthwhile scenario exists is not honestly airtight.
The defensible negative verdict is narrower: the proponent has not produced a faithful continuous mirror of the paper’s named hardness result. The stated model loses closure under asynchronous updates, while the repairs either change the diffusion process or abandon fractional population intervention. Thus Corollary 1 does not currently support a green mirror; the case against is strong as a critique of this anchor, but weak as a universal claim against every possible population model of opinion diffusion.
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.