| paper | From Market Saturation to Social Reinforcement: Understanding the Impact of Non-Linearity in Information Diffusion Models |
| authors | — |
| venue | AAMAS 2024 |
| filed under | unclassified |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | no |
The paper contains no numbered result asserting algorithmic tractability, hardness, approximation, or parameterized complexity, so bit (a) fails. The proposed \(N\)-scaled birth–death chain retains individual-sized jumps and finite-population extinction; its deterministic mass limit has no finite-time extinction. Thus the proposal is a new stochastic-process problem, not a surviving continuous-population mirror.
fails bit a — no named computational result to mirror
The proposed construction addresses only the clique threshold bounds in Corollaries 7 and 10; it does not cover the star result or provide a computational restatement of any numbered theorem.
The strict answer is that this paper has no qualifying computational anchor. Its named results—Theorems 5 and 6, Corollaries 7 and 10, Lemmas 8 and 9, and Corollary 16—are asymptotic probability and survival-time bounds, not results saying that a problem is in \(P\), NP-hard, FPT, or similar. Theorem 1 is gambler’s ruin cited from [5], and Theorems 2–4 are standard probabilistic tools cited from [20]. None defines a computational input/output problem. Thus, under the programme’s literal anchor rule, I cannot honestly present this as a paper with a proved ChoCo complexity result.
The strongest substantive positive case is nevertheless a plausible new computational mirror of the paper’s clique thresholds. I would lead with Corollary 10, proved in this paper from Lemmas 8 and 9.
Consider a very large online community whose users have identical exposure: every user can influence every other user, all users have the same recovery rate, and all use the same nonlinear infection coefficient \(\lambda\) and exponent \(\alpha>0\). The permanent structural type is therefore simply “member of this clique”; the dynamic state is susceptible or infected. A society is represented by the mass vector \(\mu=(\mu_S,\mu_I)\), where \(\mu_I\) is the infected fraction. The regime is genuinely high-multiplicity: \(N\) is huge while the number of structural types is one, or two if state is included.
To preserve the stochastic extinction event, use \(N\) as a population intensity rather than as a list of named individuals. Starting from \(I_0=N\mu_I\) infected agents, define the mass process \(X_t=I_t/N\), with transitions
\[ i\longrightarrow i+1 \quad\text{at rate}\quad (N-i)\lambda i^{1+\alpha}, \]
and
\[ i\longrightarrow i-1 \quad\text{at rate}\quad i. \]
Let \(T_0=\inf\{t:I_t=0\}\). The problem \(\mathrm{Clique\text{-}Mass\text{-}Survival}_\infty\) is:
Given rational \(N,\lambda,\alpha,\mu_I\), and a threshold \(H\), decide whether \(\mathbb{E}[T_0]\ge H\). Equivalently, with \(\lambda\) as the controllable campaign intensity, compute the minimum \(\lambda\) that guarantees \(\mathbb{E}[T_0]\ge H\).
This is recognisably the paper’s problem: the infection rule, recovery rule, clique interaction, extinction event, and nonlinear exponent are unchanged. Rational mass instances also have an exact high-multiplicity bridge: clearing denominators produces the corresponding population of exchangeable clones, and every finite clique process is representable this way.
For the Corollary 10 regime, the expected direction is Class A for a promised threshold or approximation version. The state space is one-dimensional, and the hitting-time calculation reduces to explicit birth–death products of exactly the sort exploited in the paper’s gambler’s-ruin arguments. Corollary 10 supplies the asymptotic benchmark:
\[ \lambda\in\omega\!\left(N^{-1-\alpha}\log(N)^\alpha\right) \]
gives exponential expected survival, whereas
\[ \lambda\in o\!\left(N^{-1-\alpha}\right) \]
gives constant expected survival. A natural research question is whether this gap can be algorithmically closed in time polynomial in \(\log N\) and the input bit-length, rather than by an \(O(N)\)-state dynamic programme.
A second, weaker mirror uses Corollary 7, also proved here, for \(\alpha\in(-1,0)\). It is the same formally specified problem, restricted to the sublinear regime, with the promised alternatives
\[ \lambda\in\omega\!\left(\frac{\log(N)^{-\alpha}}{N}\right) \]
for super-polynomial survival and
\[ \lambda\in O\!\left(\frac{1}{N}\right) \]
for constant survival. This should be viewed as a second scientific anchor, not a computational one.
I would not anchor on Corollary 16. A star has a unique center, so a normalized population limit makes the structurally essential center have vanishing mass. Repeating many stars creates a different process, and giving the center positive mass changes the interaction pattern.
The weakest point is decisive: the paper’s phenomenon depends on finite-population fluctuations, especially the rare event of escaping the repelling equilibrium in Corollary 10. A genuinely atomless deterministic mass process does not have the same extinction event or rare-crossing probability. Keeping \(N\) restores fidelity, but makes the construction a stochastic high-multiplicity family rather than a pure atomless continuum.
So the honest verdict is: there is a credible Class-A research problem inspired directly by Corollaries 7 and 10, with an especially clean clique regime, but this paper itself contains no named computational result to anchor a formal ChoCo case.
The proponent’s opening concession is decisive under ChoCo’s stated anchor rule. The paper contains no computational result to continuize. Theorem 5, Theorem 6, Corollary 7, Lemma 8, Lemma 9, Corollary 10, and Corollary 16 are asymptotic bounds on a stochastic process. None defines an algorithmic input, output, decision problem, optimization problem, or complexity classification. The proposed computational problems are new wrappers invented after the fact.
The clique construction based on Corollary 10 also fails as a continuous-population mirror for a more substantive reason. Writing \(X_t=I_t/N\) does not continuize the process: the underlying chain remains the integer-valued process \(I_t\in\{0,\ldots,N\}\), and its extinction event depends entirely on the unit of one individual. The paper starts with \(I_0=1\), which becomes \(X_0=1/N\) and disappears in the population limit. The rare escape from the repelling equilibrium is precisely a finite-population fluctuation at this microscopic scale.
The natural density scaling makes the problem’s degeneration explicit. Since the total infection rate is \((N-i)\lambda i^{1+\alpha}\), setting \(\lambda=\beta N^{-(1+\alpha)}\) yields the limiting mass equation
\[ \dot{x}=\beta(1-x)x^{1+\alpha}-x. \]
For every \(x_0>0\), this deterministic process remains positive at every finite time; near zero its decay is at most exponential. Thus the paper’s extinction time is infinite in the continuum, while \(x_0=0\) remains extinct forever. The continuum survival question is therefore trivial. If one instead defines extinction as reaching a cutoff such as \(1/N\), then \(N\) has been reintroduced as the microscopic resolution, and the model is again the original finite chain in normalized notation.
Corollary 7 has the same defect, not an independent rescue. Its interesting regime concerns an attracting equilibrium and an initial infection count of one, with the relevant equilibrium still sublinear in \(N\). Both the seed and the entire threshold phenomenon have vanishing mass. A positive-mass initial condition does not represent the theorem’s process; it places the continuum outside the boundary layer where the result lives.
The suggested “minimum \(\lambda\)” problem does not repair this. \(\lambda\) is a physical parameter in the paper, not a campaign action or computational control variable. One can of course optimize over it, but that merely creates a new succinct birth–death-chain problem. Clearing denominators establishes equivalence with a finite population; it does not establish a continuous relaxation. The essential randomness still comes from individual-level jumps of size \(1/N\).
No alternative type space solves this while preserving the result. Replicating many identical cliques removes the single global extinction event or introduces a second population-size parameter. Replacing the clique by a continuum of agents removes the finite-size fluctuation that produces the threshold. Retaining a finite stochastic seed or cutoff produces a hybrid finite-population model rather than a continuous society.
There may well be a worthwhile paper on computing extinction expectations for succinctly represented nonlinear birth–death chains. But that would belong to stochastic-process or succinct Markov-chain complexity, not to ChoCo’s programme of computational questions over a continuous population. The strongest possible mirror therefore either loses the paper’s phenomenon in the continuum or retains \(N\) and ceases to be a continuous mirror.
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.