| paper | d4-conf-aaai-2020-1175 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 3.1
Given a finite set of types \(T\) with rational shares \(\mu_t\), a block-structured cascade model with a finite shared environment \(\Omega\) and rational prior, a seeding budget \(\beta\), and \(q\) rounds, determine the infimum ratio of expected adopted mass under adaptive greedy to that under non-adaptive greedy. In each round, each policy chooses a type-mass vector \(\Delta x\geq 0\) with \(\sum_t\Delta x_t\leq\beta/q\) and \(x+\Delta x\leq\mu\), maximizing expected marginal adoption; adaptive greedy conditions on the observed type-level adoption profile under full feedback, or the type-level exposure profile under myopic feedback, while non-adaptive greedy uses the prior.
A repeated block-network population whose types encode shared network role, contact profile, seeding cost, response behavior, and feedback visibility; the decision variables are seeded masses \(x_t\), and the objective is expected total adopted mass under a finite shared platform environment.
The tight construction in Theorem 3.1 relies on an individual infection event, and the case does not show that shared environmental uncertainty in a block population preserves that construction or its sharp ratio.
fatal: False
The mirror covers Theorem 3.1's adaptive-greedy comparison and Theorem 5.2's non-adaptive approximation guarantee; it leaves the unbounded-gap results, other theoretical results, and experiments unmirrored.
The strongest positive mirror is large scale campaigning: millions of voters or platform users, grouped into a relatively small number of types that share the same targeting cost, response behaviour, contact profile, and feedback visibility. A campaign buys a fraction of each type, with a budget measured as a fraction of the population, and seeks to maximize the mass that adopts. This keeps the paper’s computational question—how adaptive greedy compares with non-adaptive greedy—while making the population itself continuous.
The paper does not prove a numbered P, NP-hardness, or parameterized-complexity result. Its \(\#P\)-hardness statement about evaluating influence is cited background in Section 5, not a numbered result proved here. My anchors are therefore named algorithmic and performance results.
The lead anchor is Theorem 3.1, proved in this paper from its tight examples and lower bound. It says that, under full-adoption feedback, the infimum of the ratio of adaptive-greedy influence to non-adaptive-greedy influence is exactly \(1-1/e\), separately for the independent cascade model, the linear threshold model, and the general triggering model. The same equalities hold under myopic feedback. The theorem’s entries for the independent cascade model alone are enough to motivate the mirror; the linear threshold and general-triggering entries show the breadth of the result.
Here is a continuous version of that question. Let \(T\) be a finite set of user types, with rational population shares \(\mu_t\) summing to \(1\). A type specifies everything relevant to seeding and spread: eligibility and cost, response behaviour, contact profile, and what feedback is observable. The regime is \(N\) users with \(\tau=|T|\) types, where \(N\) is in the millions and \(\tau\) is perhaps hundreds or thousands. For example, a political campaign might distinguish voters by preference, persuasion susceptibility, and exposure channel, while treating users within each group as interchangeable.
A continuous instance also specifies a finite latent set of platform or campaign environments \(\Omega\), with rational prior probabilities. For each \(\omega\in\Omega\), a type-level cascade map takes a seed-mass vector \(x\in[0,\mu]\) to the final adopted-mass profile \(R_\omega(x)\). The map is supplied by an explicit block cascade description and has the monotonicity and diminishing-returns properties inherited from the cascade model. A campaign has mass budget \(\beta\) and acts in \(q\) rounds, adding at most \(\beta/q\) mass per round. Full feedback reveals the adopted-mass profile by type; myopic feedback reveals the corresponding directly exposed or adopted masses. Thus a policy is a rule from its history of observed profiles to the next type to seed. A non-adaptive greedy schedule uses prior expected marginal gains and ignores feedback; an adaptive greedy policy uses the posterior expected marginal gains given its observations.
Call the resulting problem Type-Mass Greedy Adaptivity Gap. Given the type shares, cascade and feedback descriptions, latent environment distribution, budget, and number of rounds, its task is to return the two greedy policies and their expected adopted masses, and determine the infimum of their ratio over instances. I expect the \(1-1/e\) lower guarantee to survive as a Class A type result: the paper’s conditional-submodularity and telescoping argument has a natural diminishing-returns counterpart for mass allocations. I also think the exact infimum may remain \(1-1/e\) as the type support grows, but that is a conjecture, not something the finite-graph constructions establish automatically. Useful next questions are whether the sharp constant persists at fixed \(\tau\), and how it changes as the seed-mass increment shrinks.
A second anchor, Theorem 5.2, is also proved here. It states that for submodular influence maximization, if \(\varepsilon\leq 1/k\), an \((\varepsilon,\delta/k)\)-greedy algorithm produces a \((1-1/e-\varepsilon)\)-approximation to the optimal non-adaptive seed set with probability at least \(1-\delta\). This is an algorithmic guarantee, not a hardness result.
Its continuous mirror is Type-Mass Influence Approximation. The instance is the same finite type population, with seed-mass budget \(\beta\), but the task is non-adaptive: output an allocation \(x\in[0,\mu]\) with total mass at most \(\beta\) whose expected adoption is at least \((1-1/e-\varepsilon)\) times the best feasible allocation, with the requested success probability. The prover receives a type-level cascade evaluator or sampling oracle for marginal adoption. I expect this one to be Class A: greedy mass allocation should inherit the diminishing-returns guarantee, with the running time expressed in \(\tau\), the number of rounds, the evaluator’s cost, and the input bit length. The follow-up questions concern efficient estimation of marginal influence and how many samples are needed as the type support grows.
These mirrors stay within the population-continuity scope. They make user mass, seed budget, and adoption mass fractional; the campaign rounds remain discrete. They do not replace population continuity with fractional outcomes, stochastic ballots, or continuous time. The paper’s experiments and its other results need not be mirrored for this case to stand.
The weakest point is preserving the feedback that drives Theorem 3.1. In a continuum limit, independent edge randomness can average out, making aggregate adoption profiles nearly deterministic and leaving little for an adaptive policy to learn. The proposed model retains uncertainty through a shared latent campaign or platform environment, which makes aggregate feedback informative and is plausible for real campaigns. But that modification means the tight finite-network examples do not, by themselves, prove the continuous ratio is sharp. There is a related type-count issue: exact neighborhoods can make every node its own type. The positive case is strongest for block or platform-mediated networks where many users really do share contact and response profiles. Within that regime, the authors should recognize the mirror: it preserves their objective, seed budget, greedy rule, feedback distinction, and adaptive-versus-non-adaptive comparison, while asking how those questions change when the society is specified by type masses.
The strongest objection is representational. In this paper, a vertex is simultaneously a possible seed, a target of influence, and a coordinate of the feedback. Its value depends on its place in the network and on how its cascade overlaps with other vertices. To make agents of the same type interchangeable, a type would have to preserve those network roles. On general instances that can require essentially one type per vertex, so \(\tau\) grows with the population. Coarsening to a few demographic or exposure types loses precisely the overlap and reachability information that drives the greedy choices.
That problem is sharpest for Theorem 3.1. Its tight example turns on feedback about one vertex \(t\): whether \(s\) infected \(t\) changes which seed adaptive greedy chooses next. In a population limit with many interchangeable copies of \(t\), independent cascade outcomes aggregate: the observed infected mass concentrates, and the single-vertex branch that drives the construction no longer supplies the same persistent signal. A mean-field model with fixed type masses and independent individual randomness typically gives deterministic aggregate feedback. To retain informative uncertainty, the proposed mirror adds a shared latent environment or preserves a finite set of special hubs. Either may define a sensible model, but the uncertainty then comes from that added environment or those individually distinguished nodes, not from the high-multiplicity population in the paper. The finite-graph tight example does not establish the continuous ratio.
Theorem 5.2 is a less compelling anchor. It gives the familiar greedy approximation for a finite submodular influence function; it does not analyze the cost of evaluating influence, which the paper says is \(\#P\)-hard. If the proposed type-mass model supplies a diminishing-returns evaluator, the approximation guarantee follows from generic continuous allocation machinery, while the evaluator has hidden the influence-computation problem. If it supplies an explicit cascade representation instead, type masses alone do not specify the network information needed to evaluate marginal adoption. Either way, a continuous version needs a separate input model and complexity analysis before it says much about the paper’s computational bottleneck.
So the best negative case is that these anchors do not directly carry over: preserving the network structure defeats the small-support promise, while aggregating it risks removing the feedback signal or outsourcing the hard computation to an oracle. That is a strong objection to a straightforward mirror. It does not honestly prove the universal claim, though. A campaign over repeated network blocks with a plausible shared platform shock could make aggregate feedback informative and population mass meaningful. The supplied case identifies such a possibility, and the programme explicitly permits model co-modifications. The argument against is therefore weakest exactly where it must be strongest: ruling out every worthwhile block-population 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.