| paper | d4-conf-aaai-2023-0310 |
| 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→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\text{-hard}\) · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 3.4
statement extracted from the paper’s text layer
Given rational type masses \(\mu_t>0\) summing to \(1\), a partition into communities \(C_j\), baseline block contact rates \(\lambda^0_{tu}\), and budgets \(\kappa,\beta\), choose nonnegative type-pair link rates \(z_{tu}\) with \(\sum_{t,u}\mu_t\mu_u z_{tu}\le\beta\). Seed masses satisfy \(0\le x_t\le\mu_t\) and \(\sum_t x_t\le\kappa\). Let \(r_t^0=x_t/\mu_t\), \(d_t^\ell=r_t^\ell-r_t^{\ell-1}\), and evolve the block-kernel independent-cascade limit by \(r_u^{\ell+1}=r_u^\ell+(1-r_u^\ell)(1-\exp[-\sum_t\mu_t(\lambda^0_{tu}+z_{tu})d_t^\ell])\); write \(R_t(x,z)=\lim_{\ell\to\infty}r_t^\ell\). Define \(X^*(z)\) as the seed-mass vectors maximizing \(\sum_t\mu_tR_t(x,z)\). For fixed additive gap \(\varepsilon>0\), approximate \(\max_z\min_{x\in X^*(z)}\min_j\frac{\sum_{t\in C_j}\mu_tR_t(x,z)}{\sum_{t\in C_j}\mu_t}\), or decide whether this value is at least \(\theta\) using a corresponding rational-input gap formulation.
A finite-type stochastic block population with mass \(\mu_t\), baseline contact kernel \(\lambda^0_{tu}\), type-pair link-rate decisions \(z_{tu}\), and seed-mass decisions \(x_t\). The objective is to maximize minimum community coverage under the mean-field cascade, taking the minimum over all seed-mass vectors that maximize total spread.
The type-pair contact rates replace the paper’s choices of particular non-edges, so the mirror assumes diffuse, population-scale interventions whose fidelity to the paper’s edge-level setting is not established.
fatal: False
The mirror covers the FIMAL objective and anchors on Theorem 3.4. It does not claim that the theorem’s reduction or the further FIMAL hardness results in Theorems 3.5–3.7 transfer; it leaves the separate greedy-spreader problem FIM\({}^{g}_{\mathrm{AL}}\) aside.
The strongest mirror I see is for the paper’s FIMAL problem: an organization changes a large network so that an efficiency-seeking information spreader also gives each community reasonable coverage.
My anchor is Theorem 3.4, proved in this paper. It says that deciding FIMAL is \(\Sigma_2^p\)-hard even in the deterministic case. In full, an instance gives a directed weighted graph, a community structure, link budget \(b\), seed budget \(k\), and threshold \(t\). The question is whether there is a set \(F\) of at most \(b\) non-edges such that, after adding \(F\), every seed set \(S\) of size at most \(k\) that maximizes total spread has minimum community coverage at least \(t\). The paper proves this by reduction from \(\Sigma_2\mathrm{SAT}\).
Here is a continuous-population version I would be willing to put to a prover. Call it Population-FIMAL. An instance has a finite set \(T\) of user types, with rational masses \(\mu_t>0\) summing to \(1\); a partition of the types into communities \(C_1,\ldots,C_m\); baseline directed contact rates \(\lambda^0_{tu}\); a seed-mass budget \(\kappa\); and an added-link budget \(\beta\). A type completely specifies the user properties relevant to the model: community, contact behavior, and eligibility for link additions.
The decision variable is a nonnegative matrix \(z\), where \(z_{tu}\) is the added contact rate from type \(t\) to type \(u\). Its per-capita link cost is \(\sum_{t,u}\mu_t\mu_u z_{tu}\), which must be at most \(\beta\). This is the co-modification needed to express link additions in a population model: the action is a type-to-type rate, rather than a choice among named individuals.
For seed mass, let \(x_t\in[0,\mu_t]\), with \(\sum_t x_t\le\kappa\). Under independent-cascade diffusion in the sparse block-network limit, write \(r_t^\ell\) for the fraction of type \(t\) reached by round \(\ell\), starting from \(r_t^0=x_t/\mu_t\), and let \(d_t^\ell=r_t^\ell-r_t^{\ell-1}\), with \(r_t^{-1}=0\). The mean-field cascade is
\[ r_u^{\ell+1} = r_u^\ell+(1-r_u^\ell) \left(1-\exp\left[-\sum_t\mu_t(\lambda^0_{tu}+z_{tu})d_t^\ell\right]\right). \]
Let \(R_t(x,z)=\lim_{\ell\to\infty}r_t^\ell\). Total spread is \(\sum_t\mu_tR_t(x,z)\), and coverage of community \(C_j\) is \(\sum_{t\in C_j}\mu_tR_t(x,z)/\sum_{t\in C_j}\mu_t\). Define \(X^*(z)\) to be the seed-mass vectors maximizing total spread for \(z\). The Population-FIMAL question is: is there a feasible \(z\) for which every \(x\in X^*(z)\) gives every community coverage at least \(\theta\)? Equivalently, its optimization version chooses \(z\) to maximize the minimum community coverage over all total-spread-maximizing seed vectors. For a bit-complexity formulation, one can ask for an additive-\(\varepsilon\) approximation, with rational input rates and output rates. This definition assumes the inner spread maximum is attained; alternatively, a version can require fairness for all limit points of nearly optimal seed vectors.
The regime is a large platform with repeated user roles: for example, many users sharing a region, language, and broad interaction pattern. The number of people \(N\) is large compared with the number of types \(\tau\). Seed and link budgets scale with population size, so \(\kappa\) is the seeded fraction and \(\beta\) is added links per capita. The cascade is still stochastic; the continuous object is the population, whose reached fractions are the limit quantities. The paper’s order of decisions survives intact: add links, let an efficiency-oriented spreader choose seeds, then measure worst-community coverage across all spread maximizers.
This is a credible mirror of Theorem 3.4’s underlying problem, rather than of its graph encoding. The paper studies exactly the interaction between a link designer, a spread maximizer, and community fairness. The type-level model makes its assumptions about repeated roles explicit and gives a natural normalized meaning to both budgets. The exact complexity theorem does not automatically carry over, though: the reduction uses a finite graph’s individual edge opportunities, while Population-FIMAL permits fractional seed mass and fractional link rates.
My provisional expectation is Class C, continuum-specifically hard. The nested requirement that a link choice work against every spread maximizer remains, and the mean-field cascade introduces a nonlinear response to link rates. But I would treat that as a conjecture about the mirror, not as a consequence of Theorem 3.4. A useful first question for a prover is whether the reduction can be implemented with cohorts of repeated agents while preserving its yes/no behavior. If so, this would instead be a Class B hardness transfer. If fractional augmentation destroys the reduction, the next questions are whether bounded \(\tau\) permits an approximation algorithm and whether the exponential cascade response admits a tractable relaxation.
This covers the paper’s FIMAL fairness-under-optimal-spread results, especially Theorem 3.4. It does not claim to mirror the separate greedy-spreader problem FIM\({}^{g}_{\mathrm{AL}}\).
My weakest point is that the paper’s hardness construction assigns structure to named vertices, whereas the mirror aggregates agents who are interchangeable for the model. The theorem therefore motivates a precise continuous question but does not establish its hardness. The positive case rests on the model preserving the paper’s central decision sequence and fairness objective, and on repeated user roles being a plausible network regime.
The strongest objection is to the fit between Theorem 3.4’s reduction and a high-multiplicity population. Its graph is a Boolean gadget: choosing particular new edges out of \(q\) encodes an assignment, and the clause communities and optimal seed sets test that assignment against every assignment to the remaining variables. The reduction uses which named vertices are connected to which other named vertices.
That structure does not survive simple replication. If you clone vertices but keep their clause roles and edge opportunities distinct, the clones are not interchangeable for the problem, so the type count grows with the instance. If you pool them into types, the mirror replaces choices of particular edges and seed sets with fractional link rates and seed masses. In the proposed model, \(z_{tu}\) applies to a whole type pair; it cannot express “add this one link because these two particular vertices make the gadget work.” The resulting universal condition over all maximizing mass vectors is sensible, but it is a new condition on a new optimization problem, not a high-multiplicity realization of the reduction.
The block-network version is the best repair: repeated user roles, a type-to-type contact kernel, and budgets scaled per capita. It is plausible for a large platform, but it assumes users mix according to that kernel and gives the designer diffuse control over type pairs. The paper’s setting instead gives the designer specific non-edges in a particular network; individual bridges and their locations can matter. Adding latent coordinates to preserve that topology creates a harder dilemma: the coordinates make agents effectively distinct, while edits at individual points have zero mass in the limit. Macroscopic kernel changes avoid that problem by changing the intervention scale.
I would therefore argue against treating this as a strong mirror of Theorem 3.4: the reduction offers little reason to expect its population version to illuminate the paper’s result, and the more faithful network-limit model would need substantial independent justification. But this is not a decisive case against asking the question. A stochastic block model with per-capita link and seed budgets is a coherent computational problem, and the paper’s authors might well recognize it as theirs. The negative case is weakest there: saying the answer may differ, or that hardness may fail to transfer, would not make the mirror unworthy.
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.