| paper | d4-conf-ijcai-2017-0529 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→other discrete result → its continuous mirror
Answer: Yes. The rational cap \(h=\min\{1,\alpha b\}\) gives a finite exact mass-flow implementation satisfying \(F(\pi)\geq\alpha(1-e^{-1/\alpha})\operatorname{OPT}\), hence also the requested bound with \(-\varepsilon\). An achievable exact running time is \(2^{O(m^2)}\operatorname{poly}(m,\tau,L,1/h)\), where \(m=\tau=q\). · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 2
statement extracted from the paper’s text layer
Given a finite directed template \(H=(U,E)\) with \(q=|U|\), rational IC edge probabilities, and a rational budget \(b\), consider a continuum of independent copies indexed by \(x\in[0,1]\). Each role \(u\in U\) has normalized mass \(1/q\) per copy, and \(H\) specifies the ties within each copy. A policy chooses role seeds in copies based on the paper's partial edge feedback, with \(\int_0^1 |S_x|\,dx\le b\) on every realization, and maximizes \(F(\pi)=\frac1q\mathbb{E}[\int_0^1\sum_{u\in U}\mathbf{1}\{u\text{ is eventually active in copy }x\}\,dx]\). Does a mass version of the paper's α-greedy policy attain \(F(\pi)\ge\alpha(1-e^{-1/\alpha})\operatorname{OPT}-\varepsilon\), and can such a policy be represented and computed from finite module and feedback-history data?
A continuum of repeated finite IC network modules, with a fixed directed template \(H\) encoding within-module ties, role masses \(\mu_u=1/q\), and decisions assigning seed mass across module histories under a pathwise average budget. The objective is normalized expected active mass; module structure is retained because role frequencies alone do not describe the graph.
The mirror needs the fixed within-module graph and module-level feedback histories in addition to role masses, so it covers repeated modular networks rather than societies described by type frequencies alone; the proponent already specifies this fixed-template regime.
fatal: False
Covers Theorem 2's uniform-cost α-greedy guarantee for repeated modules; leaves the nonuniform-cost results, estimation refinements, other feedback settings, and experiments outside the mirror.
The best mirror I see is a high multiplicity regime of partial feedback influence maximization: many structurally identical local communities, each with the same small network template. This is specialized, but it keeps the paper’s central problem intact: choose seeds under a budget, observe partial diffusion, and decide when to seed again.
My anchor is Theorem 2, proved in this paper. For the independent cascade model with uniform seed costs, budget \(B\), and partial feedback parameter \(0<\alpha\le1\), it proves that the paper’s \(\alpha\)-greedy policy \(\pi^u\) achieves
\[
f(\pi^u)\ge \alpha(1-e^{-1/\alpha})f(\pi^*),
\]
where \(f\) is expected cascade and \(\pi^*\) is the optimal adaptive policy. This is an approximation guarantee, not a result that the problem is in P: the paper’s later discussion says exact cascade computations can be #P-hard and considers inaccurate estimates. I would not present Theorem 2 as proving polynomial-time solvability.
Here is the continuous problem I would hand to a prover. Let \(H=(U,E)\) be a finite directed template network with rational independent-cascade probabilities, \(|U|=q\), and uniform seed costs. A unit interval of communities \(x\in[0,1]\) each contains one copy of \(H\); diffusion realizations are independent between communities. A type is a role \(u\in U\) in the template, including its network position and incident propagation parameters. Thus each type has population mass \(\mu_u=1/q\), while the number \(K\) of communities can grow far beyond \(q\). A rational budget \(b\) means at most \(b\) seeds per community on average: in the \(K\)-copy finite instance the budget is \(B_K=\lfloor bK\rfloor\).
A policy may wait or choose measurable sets of communities in which to seed particular roles. Its choices may depend on the partial diffusion feedback available in each community, using the paper’s rule for which edge states are revealed after each slot. The pathwise total seed mass is at most \(b\). Its objective is
\[
F(\pi)=\frac1q\mathbb E\!\left[\int_0^1\sum_{u\in U}
\mathbf 1\{u\text{ is eventually active in community }x\}\,dx\right].
\]
The task is to compute the supremum of \(F(\pi)\) over these policies, or to return a policy with value at least \(\alpha(1-e^{-1/\alpha})\operatorname{OPT}-\varepsilon\). A mass version of the paper’s greedy rule waits until the integrated average activation probability among roles with nonzero activation probability reaches \(\alpha\), then seeds role mass with maximum expected marginal cascade.
This seems like a question the authors would recognize: it retains their IC dynamics, expected-cascade objective, seed budget, and partial feedback, while scaling a finite network into a society with few repeated types. It also has a plausible setting: a campaign across many similar chapters, branches, or local online communities, with role-specific interaction patterns. The continuous question covers Theorem 2’s uniform-cost result, not the paper’s entire range of discussion.
For the approximation question, I expect a Class A style outcome: the finite \(K\)-copy graphs are instances of the paper’s model, so Theorem 2 gives the same ratio for each \(K\), and the normalized guarantee should carry to a suitable limit. That does not settle the bit complexity of computing the mass policy. Whether its marginal choices can be computed efficiently, and whether exact optimization retains hardness from the template network, are further questions.
The weakest point is the replicated-template assumption. Real social networks often have idiosyncratic ties, and representing each distinct neighborhood as a separate type could make the support grow with the population. This mirror is convincing only in the narrower regime where many people occupy a relatively small set of repeated network roles; it should not be sold as a model of arbitrary social graphs.
The sole anchor is Theorem 2, so I can’t make the decisive case that the paper has no computational result to mirror. It proves a genuine approximation guarantee for \(\alpha\)-greedy partial-feedback influence maximization. The strongest objection is that the paper’s computational object is a network, not a population described by type masses.
A mass \(\mu_t\) for each role in a replicated template does not say which agents are connected. In the proposed \(K\)-copy construction, two agents of roles \(u\) and \(v\) interact only when they belong to the same copy. Keep only the role masses and that relationship disappears. Add copy identity to each type, and the support grows with \(K\), so it is no longer the fixed, small type support that makes high multiplicity useful. The problem is especially acute here because partial feedback consists of observations of particular edges and their reachable neighborhoods; those histories are relational too.
The best repair is to model a continuum of finite network modules and track the distribution of their local states and feedback histories. That is coherent, and the finite \(K\)-copy theorem gives it a clear starting point. But its continuum objects are modules or module states, not masses of interchangeable individual agents. A richer version could instead specify how types connect. Dense type-based networks risk making each seed affect a macroscopic fraction of society, washing out the paper’s seed-by-seed feedback tradeoff; sparse networks preserve local cascades but require neighborhood structure and histories beyond type frequencies. Either route may be worth studying, but neither is a direct continuization of the paper’s graph input.
That leaves a real negative case against this particular mirror: the replica construction needs extra relational structure that a type distribution does not carry, and its cleanest repair changes the population unit. But I would not claim the universal negative is strong. A continuum model of many repeated local networks—or a suitable sparse-network limit—could be a worthwhile computational problem that the authors would recognize. The objection weakens the proposed anchor; it does not establish that no worthwhile continuous mirror exists.
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.