| paper | d4-conf-aaai-2021-1344 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→P discrete result → its continuous mirror
Answer: Polynomial-time computable; the specified mass recurrence admits a deterministic fully polynomial approximation scheme. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 3.4
statement extracted from the paper’s text layer
Given finite seed and recipient type sets \(E\) and \(R\), rational masses \(\mu_t>0\) summing to \(1\), a directed acyclic contact graph with rational rates \(\beta_{st}\), recipient communities \(\mathcal C\), and a rational seed-mass budget \(\kappa\), choose \(x_s\in[0,1]\) with \(\sum_{s\in E}\mu_s x_s\le\kappa\). Set \(r_s=x_s\) for seed types and, in topological order, \(r_t=1-\exp(-\sum_{s:(s,t)\in A}\mu_s\beta_{st}r_s)\) for downstream types. What is the maximum of \(\min_{C\in\mathcal C}\frac{\sum_{t\in C}\mu_t r_t}{\sum_{t\in C}\mu_t}\), or an additive-\(\epsilon\) approximation to it?
A society consists of type masses \(\mu_t\); the decision is the seeded fraction \(x_s\) of each eligible type, subject to the mass budget \(\sum_s\mu_s x_s\le\kappa\). Type contact rates and the acyclic exposure equations determine reached fractions \(r_t\), and the objective maximizes the minimum mass-weighted reached fraction across communities.
The mirror covers Theorem 3.4’s node-based maximin seeding question in a typed, acyclic mean-field regime. It leaves the paper’s other hardness, approximation, price-of-fairness, and experimental results outside the proposed mirror.
The mirror I find strongest is a finite-type, acyclic mean-field version of maximin influence maximization. Consider a large public-health or outreach campaign with \(N\) people but only \(\tau\) diffusion-relevant roles: for example, organizer types with particular access to recipient groups, and recipient types with particular group memberships. People of a type share their contact rates, seeding eligibility, and group attributes. The intended regime has \(N\) much larger than \(\tau\), with type masses \(\mu_t\) describing population shares.
My lead anchor is Theorem 3.4, proved in this paper using the cited Max-Coverage hardness result. It says that, for every \(\epsilon>0\), the paper’s node-based probabilistic maximin problem has no polynomial-time \((1-1/e+\epsilon)\)-approximation unless \(P=NP\). In that problem, given a graph, communities, and seed budget \(k\), one chooses probabilities \(x_i\in[0,1]\) with \(\sum_i x_i\le k\); each node is independently seeded with probability \(x_i\), and the objective is to maximize the minimum community’s expected fraction reached. The reduction uses an IC instance with one community \(R\) and a bipartite unit-edge graph encoding a Max-Coverage instance. This is a particularly useful anchor because it is a hardness result, and the paper itself says the bound is tight up to its additive error.
Here is the continuous question I would hand to a prover. Typed Mean-Field Maximin Seeding takes as input disjoint finite sets of seed types \(E\) and recipient types \(R\), a rational mass \(\mu_t>0\) for each type with \(\sum_t\mu_t=1\), and a directed acyclic graph of type-level contacts with rational rates \(\beta_{st}\ge 0\). It also takes recipient communities \(\mathcal C\), each a nonempty subset of \(R\), and a rational seed-mass budget \(\kappa\). Choose a seed fraction \(x_s\in[0,1]\) for each \(s\in E\), subject to \(\sum_{s\in E}\mu_s x_s\le\kappa\). In topological order, set \(r_s=x_s\) for seed types and, for each downstream type \(t\), set
\[
r_t=1-\exp\!\left(-\sum_{s:(s,t)\in A}\mu_s\beta_{st}r_s\right).
\]
Here \(r_t\) is the probability a representative type-\(t\) person is reached: each active type-\(s\) person contributes contacts to type-\(t\) people at per-capita rate \(\beta_{st}\), giving Poisson exposure in the population limit. For each community \(C\), its expected reached fraction is
\[
g_C(x)=\frac{\sum_{t\in C}\mu_t r_t}{\sum_{t\in C}\mu_t}.
\]
The task is to maximize \(\min_{C\in\mathcal C}g_C(x)\). A solution is a feasible vector \(x\) attaining the optimum, or an additive-\(\epsilon\) approximation to it.
This keeps the paper’s computational question—allocate seeds to maximize the least expected group coverage—while making population mass the object being modeled. A finite population with \(n_t\) people of each type, independently seeded at rate \(x_t\), and per-pair contact probability \(\beta_{st}/N\), converges to the stated type-level exposure equations as \(N\) grows. The mass budget is the high-multiplicity counterpart of the paper’s expected seed-count budget.
For this stated mirror, I expect Class A: tractable. In a type DAG, each \(r_t\) is a concave function of the seed fractions: the root values are linear, and each later value is an increasing concave function of a nonnegative linear combination of earlier values. Thus every \(g_C\) is concave. Maximizing a threshold subject to constraints \(\theta\le g_C(x)\), the seed-mass budget, and box constraints is convex optimization; the exponential terms admit standard convex representations. An additive-\(\epsilon\) solution is therefore computable in time polynomial in the type-level input size, its bit length, and \(\log(1/\epsilon)\).
The paper’s hardness does not automatically carry over. Its Max-Coverage reduction encodes arbitrary incidence patterns in a finite graph; this mirror replaces those per-person edges by per-capita contact rates and aggregate Poisson exposure. That co-modification is what yields the concave response. Further questions include whether tractability extends to cyclic type networks, what convergence guarantees relate the finite-population optimum to the mass optimum, and whether hardness returns when the type support grows or the contact model retains more of the finite graph’s structure.
The weakest point is the restriction to a typed, acyclic mean-field diffusion model. Theorem 3.4 is already hard despite independent random seeding, so the gain here does not come merely from making seed choices fractional. It comes from the continuous-population exposure law, which may be too strong a change for authors who regard arbitrary finite-network topology as essential. I think they would recognize the objective and its large-population regime as a credible analogue for this slice of their work, but this mirror covers Theorem 3.4’s maximin-seeding question in that regime; it does not claim to continuize the paper’s other results.
Theorem 3.4 is a real computational anchor: it gives a sharp approximation threshold for node-based maximin seeding. My strongest objection is to how far the proposed mirror moves from the network model that result concerns. In the theorem’s Max-Coverage construction, each seed node’s particular neighborhood matters, including how it overlaps other neighborhoods. Replacing those links with type-to-type rates turns a realized social network into an aggregate contact model. To preserve the original graph’s exact contact structure, types would have to encode increasingly detailed network positions; for a generic sparse network, the number of types would grow with the population. If types stay few, the model describes a much narrower class of networks.
The proposed DAG makes a further substantive restriction. Its recursive exposure law assumes feed-forward contact between types, and its tractability argument relies on that structure. A plausible repair is a fixed-support stochastic block model with rational contact rates, population-proportional seeding, and perhaps cycles. That is a coherent continuous-population problem, but it models a large campaign with extensive seeding and mass-action contacts, rather than the paper’s general problem of choosing a limited seed set in a given social graph. If the seed budget stays fixed as the population grows, its per-capita mass vanishes; keeping a nontrivial coverage objective requires changing the budget regime.
Those points justify calling the proposed result a mirror of a restricted contact-model variant, not a continuation of Theorem 3.4 across the paper’s network setting. They do not defeat the anchor under ChoCo’s stated gate, though. The stochastic-block scenario has repeated, diffusion-relevant roles, a meaningful population mass, and the same maximin seeding question. It is computational, and the paper’s existing analytic neighbors would not answer its complexity question. I cannot honestly make the universal negative case: the objections narrow the mirror, but the repaired version remains a credible one.
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.