| paper | d4-conf-atal-2020-0172 |
| 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: \(R=\frac12\). Acyclic instances with dyadic rational data have continuous greedy ratios arbitrarily close to \(\frac12\). · discrete side: other · adjudication: proved
full proof & adversarial review →
Corollary 5.3
statement extracted from the paper’s text layer
Given a finite type set \(T\), rational masses \(\mu_t\), message-specific contact rates \(\kappa_i(s,t)\), utilities satisfying \(\max(u_1,u_2)\le u_{1,2}\le u_1+u_2\), and a per-capita seed budget \(\beta\), determine the worst-case value ratio of marginal-gain greedy for maximizing the induced per-capita utility \(\Phi(x)\). Define the continuous greedy process as the limit of feasible mass-grid greedy allocations as the grid size tends to zero; is its infimum ratio \(1/2\), and can actual mean-field influence instances approach that ratio?
Types \(t\in T\) have masses \(\mu_t\); \(\kappa_i(s,t)\) gives message \(i\)’s contact rate from type \(s\) to type \(t\). Choose seed masses \(x_{t,i}\ge 0\) with \(x_{t,1}+x_{t,2}\le\mu_t\) and \(\sum_{t,i}x_{t,i}\le\beta\). The active masses follow the limiting cascade equation \(q_{t,i}=x_{t,i}+(\mu_t-x_{t,i})(1-\exp[-\sum_s\kappa_i(s,t)q_{s,i}])\); \(\Phi(x)\) is the expected per-capita utility from the two message activation states.
The proposed Poisson cohort process is not shown to arise as a limit of the paper’s arbitrary fixed-graph independent-cascade model, so the mirror depends on that separately specified instance regime.
fatal: False
The mirror covers greedy-ratio tightness for two-message UBIM under the paper’s utility condition; it leaves ETAB’s empirical comparisons and influence maximization on arbitrary fixed graphs outside the mirror.
The strongest positive mirror is a mean-field version of the paper’s two-message independent-cascade problem. There is no numbered NP-hardness, polynomial-time, or parameterized-complexity result in the paper to anchor; its numbered results concern approximation and structure. It cites the NP-hardness of ordinary discrete influence maximization as prior work [8], but that is not a numbered result of this paper.
A plausible high-multiplicity setting is a large platform campaign with many users in a modest number of recurring cohorts. A type records the user’s role and message-specific exposure rates to every other cohort; users of that type have the same utility and campaign eligibility. Think millions of users and dozens or hundreds of types. The campaign chooses shares of each type to seed with each message, under a budget that scales with population size. This preserves the paper’s central choice—how to divide seed resources between a viral, lower-utility message and a more effective one—while making the population the continuous object. The co-modification is the contact model: each active user has a bounded expected number of contacts as the population grows, described by rates between types.
Here is a concrete problem to give a prover. Call it Mean-Field UBIM. An instance has a finite type set \(T\), rational masses \(\mu_t\) summing to \(1\), rational message-specific contact rates \(\kappa_i(s,t)\) for \(i\in\{1,2\}\), utilities \(u_1,u_2,u_{1,2}\), and a per-capita seed budget \(\beta\). Assume \(\max(u_1,u_2)\le u_{1,2}\le u_1+u_2\), as in Theorem 5.1. The action is an allocation \(x_{t,i}\ge0\), with \(x_{t,1}+x_{t,2}\le\mu_t\) and \(\sum_{t,i}x_{t,i}\le\beta\). Thus no unit of population is seeded with both messages.
Define the limiting independent-cascade process by starting with \(q_{t,i}^{(0)}=x_{t,i}\) and iterating
\[
q_{t,i}^{(r+1)}
=x_{t,i}+(\mu_t-x_{t,i})
\left(1-\exp\left[-\sum_{s\in T}\kappa_i(s,t)q_{s,i}^{(r)}\right]\right).
\]
The limit \(q_{t,i}\) is the active mass of type \(t\) for message \(i\). For non-seeds of message \(i\), write \(\rho_{t,i}=(q_{t,i}-x_{t,i})/(\mu_t-x_{t,i})\), taking \(\rho_{t,i}=0\) if the denominator is zero. Let \(\Phi(x)\) be the per-capita expected utility: for each type, count the \(x_{t,1}\) mass as already active with message 1 and reached by message 2 with probability \(\rho_{t,2}\); count \(x_{t,2}\) symmetrically; and count the remaining mass with independent message-activation probabilities \(\rho_{t,1},\rho_{t,2}\), using utilities \(u_1,u_2,u_{1,2}\) for the resulting states. The problem is to return a feasible allocation with \(\Phi(x)\ge \tfrac12\operatorname{OPT}-\epsilon\), for a given rational \(\epsilon>0\), and classify its complexity in \(\tau=|T|\), input bit length \(L\), and \(1/\epsilon\).
My lead anchor is Theorem 5.1, proved in this paper. It says that when \(\max(u_1,u_2)\le u_{1,2}\le u_1+u_2\), the expected utility function \(\sigma(\cdot,\cdot)\) is monotone and bisubmodular for the paper’s two-message IC model. The authors then use this structure to obtain a greedy \(1/2\)-approximation. The continuous question is whether a comparable guarantee can be computed for Mean-Field UBIM. I expect the approximation guarantee to carry over through finite cohort approximations, making this a Class A approximation question. That expectation still leaves work: a proof must connect the limiting process to the finite models, and an algorithm must handle cascade evaluation in time polynomial in the stated parameters.
A second, narrower anchor is Corollary 5.3, also proved here. It says the greedy algorithm’s approximation ratio is tight: for every \(\epsilon>0\), there is a monotone bisubmodular instance on which greedy achieves at most \(1/2+\epsilon\) of optimum. Its proof uses the abstract construction from Lemma 5.2; the paper does not establish that the construction is realizable by an IC influence network. The corresponding continuous problem is: over Mean-Field UBIM instances, what is the worst-case ratio of infinitesimal marginal-gain greedy, defined as the limit of greedy allocations on increasingly fine mass grids? The output should be a universal guarantee and, for sharpness, a family of actual mean-field influence instances approaching it. I expect the \(1/2\) guarantee to survive; the paper’s generic tightness example alone does not settle whether that constant is sharp for this restricted network model.
The mirror covers the two-message UBIM objective and its utility condition, not every result or experiment in the paper. Its weakest point is the network abstraction: the authors allow arbitrary individual graphs, while this mirror assumes users within a type are exchangeable apart from type-to-type contact rates. That is a real restriction, and the authors might reject it if individual neighborhoods are essential in their intended applications. Still, a large-cohort campaign with stable exposure rates is a credible regime, and the population-scale budget makes the mass decision match how such a campaign would be described.
The strongest case against a ChoCo mirror is that the paper’s proved structure lives on a fixed graph, where each user’s identity and position can matter. In Theorem 5.1, the authors condition on a live-edge realization and compare the reachability sets \(A_1(S_1)\) and \(A_2(S_2)\). To preserve those sets exactly, a type must encode enough of the user’s network position and connections to determine its reachability effects. In a general social network, that can make the number of types grow with the population. Grouping users by degree or broad cohort is not enough: it can erase which paths overlap, which is central to influence.
The proposed repair—replace the graph with finitely many cohorts and type-to-type contact rates—is coherent, but it changes the network model. It also creates a delicate choice of limit. With a sublinear seed budget, the seeded fraction tends to zero, even though one seed in a supercritical sparse network can have positive expected spread as a fraction of the population. A deterministic mean-field equation initialized at zero gives no spread; taking positive seed fractions to zero can instead select a macroscopic cascade and omit the finite network’s chance of extinction. A positive per-capita seed budget avoids that mismatch, but studies a different budget regime. Near the cascade threshold, even that model can have a discontinuity as the seed fraction approaches zero. These are reasons the paper’s model does not single out one faithful continuous question.
They also limit what Theorem 5.1 provides. Its bisubmodularity argument may survive a carefully justified sequence of cohort models, since the finite-graph inequalities hold before taking a limit. If so, the \(1/2\) guarantee is largely inherited from the finite problems; it does not by itself produce a new complexity classification. The more ambitious question—optimizing mass allocations in the mean-field model—could be computationally interesting, but its difficulty would come from the chosen nonlinear epidemic model and its limit assumptions, not directly from the paper’s theorem.
Corollary 5.3 is a weaker anchor still. Its tight example is an abstract bisubmodular function, and the paper does not show that an influence network realizes it. A continuous claim about the sharp ratio for infinitesimal greedy therefore needs a separate construction within a specific network model. If that construction exists, it could be useful; the corollary alone gives no reason to expect it. The paper also has no numbered hardness or running-time result for UBIM: its formal algorithmic result is the approximation guarantee, while ETAB’s advantage is empirical.
I would vote against treating this as a strong paper-specific mirror, but the negative case is not airtight. A large platform with recurring cohorts, type-level contact rates, and a budget proportional to its population is plausible, and optimizing its two-message campaign is a recognizable computational question. I cannot honestly rule out that mirror; the case against it rests on the substantial modeling choices and the gap between the paper’s proved results and the resulting mean-field optimization problem.
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.