| paper | d4-journals-jair-2026-0049 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: Yes. A deterministic algorithm running in time polynomial in \(\tau\), \(L\), and \(1/\epsilon\) returns a feasible rational allocation \(d\) satisfying \(\Phi_K(d)\ge(1-1/e-\epsilon)\mathrm{OPT}\). · discrete side: other · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 4
statement extracted from the paper’s text layer
Given \(\tau\) types with rational masses \(\mu_t>0\) summing to \(1\), a rational type-to-type contact-rate kernel \(K\), and a per-capita budget \(\kappa\), choose type-level seed probabilities \(d_t\in[0,1]\) with \(\sum_t\mu_t d_t\le\kappa\) to maximize limiting active mass \(\Phi_K(d)=\sum_t\mu_t a_t^{(\infty)}\), where \(a_t^{(0)}=d_t\) and \(a_t^{(r+1)}=1-(1-d_t)\exp(-\sum_s\mu_sK_{st}a_s^{(r)})\). Does there exist an algorithm, polynomial in \(\tau\), input bit length \(L\), and \(1/\epsilon\), that returns a feasible rational \(d\) with value at least \((1-1/e-\epsilon)\) times optimum?
A large sparse stochastic-block social network with \(\tau\) exchangeable user types, masses \(\mu_t\), and contact rates \(K_{st}/N\) from type \(s\) to type \(t\) as population size \(N\) grows. With a common per-user sponsorship cost, choose the initial activation probability \(d_t\) for each type under a per-capita budget; maximize the resulting limiting fraction of active users.
The mirror covers the FIM approximation result in Theorem 4; it leaves aside the optimal-solution characterization, budget-selection and profit procedures, experiments, and the paper's proposed future variants.
The strongest mirror I see is a typed population version of fractional influence maximization. The paper already makes each user’s incentive continuous, but its society is still a finite list of named network nodes. That is continuous action space, not a continuous population. The mirror would replace the node list with masses of exchangeable users while preserving the paper’s central question: how to spend an incentive budget to maximize expected spread.
Here is a concrete model. There are \(\tau\) user types, with rational masses \(\mu_t\ge 0\) summing to \(1\). A type records everything the influence model uses: sponsorship cost and its contact rates with every other type. Let \(K_{st}\) describe type \(s\)’s contact rate with type \(t\). One finite-population interpretation is a network of \(N\) users, about \(N\mu_t\) of type \(t\), where a directed contact from a type-\(s\) user to a type-\(t\) user occurs with probability \(K_{st}/N\). Thus \(N\) can be very large while \(\tau\) stays small.
The decision is a seed mass \(z_t\in[0,\mu_t]\) for each type. Equivalently, \(d_t=z_t/\mu_t\) is the incentive or initial activation probability applied to type \(t\). With per-capita budget \(\kappa\), feasibility is \(\sum_t z_t=\sum_t\mu_t d_t\le\kappa\). Define \(a_t^{(0)}=d_t\), and for rounds \(r\ge 0\) define
\[
a_t^{(r+1)}
=1-(1-d_t)\exp\!\left(-\sum_s\mu_sK_{st}a_s^{(r)}\right).
\]
The objective is the final active population mass,
\[
\Phi_K(d)=\sum_t\mu_t\lim_{r\to\infty}a_t^{(r)}.
\]
This specifies a finite-input optimization problem: given \((T,\mu,K,\kappa,\epsilon)\), return a feasible rational \(d\) with
\[
\Phi_K(d)\ge (1-1/e-\epsilon)
\max_{\substack{d'\in[0,1]^\tau\\ \sum_t\mu_td'_t\le\kappa}}
\Phi_K(d').
\]
The complexity question is whether this guarantee can be achieved in time polynomial in \(\tau\), the input bit length \(L\), and \(1/\epsilon\), with the typed diffusion objective evaluated from the supplied kernel. Normalizing the budget and spread by \(N\), and scaling contact probabilities with population size, are co-modifications needed for this population limit.
A plausible regime is a very large platform with a small number of standardized audience roles or community cohorts. There may be millions of users but only tens or hundreds of types; users within a type have the same sponsorship terms and contact-rate profile, and individual links are stochastic realizations of those shared rates. That makes a type a complete description for this model and makes the mass of a type meaningful. It is one instance regime, not a claim that arbitrary social networks have low type diversity.
My anchor is Theorem 4, proved in this paper. It states that MLE-Greedy is a \((1-1/e)\)-factor approximation for FIM: for a real budget \(k\), it combines nested discrete influence-maximization solutions at budgets \(\lfloor k\rfloor\) and \(\lfloor k\rfloor+1\), and its multilinear-extension value is at least \(1-1/e\) times the FIM optimum. The paper proves this result here, deriving it from the nested discrete solutions and the piecewise-linear path argument. The paper’s NP-hardness statement for DIM is background attributed to Kempe et al.; it is not a numbered computational theorem in this paper, so I would not use it as another anchor.
I expect the typed approximation question to be Class A for approximation, though that is a prediction for the mirror, not a consequence already proved by Theorem 4. The anchor gives a close algorithmic precedent, and the typed objective aggregates a monotone influence process into \(\tau\) mass variables. A prover could investigate whether that diminishing-returns structure and efficient evaluation from \(K\) yield the stated guarantee. Exact optimization, or improved guarantees as \(\tau\) grows, could have a different complexity. This case covers only the paper’s budgeted expected-spread problem and its approximation result; it does not claim mirrors for its budget-selection, profit, competitive, online, or fairness variants.
The weakest point is the loss of individual network topology. The paper’s theorem calls a discrete influence-maximization oracle over named nodes; it does not establish a polynomial-in-\(\tau\) algorithm for this typed limit, and its guarantee does not automatically transfer to the restricted type model. In many observed networks, two users with the same broad role can still have very different influence because of their particular neighbors. That makes this a credible mirror for exchangeable large-population regimes, but not a faithful replacement for every network the paper studies. The case survives because the paper’s problem itself is expected spread under partial incentives, and the typed model preserves that problem while making the population—not merely the incentive vector—the continuous object.
Theorem 4 is a real computational anchor: it proves a \((1-1/e)\)-approximation for FIM. Its variables, however, are still the activation probabilities of the \(n\) named nodes, and its algorithm gets its nested solutions from a discrete influence-maximization oracle. The theorem does not show that the same guarantee, or an efficient algorithm, survives when the input is only a small collection of type masses.
The strongest objection is that compressing the population also compresses the graph. In the paper’s fixed-network model, cascade value depends on paths, overlaps, and bottlenecks. Two users with the same average contact rates can have very different effects when seeded. A type that captures all distinctions relevant to influence may therefore need to retain much of each node’s network position; for a general graph, the number of types can approach \(n\). A small type space avoids that growth by imposing an exchangeable or stochastic-block network model. That can be sensible, but it changes the instance regime and removes the realized topology that drives the paper’s targeting problem.
There is also a scaling problem for the paper’s prominent use case. Its large-network experiments use budgets up to \(20\) on graphs with as many as \(1{,}134{,}890\) nodes. With normalized population mass, a fixed number of seeds has mass \(O(1/n)\). In a supercritical sparse network, a single seed can still trigger a cascade affecting a positive fraction of the population with nonzero probability. Yet the zero-seed-mass mean-field recursion has the zero solution, so that limit can lose the effect the discrete objective measures. A positive per-capita budget \(\kappa\) avoids this degeneration, but it studies budgets of order \(n\), a materially different regime.
The proponent’s best repair is a typed random-network model with positive per-capita budget. That is a plausible computational question about optimizing a mass-action cascade. But Theorem 4 supplies little of its algorithmic answer: the mirror would need to optimize a type-level fixed-point objective, and the paper’s argument based on adjacent integer budgets and nested node sets does not directly apply to uniform incentives within types. The cited continuous influence work does not settle this objection either; those models continuousize incentives while retaining a finite population.
So my negative case is a prioritization argument: preserving the paper’s fixed-network targeting problem appears to require many types, while a compact type model changes it into mean-field cascade optimization. That makes the theorem a weak foundation for this particular mirror. It does not, however, defeat the proposed positive-density typed model as a worthwhile problem in its own right. I cannot honestly rule out every plausible scenario; the universal negative is weak precisely at that point.
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.