| paper | d4-conf-ijcai-2019-0712 |
| 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: A deterministic algorithm running in time \(\operatorname{poly}(m,\tau,L,1/\varepsilon)\) returns a rational budget-feasible vector satisfying all the requested \((1-1/e)\) multiplicative and \(\varepsilon\) additive guarantees. · discrete side: other · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 3.2
statement extracted from the paper’s text layer
Given rational type masses μ_t summing to \(1\), group memberships \(a_{gt}\), rational contact rates λ_{tu}, a seed budget β, and feasible group targets \(W_g\), choose seed fractions \(x_t\in[0,1]\) with \(\sum_t \mu_t x_t\le\beta\). Define \(z_t^{(0)}=x_t\), \(z_u^{(q+1)}=x_u+(1-x_u)(1-\exp(-\sum_t\mu_t\lambda_{tu}z_t^{(q)}))\), and \(\Phi_g(x)=\sum_t\mu_t a_{gt}z_t^{(\infty)}/\sum_t\mu_t a_{gt}\). Maximize \(\sum_t\mu_t z_t^{(\infty)}\) subject to \(\Phi_g(x)\ge W_g\); for additive error \(\varepsilon>0\), determine the complexity of returning an \(x\) with \(\Phi_g(x)\ge W_g-\varepsilon\) for every group and total influence within \(\varepsilon\) of optimum, as a function of \(\tau,r,L,1/\varepsilon\).
A type-mass block-contact model: each type \(t\) carries mass \(\mu_t\), has group memberships \(a_{gt}\), and contacts type \(u\) at rate \(\lambda_{tu}\). The decision is the seeded fraction \(x_t\); the cascade follows the stated mean-field recurrence, and the objective is total influenced mass subject to group influence targets.
The proposed mean-field influence objectives may not retain the submodularity that underlies Theorem 3.2, so its stated approximation guarantee may not apply.
fatal: False
The mirror covers the multiobjective fair seed-selection problem in Theorem 3.2, including group targets and total influence; it leaves the non-submodularity and price-of-fairness results in Theorems 3.1 and 4.1–4.4 aside.
The strongest honest case is a mirror of the paper’s multiobjective influence problem in a large, exchangeable population. Take a regional public-health outreach programme with many potential recipients but relatively few modeled types. A type records group memberships, location or demographic attributes, and its contact rates with every other type. People of a type have the same modeled contact behavior and transmission parameters. The regime is credible when the population \(N\) is large while the number of types \(\tau\) and groups \(r\) stay modest. This is a high-multiplicity version of the paper’s seed-selection problem: each person still receives an integral decision, but the decision variable can be the fraction of each type seeded.
My lead mirror is Type-Mass Fair Influence Targeting. An instance has rational type masses \(\mu_t\) summing to \(1\), group memberships \(a_{gt}\in\{0,1\}\), rational contact rates \(\lambda_{tu}\), a seed budget \(\beta\) as a fraction of the population, and target influence levels \(W_g\). In the population model, a type-\(t\) agent has contact intensity \(\lambda_{tu}\) toward each type-\(u\) agent at population scale \(N\); this corresponds to a sparse block network with pairwise live-edge probability \(\lambda_{tu}/N\). A solution is a seed-fraction vector \(x\in[0,1]^\tau\) with \(\sum_t\mu_t x_t\le\beta\).
For a concrete continuum cascade semantics, let \(z_t^{(0)}=x_t\), and update by \(z_u^{(q+1)}=x_u+(1-x_u)\bigl(1-\exp(-\sum_t\mu_t\lambda_{tu}z_t^{(q)})\bigr)\). The influenced share of group \(g\) is \(\Phi_g(x)=\sum_t\mu_t a_{gt}z_t^{(\infty)}/\sum_t\mu_t a_{gt}\). Given feasible targets, the problem asks for a seed-fraction vector meeting all group targets, or an approximation satisfying \(\Phi_g(x)\ge(1-1/e-\varepsilon)W_g-\varepsilon\). The paper’s diversity-constrained welfare objective fits by adding total influence as another objective and searching for its largest feasible target. The type-level cascade rule is the explicit modeling choice here; its correspondence to large finite block networks is a bridge to establish, not an identity for arbitrary fixed graphs.
The anchor is Theorem 3.2, proved in this paper (with its proof in Appendix B.5). For feasible targets \(W_1,\ldots,W_m\), the paper’s algorithm returns a set \(S\) with \(f_i(S)\ge(1-\varepsilon)(1-\frac{m}{k(1+\varepsilon')\varepsilon^3})(1-\frac1e)W_i-\varepsilon\) for every objective, with probability at least \(1-\delta\). Here the \(f_i\) are monotone submodular objectives, \(k\) is the seed budget, and the result’s asymptotic approximation approaches \(1-1/e\) as \(k\to\infty\) when \(m=o(k\log^3 k)\). The theorem also gives oracle-call bounds: \(O(nm)\) \(\varepsilon'\)-accurate value calls, \(O(mbk^2\varepsilon^{-1}\log(1/\delta))\) \(\varepsilon\)-accurate value calls, and \(O(bk^4c^2\varepsilon^{-5}\log(n+bk/(\delta\varepsilon)))\) gradient and item-gradient calls, plus its stated polynomial additional work. The paper supplies stochastic gradient oracles for independent-cascade influence in Appendix C. I find no named hardness result in the supplied text, so this algorithmic theorem is the appropriate anchor.
I expect this mirror to be Class A, at least for stable type-contact kernels with a fixed number of groups. The population budget corresponds to \(k=\beta N\), so fixed \(r\) is well within the theorem’s many-seeds, few-objectives regime. More significantly, the paper already reduces group fairness to simultaneous submodular targets and develops a continuous Frank–Wolfe method to handle them. In the mirror, agents of a type are exchangeable, so seed fractions are the natural decisions; the type-level influence and its gradients can plausibly be computed from the contact kernel without enumerating people. The actual research question is whether one can obtain the approximation in time polynomial in \(\tau,r,L,1/\varepsilon\), where \(L\) is the binary input length, rather than in the population size \(N\). Theorem 3.2 motivates that question but does not prove this compressed-input running time.
The mirror covers the paper’s algorithmic result for fair seed selection: group targets for maximin fairness, and group targets plus total influence for diversity constraints. It does not claim to continuize the paper’s price-of-fairness bounds or its non-submodularity result.
The weak point is the network model. On an observed fixed graph, two people with the same demographics can have very different centralities and neighborhoods; grouping them by average contact rates could erase strategically important seed choices. The paper’s empirical networks are also small, so they do not establish this large-population regime. The positive case survives as a plausible alternate scenario: a large outreach population modeled by a block contact process, where agents really are interchangeable for the intervention model. Its high-multiplicity assumption is explicit and testable, and the paper’s fairness objectives and multiobjective algorithm remain recognizable.
The strongest objection is that Theorem 3.2 does not supply the claimed compressed algorithm. Its ground set is the set of individual seed nodes, and its oracle calls and running time depend on \(n\) and \(k\). The paper’s influence oracles use the realized graph to estimate each node’s marginal effect. Replacing that graph with type masses and contact rates changes the input: it assumes an exchangeable block network and a type-level cascade limit. The recurrence in the proposed mirror is a plausible model, but its connection to finite networks is a result to establish, not a consequence of Theorem 3.2. At best, the paper motivates a new computational question; its main algorithmic theorem does not answer it.
That is not enough to rule out a worthwhile mirror. In an observed network, a person’s position and neighborhood affect their seeding value. A type that captures those differences may need to distinguish nearly every person, leaving no useful multiplicity. Grouping people by demographics and average contact rates avoids that problem only by removing the realized network from the decision problem. The resulting randomized block model is coherent, and authors could plausibly recognize it as fair influence maximization in a different regime. It remains a credible continuous-population question, even if the paper’s theorem offers little direct leverage.
So the negative case is weak on the required universal claim. The paper’s actual graph-based setting resists compression, and Theorem 3.2 does not transfer its guarantee to a type-mass model. But the proposed block-network scenario survives those objections: high multiplicity is sensible there, and the mass-based fairness optimization is well posed. I cannot honestly argue that it is not worth asking.
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.