| paper | Random Majority Opinion Diffusion: Stabilization Time, Absorbing States, and Influential Nodes |
| authors | — |
| venue | AAMAS 2023 |
| filed under | frontier · opinion-networks |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 3.2
statement extracted from the paper’s text layer
Given rational masses \(\mu_1,\ldots,\mu_\tau>0\) summing to \(1\) on communities arranged as \(C_\tau\), choose \(S\subseteq[\tau]\) minimizing \(\mu(S)=\sum_{i\in S}\mu_i\) such that forcing every resident in \(S\) blue, respectively white, makes synchronous MM reach the all-blue, respectively all-white, state for every initial assignment outside \(S\), where each community has one public color and retains it when its two neighbors tie.
A high-multiplicity viral-marketing model with \(\tau\) exchangeable community types, population masses \(\mu_i\), binary public states \(z_i\in\{b,w\}\), type-level campaign decisions \(S\), and objective \(\mu(S)\).
In the stated mirror, \(\mu_i\) affects only campaign cost, while the dynamics remain on \(\{b,w\}^\tau\); arbitrary within-community initial colorings are excluded, and the proposed fractional repair is not fully specified.
fatal: False
The mirror covers Theorem 3.2 and its weighted cycle extension, while leaving the stabilization, periodicity, stable-coloring, and random-initial-coloring results unmirrored.
The positive case is real, but narrow. The paper supports a strong mirror for its minimum-winning-set result; it does not support one for every stabilization or absorption theorem.
One qualification is important. The paper contains no numbered theorem asserting NP-hardness, membership in \(P\), W[1]-hardness, or FPT. Its NP-hardness and inapproximability statements in Section 1.3 are cited prose, not named results proved in the paper. The closest valid anchor is therefore the exact optimization result in Theorem 3.2, proved here (with the conference version giving a proof sketch and the complete proof referred to as [44]).
The lead mirror is Continuous Minimum Winning Mass on a Cycle, \(\textsc{CMWM}_{\infty}^{\mathrm{MM}}(C_\tau)\).
There are \(\tau\) local communities arranged on a cycle \(C_\tau\). Community \(i\) has rational population mass \(\mu_i>0\), with \(\sum_i\mu_i=1\). A type is a resident of a particular community, with the same two neighbouring communities, the same update rule, and the same campaign treatment. The current opinion is blue or white. The community-level state is \(z_i\in\{b,w\}\), and all residents of a community share its public opinion. In each synchronous round, community \(i\) adopts the majority opinion of communities \(i-1\) and \(i+1\), retaining \(z_i\) when those opinions differ.
A campaign chooses a set \(S\subseteq[\tau]\) of community types and forces all mass in \(S\) to be blue initially. The mass cost is \(\mu(S)=\sum_{i\in S}\mu_i\). The set is winning if, for every initial assignment of blue and white opinions outside \(S\), the process eventually reaches the all-blue state, and likewise reaches the all-white state when the types in \(S\) are forced white. The problem asks for a minimum-cost winning set \(S\).
This is a genuine high-multiplicity regime. If the masses have common denominator \(N\), community \(i\) represents \(N\mu_i\) exchangeable residents, with \(N\gg\tau\). A campaign cannot target one named resident; it buys the whole repeated type. Conversely, a finite population of repeated community cohorts collapses exactly to the rational vector \(\mu\). Thus the continuous input is not a fractional outcome assignment: the population itself is the distribution \(\mu\).
For uniform masses \(\mu_i=1/\tau\), this is exactly the cycle-level problem in Theorem 3.2. Its optimum is \((\lfloor\tau/2\rfloor+1)/\tau\). The extra \(1\) is essential when \(\tau\) is even: seeding exactly one alternating parity produces the blinking configuration rather than consensus. The theorem therefore gives a precise benchmark for the continuous problem, while nonuniform rational masses produce a natural weighted extension.
I expect the cycle version to be Class A. The paper’s structural proof identifies the only obstruction—the alternating configuration—and the weighted version should reduce to a small dynamic programme around the cycle, polynomial in \(\tau\) and the encoding length of the masses. The more general problem on an arbitrary type-influence graph is a different question: hardness may transfer from discrete dynamic-monopoly instances, placing that extension in Class B, while bounded-treewidth or highly repeated graph families may remain tractable.
The scenario is one the authors should recognise. It is viral marketing or political campaigning in a society of many recurring local communities: neighbourhoods, schools, workplaces, or online groups whose members have a common public opinion and common exposure pattern. The paper already motivates winning sets through exactly this kind of campaign. Replacing “\(547\) individually named vertices” by “\(0.5\%\) of the population in a community type” is a natural high-multiplicity interpretation, not a change to the outcome space.
The main weakness is the synchronization assumption. The original paper allows every node outside \(S\) to have an independently chosen colour. My lead mirror treats a community as the indivisible dynamic unit. If a real application permits arbitrary disagreement among the \(N\mu_i\) residents of one community, this model is too coarse. The natural repair is a fractional version with blue masses \(b_i\in[0,\mu_i]\), fractional seeding variables \(x_i\), and majority updates based on neighbouring blue mass. That is a worthwhile further problem, but Theorem 3.2 does not prove its complexity.
I would therefore not claim mirrors for Theorems 2.1, 2.5, 2.6, or Corollary 4.3 as primary anchors. Their exponential delays, absorbing states, and fixation probabilities depend on finite independent coin flips and last-particle events; those phenomena generally disappear in a deterministic continuum limit. Theorem 4.2’s martingale does have a formal mass analogue, but it is analytic rather than computational. The strongest honest positive claim is consequently: Theorem 3.2 yields a recognisable, precise, and plausibly tractable continuous population problem, covering the paper’s winning-set result and opening a substantive weighted and fractional research programme beyond it.
The strongest objection is that the proposed \(\textsc{CMWM}_{\infty}^{\mathrm{MM}}\) does not actually continuize the process studied in Theorem 3.2. In the paper, a node is both an individual and a unique position in the interaction graph. Its one-bit colour matters, and the winning-set quantifier ranges over every colouring of the other nodes. The proposed mirror replaces node \(i\) by mass \(\mu_i\), but then imposes a single community state \(z_i\) on that entire mass. The transition system is therefore still just \(F:\{b,w\}^{\tau}\to\{b,w\}^{\tau}\), completely independent of \(\mu\); \(\mu\) appears only in the campaign objective \(\sum_{i\in S}\mu_i\). For uniform masses, the result is literally the finite theorem divided by \(\tau\). For nonuniform masses, it is a weighted winning-set problem on the same finite cycle.
That is not merely a case where “continuity fails to help.” It means the population multiplicity has been removed from the dynamics. If \(\mu_i=a_i/N\) really represents \(a_i\) exchangeable residents, the high-multiplicity analogue must allow those residents to have different initial colours. Otherwise the mirror excludes precisely the microstates quantified over in the original winning-set definition. Exchangeability does not imply synchronisation. Synchronisation is an additional coordination assumption, and under it the population is only a price attached to a graph vertex.
The proposed repair—blue masses \(b_i\in[0,\mu_i]\) and fractional seeding—is more defensible, but it is no longer an anchored mirror of Theorem 3.2. One must newly specify whether neighbouring majorities compare absolute blue mass or blue proportions, how tied mass behaves, and how a continuum of residents is connected. A mass-majority rule gives a new fractional threshold dynamical system; independent microscopic updates give a mean-field limit; preserving the sparse cycle requires a nonstandard interaction kernel, since an ordinary graphon gives cycle edges measure zero. These are potentially interesting models, but each either returns to the finite weighted quotient or changes the state space and dynamics substantially.
Thus the paper provides no continuous computational result beyond a conjectural weighted reinterpretation of one closed-form theorem. The stabilization, absorption, and random-colouring results do not repair this gap: their relevant finite-particle phenomena were not claimed as mirrors by the proponent.
I would not claim the universal negative is airtight. If ChoCo accepts synchronised finite-type communities as a legitimate population model, then the weighted winning-set problem is a plausible narrow Class-A candidate. But under the stricter requirement that the population itself be continuized while preserving the paper’s individual network dynamics, the proposed anchor does not survive: it is either a finite graph problem with mass-weighted costs or a new opinion-diffusion model whose motivation must be supplied independently.
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.