| paper | Viral Marketing and Convergence Properties in Generalised Voter Model |
| authors | Abhiram Manohara, Ahad N. Zehmakan |
| venue | IJCAI 2025 |
| filed under | unclassified |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 4.1
statement extracted from the paper’s text layer
Given rational \(q\), masses \(\mu_t\) with \(\sum_t\mu_t=1\), a row-stochastic role matrix \(P\), initial colours, stubbornness flags, horizon \(h\), and budget \(\alpha\), choose \(a_t\in[0,\mu_t]\) with \(\sum_t a_t\le\alpha\) to maximize \(F_h(a)=\sum_t\mu_t p^h_{t,b}(a)\). Seeding changes the initial distribution by \(a_t/\mu_t\); with \(\pi^s_{t,c}=\sum_uP_{tu}p^s_{u,c}\), each non-stubborn type follows the generalized voter recurrence, while stubborn types remain fixed. Determine exact and approximation complexity, including whether \(F_h(a)\) is continuously diminishing-returns submodular.
An exchangeable role-based mean-field society: type \(t\) has mass \(\mu_t\), initial colour, stubbornness and campaign eligibility, and samples types according to \(P_{t,\cdot}\). The decision variable is seeded mass \(a_t\), the dynamics are the mean-field generalized voter recurrence, and the objective is expected blue population mass \(F_h(a)\).
The finite blow-up does not exactly factorize node-state correlations at finite \(N\), and no rounding argument yet shows that fractional seeding preserves the Maximum Coverage gap or the submodularity theorem.
fatal: False
The mirror covers Section 4's Adoption Maximisation, including Theorem 4.1's inapproximability and Theorem 4.6's monotone-submodular structure. It leaves the Section 5 convergence-period and convergence-time results, including Theorem 5.1, outside the mirror.
The strongest honest positive case is for the paper’s Section 4, Adoption Maximisation. I would not try to mirror the finite Markov-chain convergence-period results: their state-space notion of period does not survive naturally in a continuum. My lead anchor is Theorem 4.1, an original result of this paper: it states that Adoption Maximisation has no polynomial-time \( (1-\frac1e+\varepsilon) \)-approximation unless \( \mathrm{NP}\subseteq\mathrm{DTIME}(n^{O(\log\log n)}) \). The proceedings version gives the proof sketch and points to the authors’ full version for details; this is not merely a theorem cited from elsewhere. The paper’s Theorem 4.6, proved in the paper, is useful supporting evidence: the same objective is monotone and submodular.
The mirror I would propose is Continuous Adoption Maximisation, or \( \mathrm{CAM}_\infty \).
A type is an exchangeable network role, not merely a colour. Let \( \mathcal T=\{1,\ldots,q\} \) be the types. Type \(t\) has mass \( \mu_t\), with \( \sum_t\mu_t=1\); an initial colour \(c_t\in\{r,b,u\}\); a stubbornness flag; and a row \(P_{t,\cdot}\) of a stochastic matrix. \(P_{tu}\) is the probability that a user of type \(t\) samples a user of type \(u\). Users of the same type therefore have the same weighted directed exposure profile, initial status, and campaign eligibility.
This is a genuine high-multiplicity regime. A finite realization has \(N_t\) users of type \(t\), with \( \mu_t=N_t/N\), and each type may have millions of users while \(q\ll N\). A plausible example is a large platform whose users fall into a few hundred or thousand stable behavioural and community roles. Within a role, users receive recommendations from the same mixture of roles, have the same initial product opinion, and have the same willingness to update. The marketing action is not “choose named vertices”; it is expose a mass of users in each role to the product.
The instance of \( \mathrm{CAM}_\infty \) consists of rational \( \mu_t\), \(P\), initial colours, a horizon \(h\), and a campaign budget \( \alpha\in[0,1]\). The decision variable is a vector \(a\), where \(a_t\in[0,\mu_t]\) is the mass of type \(t\) seeded blue at time \(0\), subject to \( \sum_t a_t\le\alpha\). Seeded users are not automatically stubborn, exactly as in the paper’s Adoption Maximisation problem.
Write \(p^s_{t,c}\) for the fraction of type \(t\) having colour \(c\) after round \(s\). If \(c_t=r\), then initially \(a_t/\mu_t\) of that type is blue and the remainder red; if \(c_t=u\), the remainder is uncoloured; if \(c_t=b\), the type is initially blue. For a non-stubborn type define \( \pi^s_{t,c}=\sum_uP_{tu}p^s_{u,c}\). The mean-field update is
\(p^{s+1}_{t,b}=p^s_{t,b}(1-\pi^s_{t,r})+(p^s_{t,r}+p^s_{t,u})\pi^s_{t,b}\),
\(p^{s+1}_{t,r}=p^s_{t,r}(1-\pi^s_{t,b})+(p^s_{t,b}+p^s_{t,u})\pi^s_{t,r}\),
and
\(p^{s+1}_{t,u}=p^s_{t,u}\pi^s_{t,u}\).
A stubborn type keeps its colour distribution unchanged. The objective is
\(F_h(a)=\sum_{t\in\mathcal T}\mu_t p^h_{t,b}(a)\).
Thus \( \mathrm{CAM}_\infty \) asks for a feasible mass vector \(a\) maximizing \(F_h(a)\). Its approximation version asks for a vector \( \widehat a \) satisfying \(F_h(\widehat a)\ge(1-\frac1e-\varepsilon)\operatorname{OPT}\). The input numbers are rational, and \(h\) can be given in unary or restricted to be polynomially bounded, matching the paper’s computational setting.
This is recognizably the authors’ problem. It preserves directed weighted influence, stubborn users, uncoloured users, simultaneous random updating, a finite propagation horizon, and a seed budget. Only the identity granularity changes. Formally, one can construct an \(M\)-fold blow-up of a type instance: replace type \(t\) by \(M\mu_t\) exchangeable copies, and give every copy of \(t\) total exposure \(P_{tu}\) to the copies of \(u\). As \(M\) grows, the empirical colour masses converge to the recurrence above. Conversely, a finite graph whose users occur in repeated network roles maps to \( \mu_t=N_t/N\), and a seed set maps to \(a_t=|A\cap t|/N\).
I expect this mirror to be Class B for exact optimization and for approximation beyond \(1-\frac1e\). The reduction behind Theorem 4.1 is from Maximum Coverage, and its essential combinatorics lie in the set/object incidence structure, not in the individuality of users. The continuous instance can retain one type for each set role and object role, with the repeated auxiliary nodes represented by high-multiplicity types. Equal type capacities and a budget corresponding to \(k\) set roles preserve the relevant choice among alternatives. The remaining technical task is a rounding lemma showing that fractional seeding across roles cannot beat the appropriate discrete coverage optimum; the monotone-submodular structure makes this plausible through dependent or pipage rounding.
Theorem 4.6 supports the algorithmic side independently. The natural mass objective is the exchangeable, multilinear extension of the paper’s finite objective. Hence it should remain monotone and exhibit the continuous diminishing-returns property needed by continuous greedy or type-level pipage rounding. The recurrence gives a value oracle in time polynomial in \(q\), \(h\), and the input bit-length, and automatic differentiation gives marginal information. The expected boundary is therefore the same as in the paper: a \(1-\frac1e\) approximation is available, while improving it would inherit the Maximum Coverage barrier. That is a meaningful computational mirror, not merely “the expected number of blue users is a fraction.”
This also generates concrete follow-up questions: can Theorem 4.1’s inapproximability be transferred formally to \( \mathrm{CAM}_\infty \); does continuous greedy achieve \(1-\frac1e\) in time polynomial in \(q\) rather than the total population; and what additive error results when a continuous solution is rounded to \(N_t\) discrete users? Parameterized questions in \(q\), the rank of \(P\), or the number of non-stubborn types are also natural.
The weakest point is that this mirror applies to a role-homogeneous network regime, not to an arbitrary graph. In a generic social network, every user may have a distinct neighbourhood profile, making \(q\) essentially \(N\) and eliminating the high-multiplicity gain. Moreover, the hardness transfer under genuinely fractional seeding still requires proof. But that is a precise technical and modelling obligation, not a reason to reject the mirror: massive platforms with repeated exposure roles are a plausible instance regime, and the paper’s own Maximum Coverage construction already exposes the role-level structure on which the continuous formulation rests.
The strongest negative case is that the proponent’s \( \mathrm{CAM}_\infty \) is not actually a high-multiplicity version of the paper’s graph process.
The paper’s dynamics are driven by individual network position, not merely by a node’s marginal distribution \(P_{t,\cdot}\). For a vertex \(v\) sampling \(w\), the probability of being blue at the next round contains terms such as
\[
\Pr(B_t(v)\land R_t(w))
\quad\text{and}\quad
\Pr(\neg B_t(v)\land B_t(w)).
\]
These are joint probabilities. In a fixed graph, the states of \(v\) and \(w\) can be correlated through their earlier interactions. The proposed type recurrence replaces these joint probabilities by products of marginals. That factorisation is justified only after imposing an additional propagation-of-chaos or random-mixing assumption. It is not a consequence of having many copies of the same graph role.
Thus a type containing only an initial colour, stubbornness flag, and row \(P_{t,\cdot}\) is not a complete type for the paper’s process. To preserve the dynamics exactly, the type must also encode the relevant neighbourhood overlaps, directed cycles, shared predecessors, and finite-horizon interaction structure. On generic graphs, this refinement produces essentially one type per vertex. Conversely, if one keeps \(q\ll N\), one has replaced the paper’s fixed network by a stochastic-block mean-field model. That may be a sensible new opinion-dynamics model, but it is not the continuous relaxation of the paper’s arbitrary-graph problem.
Theorem 4.1 does not repair this gap. It is a genuine computational anchor, so “the paper has no complexity result” is unavailable. But its Maximum Coverage reduction relies on choosing whole named set vertices. In the proposed model, a variable \(a_t\) can seed a fraction of a set type. Then coverage is no longer a Boolean event: every object receives a fractional adoption probability, and the support of \(a\) may contain every set. The paper’s decoding lemmas, which identify a seed set with a covered collection, no longer apply. The claimed transfer through dependent or pipage rounding is not automatic, because the mean-field recurrence has not been shown to be the multilinear extension of the finite set function.
Theorem 4.6 is likewise insufficient. It proves submodularity for adding individual vertices to a finite seed set. It does not prove diminishing returns for deterministic masses in the mean-field recurrence. One could instead define a randomized seed-set model whose objective is the multilinear extension, but that is a different stochastic relaxation, not the fixed mass of blue users proposed by the proponent. If one insists on whole-type campaigns to preserve the reduction, the decision variables become discrete again; \( \mu \) merely records how many users each selected role contains.
So the best negative conclusion is a dichotomy: preserving the graph semantics forces the number of types toward \(N\); preserving a small type space changes the process; preserving the hardness reduction makes the campaign discrete; allowing fractional campaigns destroys the reduction. That leaves no demonstrated mirror of Theorem 4.1 or 4.6 with all the claimed properties.
This case is not airtight, however. A deliberately role-homogeneous platform, where users genuinely sample fresh users from a small collection of behavioural roles, is a plausible mean-field model. In that restricted regime, mass seeding is meaningful and a new computational problem may well be worthwhile. The honest negative verdict is therefore not “no mirror exists,” but “the paper does not yet justify the proposed mirror, and its strongest theorem does not transfer without substantial new modelling and rounding results.”
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.