| paper | d4-conf-aaai-2021-0651 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
The repeated-module mass model is a plausible extension of the path-and-cycle setting and asks the same adaptive-versus-non-adaptive spread question. But Theorem 5 establishes only an optimum-value gap bound, so no anchor meets the required computational-result gate.
fails bit a — no named computational result to mirror
Theorem 5 compares mathrm{OPT}_A with mathrm{OPT}_N but gives no algorithm or complexity claim; this defeats the computational-result gate, and the proponent does not identify a computation asserted by the theorem.
fatal: True
The proposed mirror covers only the \(0\)-bounded path-or-cycle adaptivity-gap theorem; it leaves the in-arborescence, general-graph, and alpha-bounded results and the paper's proof techniques outside the mirror.
The strongest honest mirror I see is narrow: the path-and-cycle result, in a society made of many repeated local communities. That gives a real population limit while keeping the paper’s underlying question—how much full-adoption feedback improves influence spread—intact.
Take a finite menu \(\mathcal T\) of community templates. Each template \(t\) is a finite path or cycle with a specified independent-cascade probability for each directed edge. Let \(w_t\) be the mass of copies of template \(t\), and let \(Z=\sum_t w_t|V_t|\) be total agent mass. An agent’s type is its template and position within that template; its mass is \(w_t/Z\). Thus the number of agent types stays fixed as the population grows: if each community has at most \(r\) positions, then \(\tau\le r|\mathcal T|\), even as the number of people tends to infinity.
The continuous instance is \((\mathcal T,w,\kappa)\), where \(\kappa\in(0,1)\) is the fraction of the population available to seed. Each community has a local IC realization. When seed mass is assigned to a position in a community, full-adoption feedback reveals that seed’s complete reachable set in its community. The population is represented by masses of communities in each local history state; after a seed action, those masses split according to the IC probabilities. An adaptive solution is a policy for choosing seed mass by position and history, with total seed mass \(\kappa\). A non-adaptive solution assigns mass to fixed seed subsets before observing any cascades. In both cases the objective is expected activated agent mass, normalized by \(Z\).
This is a finite-state mass-flow optimization for fixed-size templates: its states are the possible local histories of seeded positions and observed reachable sets. The continuous problem, Cont-0B-AG, is to compute the ratio \(\mathrm{OPT}_{A,\infty}/\mathrm{OPT}_{N,\infty}\) for such an instance, and to determine whether its supremum over templates, masses, and \(\kappa\) is at most \(3e^3/(e^3-1)\). A solution is either a proof of that bound for the mass-flow model or a specified instance exceeding it.
My anchor is Theorem 5, proved in this paper, not cited as an external result. It states that for the independent-cascade model with full-adoption feedback on graphs whose undirected components are paths or cycles, and for every \(k\ge2\),
\[
AG(\mathcal G,k)\le
\min\left\{k,\frac{3}{1-(\max\{0,1-3/k\})^k}\right\}
\le \frac{3e^3}{e^3-1}\approx 3.16.
\]
The theorem is printed as Theorem 5 in the AAAI version, and its proof is in the paper’s appendix. [Theorem 5 in the AAAI proceedings paper](https://cdn.aaai.org/ojs/17433/17433-13-20927-1-2-20210518.pdf)
The regime is many repeated small referral chains or cycles: for \(N\) copies of the fixed templates, the population is \(n_N=N Z\), while the number of agent types remains at most \(r|\mathcal T|\). Set the discrete seed budget to \(k_N\approx\kappa n_N\). The theorem applies to every such finite replicated graph. The continuous question asks whether its bound carries to the limiting mass-flow values. That is a credible high-multiplicity mirror: types include the local position and edge-probability environment that matter to the problem; mass is population share; and seed budget and spread are both measured per capita. The authors should recognize the same IC process, feedback, objective, and adaptive-versus-non-adaptive comparison.
I expect the constant bound to survive. For a fixed template menu with bounded community size, the state-flow formulation is finite and can be optimized by LP; with growing template size, the state space and computational complexity need separate analysis. This is a narrow tractability case, not a claim that all influence maximization becomes easy. Further questions include whether the limiting gap is strictly below the theorem’s constant, how it depends on community size, and whether a comparable mirror works when communities have links between them.
The mirror covers Theorem 5 only. The paper supplies no named NP-hardness or standard complexity-classification anchor; this theorem is a bound on the adaptivity gap, not a running-time classification. Its relevance is the quantitative adaptive-versus-non-adaptive optimization result.
The weak point is the regime: it requires many repeated, disconnected path-or-cycle communities. That is plausible for repeated small local contact groups, but it does not represent a general connected social network. If the community templates grow with the population, their positions may become too numerous for a low-\(\tau\) description. That limits the scope of the positive case; it does not erase the mirror for repeated small communities.
The strongest objection is a mismatch between the paper’s result and the programme’s computational target. The \(0\)-bounded-graph theorem bounds a ratio of optimal values; it gives no algorithm for computing either optimum and makes no complexity claim. The proponent’s proposed question—prove the same bound for a limiting mass-flow model—is therefore another extremal-value theorem, not a continuous complexity result. One could instead ask how to compute the mass-flow optima, but that would be a new problem, not a mirror anchored by this paper’s Theorem 5.
The proposed population model also relies on a structural change. A distribution over vertex types does not specify which vertices are connected, yet those connections determine which cascades overlap and what full-adoption feedback reveals. In the repeated path-and-cycle construction, the missing information is supplied by grouping vertices into finite communities and tracking each community’s joint history. That may be a sensible model, but its continuous object is a population of stochastic network modules, not simply a society described by masses of agent types.
The best version of this mirror seems to face a tradeoff. Keep community templates bounded, and the local histories form a fixed finite state space: the result is a narrow fluid-control problem, with the programme’s broader algorithmic question still to be supplied. Let templates grow or communities interact to represent richer networks, and the state must retain more of the graph’s topology and correlated cascade information. A finite list of vertex-type masses no longer suffices; a richer graph-limit model is needed, and the proposed tractability story no longer follows.
That is a real case against *this paper* as a strong ChoCo target, but it does not defeat the anchor outright. Repeated independent referral chains are plausible, and a mass-flow model could preserve the adaptive-versus-non-adaptive comparison. The author would likely recognize that as their problem. So the honest negative case is limited: the paper supplies no computational-complexity result to mirror, and the strongest proposed mirror needs extra modeling and a new computational question. I cannot make a convincing universal case that no worthwhile continuous mirror exists in any scenario.
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.