| paper | Opinion Diffusion and Campaigning on Society Graphs |
| authors | Piotr Faliszewski, Rica Gonen, Martin Koutecký, Nimrod Talmon |
| venue | IJCAI 2018 |
| filed under | frontier · opinion-networks |
| 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 · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given candidates \(C\), voter types \(T\) with complete rankings \(\rho_t\), a society graph \(G=(T,E)\), a rational distribution \(\mu\in\mathbb{Q}_{\ge 0}^{T}\) with \(\sum_{t\in T}\mu_t=1\), and target \(p\), repeatedly select a type \(t\) and, whenever a neighbor \(u\) satisfies \(\mu_u>\frac{1}{2}\sum_{z\in N[t]}\mu_z\), move all mass \(\mu_t\) to \(u\); decide whether some legal update order reaches a stabilized distribution \(\bar{\mu}\) in which \(p\) is a Plurality winner.
A finite-type nonatomic society in which each type \(t\) carries mass \(\mu_t\), the graph \(G\) governs type-level influence, the update schedule is the decision variable, and the objective is reachability of a stabilized state where \(p\) wins Plurality.
The mirror adds limited operational novelty because each diffusion move still transfers an entire type mass, so it is very close to the paper's weighted finite-type model.
fatal: False
The mirror directly covers Theorem 1 and Theorem 2's diffusion-control and campaigning results; it does not by itself settle the paper's generalized diffusion, convergence, or every bribery-variant claim.
The strongest mirror is the paper’s asynchronous diffusion-control problem itself, with integer voter counts replaced by population masses.
Call it Async-Plurality Reachability\(_\infty\). An instance consists of candidates \(C\), a finite set \(T\) of voter types, a ranking \(\rho_t\) for every \(t\in T\), a society graph \(G=(T,E)\), a rational mass vector \(\mu\in\mathbb{Q}_{\ge 0}^{T}\) with \(\sum_t\mu_t=1\), and a distinguished candidate \(p\). A type includes its ranking and its diffusion role; agents of one type are interchangeable.
An asynchronous diffusion move selects \(t\in T\). If some neighbor \(u\) satisfies
\[ \mu_u>\frac12\sum_{z\in N[t]}\mu_z, \]
then all mass at \(t\) adopts type \(u\):
\[ \mu_u\leftarrow \mu_u+\mu_t,\qquad \mu_t\leftarrow 0. \]
The process continues until it stabilizes. The question is whether there exists a legal update order whose converged society \(\bar\mu\) makes \(p\) a Plurality winner:
\[ \sum_{\rho_t(1)=p}\bar\mu_t \ge \sum_{\rho_t(1)=c}\bar\mu_t \qquad\text{for every }c\in C. \]
A solution is the update schedule. This is not a simplified opinion-diffusion problem: the graph, majority threshold, asynchronous order, convergence requirement, and plurality objective are exactly those of the paper.
The lead anchor is Theorem 1, proved in this paper by reduction from Partition. It states that, given a weighted society graph and a preferred candidate \(p\), deciding whether there is an order of asynchronous diffusion steps that results in \(p\) being a Plurality winner in the converged election is NP-hard.
The continuous version inherits this hardness exactly. Given the paper’s integer weights \(w_t\), set
\[ \mu_t=\frac{w_t}{\sum_{u\in T}w_u}. \]
Every strict-majority test and every plurality comparison is invariant under this normalization. Thus the Partition construction becomes a rational-mass instance in polynomial time, with the same yes/no answer. Conversely, every rational mass vector can be represented by a sufficiently large finite electorate using a common denominator. This gives the requested two-way high-multiplicity dictionary.
The natural regime is a large election composed of many stable blocs: for example, demographic or geographic cohorts whose members have the same ranking and respond identically to neighboring cohorts. The number of agents may be millions while the number of distinct cohort types is modest. The paper itself strongly supports this interpretation: it emphasizes arbitrarily many voters, weighted vertices, and an input size logarithmic in the total population. The continuous model merely removes an irrelevant absolute population scale.
I would classify this mirror as Class B: hardness transfers. The reduction’s combinatorics live in the diffusion-order choices and the candidate/type structure, not in the ability to distinguish individual voters. Continuization does not dissolve that hardness. It does, however, produce a clean computational problem over distributions and makes questions about parameterizing by the number of types, candidates, or graph structure natural.
A second useful anchor is Theorem 2, proved in the paper using an integer-programming formulation and Lenstra’s theorem. It states that synchronous \(R\)-BSG is fixed-parameter tractable with respect to the number \(m\) of candidates for every ILP-\(m\)-expressible voting rule \(R\); the paper explicitly notes that this includes Borda, all scoring rules, Bucklin, STV, Kemeny, and several other classes.
Its continuous counterpart is Synchronous \(R\)-Campaigning\(_\infty\). An instance consists of \(C,T,G,\rho,\mu,p\), together with a rational campaign budget \(B\). Let \(d_p(t,t')\) be the number of unit-cost upward shifts of \(p\) needed to transform ranking \(\rho_t\) into \(\rho_{t'}\), or \(+\infty\) if the transformation is not allowed. A campaign chooses masses \(x_{t,t'}\ge 0\) satisfying
\[ \sum_{t'}x_{t,t'}=\mu_t \]
for each \(t\). Its cost is
\[ \sum_{t,t'}d_p(t,t')x_{t,t'}. \]
The post-campaign mass of type \(t'\) is \(\tilde\mu_{t'}=\sum_t x_{t,t'}\). Synchronous diffusion is then run to convergence, and the question is whether some campaign of cost at most \(B\) makes \(p\) an \(R\)-winner.
For Borda, for example, the final winning condition is
\[ \sum_t\bar\mu_t\bigl(m-\operatorname{rank}_{\rho_t}(p)\bigr) \ge \sum_t\bar\mu_t\bigl(m-\operatorname{rank}_{\rho_t}(c)\bigr) \]
for every candidate \(c\).
I would expect this mirror to be Class A, parameterized by \(m\). The paper’s ILP has variables for bribery flows, diffusion states, and the discrete choice of which types assimilate at each step. In the mass version, the flow and state variables become rational continuous variables, while the assimilation choices remain binary. Since there are at most \(m!\) ranking types and at most \(m!\) diffusion steps in the basic model, the result is a mixed-integer linear program whose integer dimension depends only on \(m\). Establishing the precise fixed-parameter bit-complexity bound would be a follow-up theorem, but the paper supplies the right formulation and the right parameter.
This second mirror is also highly plausible to the authors: it preserves their actual campaign operation, their society graph, their diffusion process, and their voting rule. Only individual counts become masses, and the budget becomes a per-capita budget. It is therefore a genuine continuous-population version of their problem, not an unrelated fractional optimization exercise.
My weakest point is that the paper is already very close to a high-multiplicity model. Its weights are integer rather than real, and its main algorithms already exploit the fact that the population is represented compactly by type weights. Thus the continuous mirror may yield a formal relaxation more than a dramatic new model. Also, I would not claim that every hardness result survives: in particular, the discrete shift-bribery hardness behind Proposition 2 may weaken when a campaign can split a type’s mass fractionally. That is precisely an interesting question for the mirror, not a reason to reject it. Theorem 1 avoids this weakness because its hardness is carried by diffusion-order choices, which normalization preserves exactly.
The strongest negative case is that the proposed continuization adds little operational content. In Theorem 1, write \(W=\sum_t w_t\) and \(\mu_t=w_t/W\). Both the diffusion condition
\[ w_u>\frac12\sum_{z\in N[t]}w_z \]
and the final Plurality comparisons are invariant under this normalization. Every diffusion trajectory is therefore identical. More importantly, the dynamics still move an entire type at once: no submass can be selected, split, or independently influenced. The graph has finitely many type-vertices, and the meaningful choices are schedules of at most \(\tau\) type eliminations. The “population” is merely a collection of numerical weights used as capacities in a finite scheduling reduction. Replacing those weights by masses is thus a projective re-encoding of the paper’s weighted-graph problem, not a genuinely divisible population model.
One could make the continuum operational by allowing a fraction \(\lambda\in[0,1]\) of a type to assimilate at each step. But that would no longer be Theorem 1: it would require a new diffusion semantics, including rules for partial adoption, scheduling infinitesimal updates, and convergence. The paper gives no uniquely natural choice among these possibilities. Its hardness result therefore does not itself motivate a continuous computational problem; it only survives a normalization.
Theorem 2 is a better candidate, but the negative case is still that the paper has already done almost all the relevant compression. Its integer program represents societies by type weights encoded in binary, so the population-size dependence is already removed. Replacing the bribery variables by rational mass flows gives essentially the same formulation with continuous variables and type-dependent binary assimilation decisions. The resulting mixed-integer program is a sensible fractional-bribery variant, but its continuous aspect is confined to the campaign operation; the diffusion remains the same finite, all-or-nothing type process. It is therefore a fractional campaign problem on a compact weighted graph, rather than a new continuous-population theory.
This is not an objection based on the answer becoming easy or hard, and existing high-multiplicity work should indeed count in its favour rather than against it. The point is narrower: for this paper, the population axis is already almost entirely exhausted by the weighted-type representation, while the paper’s interesting combinatorics lie in finite diffusion schedules and candidate rankings. A continuous mirror would either be a scale normalization, or would require inventing a new partial-diffusion model whose connection to the paper is no longer exact.
That said, the universal negative case is weak. Theorem 1 is formally a valid rational-mass mirror, and Theorem 2 supports a genuinely natural fractional-campaign variant. I cannot honestly claim that no worthwhile continuous question exists here; the proponent’s first anchor survives the strongest objections.
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.