| paper | d4-conf-atal-2017-0235 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 1
statement extracted from the paper’s text layer
For a population with rational type masses \(\mu_r\), specify a directed sparse random network by giving each ordered pair of type-\(r\) and type-\(s\) agents an edge independently with probability \(\lambda_{rs}/N\), where \(N\) is population size and the rational contact rates \(\lambda_{rs}\) are bounded. Assign edges to a fixed finite set of tie categories, each with an uncertain propagation parameter \(\theta_j\in[a_j,b_j]\). Given a seeding budget \(\kappa\), a feasible action is a type-wise seed-mass profile \(z\) with \(0\le z_r\le\mu_r\) and \(\sum_r z_r\le\kappa\). Let \(g_\mu(z,\theta)\) be the limiting expected influenced mass after a fixed finite cascade horizon, and let \(g^G_\mu(\theta)\) be the corresponding type-wise greedy benchmark. Can one compute a finitely represented randomized strategy over feasible profiles with the \((1-1/e,\epsilon)\)-minimax guarantee of Theorem 1, in time polynomial in the number of types, input bit length, horizon, and \(1/\epsilon\), independently of \(N\)?
A typed sparse random network with population masses \(\mu_r\), contact rates \(\lambda_{rs}\), a constant number of edge categories with interval propagation parameters, and a fractional seeding budget. The decision is a lottery over type-wise seed-mass profiles; the objective is worst-case limiting expected cascade mass relative to the known-parameter greedy benchmark.
A role-pair contact rate does not determine spread because neighborhood overlap changes cascade outcomes; the mirror needs an explicit network model, such as a typed sparse random graph.
fatal: False
The mirror covers Theorem 1’s robust, single-stage seed-selection guarantee. It leaves aside the dynamic policy heuristic, execution-uncertainty extension, and experimental comparisons.
The strongest honest case is narrow and rests on the paper’s robust, non-dynamic result. The paper gives no numbered hardness theorem to anchor a continuum hardness question. Its NP-hardness discussion concerns classical influence maximization, while its named main result is an approximation algorithm.
Theorem 1, proved in this paper, says that robust influence maximization has an algorithm running in \(\mathrm{poly}(m,n,1/\epsilon)\) time that returns an \((1-1/e,\epsilon)\)-minimax robust solution. In the theorem’s setting, a fixed graph has \(n\) vertices and \(m\) edges, one chooses a seed set of size \(K\), and the edge-type propagation parameters lie in specified intervals. The algorithm returns a mixed strategy \(x\) over seed sets such that
\[
\min_{\theta}\sum_S x_S\,\mathrm{RG}(S,\theta)
\;\ge\;
(1-1/e)\max_{x'}\min_{\theta}\sum_S x'_S\,\mathrm{RG}(S,\theta)-\epsilon.
\]
Here \(\mathrm{RG}(S,\theta)=g_S(\theta)/g_G(\theta)\): the expected spread from \(S\), divided by the spread of the greedy solution for known \(\theta\). The result assumes a constant number of edge types and does not cover adaptive observations or execution uncertainty. It is an approximation guarantee against the best robust mixed strategy, not an exact solution benchmarked against the true optimum.
A plausible population regime is a large health or viral-marketing campaign across many similar communities. Each person has one of a small number \(\tau\) of contact roles—say, different peer-network roles with distinct rates of contact with each other role, tie categories, and intervention attendance or cost. A role therefore records everything the model uses about a person. There may be millions of people but only a handful of roles, with a known aggregate contact kernel between roles. Contacts are exchangeable within role pairs; the campaign has aggregate contact information, not an individually observed graph. That is a credible large-population version of the paper’s health-intervention setting, though not the small, individually surveyed shelter networks in its experiments.
I would pose the lead mirror as Robust Mass Influence Maximization. An instance consists of role masses \(\mu_r\in\mathbb{Q}_{\ge 0}\), summing to \(1\); a per-capita contact kernel between roles; a finite set \(\Theta\) of tie categories and an interval \([a_\theta,b_\theta]\) for each category’s propagation parameter; and a seeding budget \(\kappa\), a fraction of the population. Use the paper’s independent-cascade process on the exchangeable role network. A seed action is a mass profile \(z\) with \(0\le z_r\le\mu_r\) and \(\sum_r z_r\le\kappa\). Let \(g_\mu(z,\theta)\) be its expected final influenced mass in the large-population limit, and let \(g_{G,\mu}(\theta)\) be the mass reached by the corresponding continuous greedy procedure when \(\theta\) is known. A solution is a finitely represented randomized strategy \(x\) over feasible mass profiles satisfying the same \((1-1/e,\epsilon)\) guarantee as Theorem 1, with \(g_\mu(z,\theta)/g_{G,\mu}(\theta)\) in place of \(\mathrm{RG}(S,\theta)\). The question for a prover is whether this guarantee can be achieved in time polynomial in \(\tau\), the input bit length, the horizon, and \(1/\epsilon\), with no dependence on the population size.
I would expect this mirror to be Class A, subject to proof: the finite population problem has a diminishing-returns spread objective and the paper already obtains its robust guarantee through a greedy response and a discretized adversary. The continuum question is whether those ingredients extend to mass-seeding profiles and the limiting spread function. It is the population that has been continuized; the paper’s parameter uncertainty remains part of the problem.
This mirror covers Theorem 1’s robust, single-stage seed-selection result. It does not claim to mirror the paper’s dynamic policy experiments, its heuristic dynamic oracle, or its execution-uncertainty extension. It also raises useful follow-up questions: does continuous spread preserve the needed diminishing-returns property; can one bound the error between the mass model and finite exchangeable networks; and can any of the guarantee extend to adaptive observations?
The weak point is substantial: Theorem 1 operates on a known individual graph, where particular nodes and their locations in the network matter. Replacing that graph with a role-level contact kernel discards information and restricts campaigns to exchangeable populations. If the actual network must be observed and exploited, many people who look alike by role are not interchangeable, and the number of relevant types may grow with the population. So this is a convincing mirror only for the stated aggregate-network regime, not a continuous version of the theorem for arbitrary known graphs.
The proponent is right that Theorem 1 is the paper’s one serious computational anchor. The difficulty is that its input is a particular graph, and influence depends on how agents are connected inside that graph. A finite list of population roles and their masses does not generally preserve the object Theorem 1 operates on.
For example, consider two populations with one role: every agent has three outgoing contacts, all contacts have the same propagation parameter, and the same fraction \(\kappa\) is seeded. One network is a disjoint union of \(K_4\) components; the other is a large, high-girth 3-regular network. They have the same role mass and the same per-capita contact rate. With propagation probability \(1\) and two stages, uniformly seeded mass reaches a different fraction in the two networks: in the clique population the reached fraction tends to \(1-(1-\kappa)^4\); in the high-girth population it tends to \(1-(1-\kappa)^{10}\). The second network has more distinct vertices within distance two of each vertex. Thus the proposed role masses and contact kernel do not determine \(g_\mu(z,\theta)\), or its greedy benchmark. This is a failure to specify the mirror’s objective, not a concern about what its answer would be.
A more faithful type would have to record network position and its relevant neighborhood. For a short, fixed horizon, that may mean increasingly detailed neighborhood information; for arbitrary horizons and targeted seeding, it can mean essentially the whole network and the overlap between candidate seeds’ neighborhoods. The support then grows with the graph, so the high-multiplicity compression disappears. A graphon or other continuum network model can retain more structure, but it introduces a new network input. In the dense case, fixed positive edge probabilities and positive seed mass can make spread collapse rapidly; retaining sparse-network behavior requires a different scaling and more local structure. Either route may define worthwhile research, but neither is a direct high-multiplicity version of the paper’s fixed-graph theorem.
That makes the negative case strong against the proposed finite-role mirror and against a faithful, low-dimensional mirror of Theorem 1. It does not establish the universal claim that no scenario is worthwhile. Repeated, exchangeable communities could support a meaningful continuous influence model, and the paper’s theorem does not rule that out. The honest conclusion is narrower: the paper gives ChoCo a poor anchor unless the programme is willing to formulate a new network-limit model, with its own input representation and notion of type.
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.