| paper | d4-conf-aaai-2023-0487 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
Answer: \(\mathrm{NP}\)-hard under the specified accuracy dependence; an algorithm polynomial in \(m,\tau,H,L,1/\epsilon\) would imply \(\mathrm P=\mathrm{NP}\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 4.1
Given rational type masses \(\mu_t\), contact rates \(a_{st}\), community memberships \(b_{jt}\), a seed-mass budget \(\kappa\), and a finite horizon \(H\), optimize over \(x_t\in[0,1]\) with \(\sum_t\mu_t x_t\le\kappa\). Define \(z_t^{(0)}=x_t\) and \(z_t^{(h+1)}=1-(1-x_t)\exp(-\sum_s\mu_s a_{st}z_s^{(h)})\); maximize \(F_H(x)=\sum_t\mu_t z_t^{(H)}\) subject to equal coverage \(\phi_j(x)=\sum_t b_{jt}\mu_t z_t^{(H)}/\sum_t b_{jt}\mu_t\) across communities. Determine the complexity, in \(|T|\), \(H\), input bit length, and \(1/\epsilon\), of finding a rational solution with objective within \(\epsilon\) of optimum and parity violations at most \(\epsilon\).
A finite-type sparse block IC population: type \(t\) has mass \(\mu_t\), type interactions have rates \(a_{st}\), and \(x_t\) is the seeded fraction of that type. The finite-horizon recurrence estimates reached mass; the objective is total reached mass, with equal average coverage across communities.
A finite matrix of block rates does not preserve reachability structure for arbitrary fixed graphs, so this studies a specific random block-network regime rather than a high-multiplicity representation of the paper’s full graph inputs.
fatal: False
The mirror covers Theorem 4.1’s deterministic IMdp hardness in the sparse block-network, finite-horizon regime. It leaves the other hardness results, the randomized-seeding variant, the approximation algorithm, the price-of-fairness results, and the experiments aside.
The strongest case I see is a continuous mirror of IMdp, the paper’s deterministic-seeding problem with demographic parity. The scenario is a large public-health or information campaign on a platform whose users fall into a manageable number of demographic and interaction-role profiles. A type records community membership and a user’s propagation rates to and from every other type. Users of one type are indistinguishable to the model; the population may contain millions of users but only tens or hundreds of types.
Here is a specific mirror. Let \(T\) be the finite type set, with rational masses \(\mu_t\ge 0\) summing to \(1\). Let \(a_{st}\ge 0\) be the contact rate from type \(s\) to type \(t\). Think of the corresponding finite population as having \(N\mu_t\) users of type \(t\), with each ordered pair from \(s\) to \(t\) having an IC live edge with probability \(a_{st}/N\). The continuum limit then has a finite type description even as \(N\) grows.
A solution chooses \(x_t\in[0,1]\), the fraction of type \(t\) seeded, with total seed mass at most \(\kappa\):
\[
\sum_{t\in T}\mu_t x_t\le \kappa.
\]
For a specified propagation horizon \(H\), define the reached fraction of type \(t\) by
\[
z_t^{(0)}=x_t,\qquad
z_t^{(h+1)}
=1-(1-x_t)\exp\!\left(-\sum_{s\in T}\mu_s a_{st}z_s^{(h)}\right).
\]
This is the sparse-block IC mean-field recurrence: a type-\(t\) user is reached if seeded or if at least one reached user contacts them. The objective is total reached mass, \(F_H(x)=\sum_t\mu_t z_t^{(H)}\).
Represent each community \(j\) by membership indicators \(b_{jt}\in\{0,1\}\), allowing overlapping communities and types outside all communities. Its reached fraction is
\[
\phi_j(x)=
\frac{\sum_t b_{jt}\mu_t z_t^{(H)}}{\sum_t b_{jt}\mu_t}.
\]
Block-Continuum IMdp\(_H\) asks for a feasible \(x\) maximizing \(F_H(x)\), subject to \(\phi_j(x)=\phi_\ell(x)\) for every pair of communities. Its approximate variants can use the paper’s \((\alpha,\beta)\) convention: the objective is compared with the exact-parity optimum, and feasibility requires \(\phi_j(x)\ge\beta\phi_\ell(x)\) for all pairs. The input is the rational type masses, rates, community memberships, budget fraction and horizon; a computational version can request rational output to a specified precision.
My anchor is Theorem 4.1, proved in this paper. It says that for every \(\alpha,\beta\in(0,1]\), there is no polynomial-time \((\alpha,\beta)\)-approximation algorithm for IMdp unless \(P=NP\). Here an \((\alpha,\beta)\)-approximation must return a seed set whose expected spread is at least \(\alpha\) times the optimum under exact parity, while each community’s coverage is at least a \(\beta\) fraction of every other’s. The paper proves the result by a reduction from Set Cover under IC diffusion: its construction makes the existence of a positive-spread \(\beta\)-feasible solution distinguishable exactly when the Set Cover instance is positive. This is a good anchor because it is a named hardness result about the paper’s demographic-parity problem, not merely an algorithmic or empirical observation.
The continuous question is not that theorem restated. The theorem’s seed set chooses discrete nodes of a finite graph; the mirror chooses seeded mass in a population whose members share type-level propagation profiles. The high-multiplicity regime is \(N\gg |T|\), with seed budget scaling as a population fraction. The parameter \(\kappa\) is the per-capita counterpart of \(k\). These changes are necessary to give seeding and network exposure a nontrivial population limit. The mirror still asks the paper’s central question: how much expected spread can be achieved while enforcing equal group coverage?
I would expect the unrestricted mirror to be Class C, hard for continuum-specific reasons, though that is a conjecture for a prover to investigate, not a consequence of Theorem 4.1. The type-interaction matrix and community constraints can still carry substantial combinatorial structure as \(|T|\) grows, and the multiround recurrence is nonlinear. But the Set Cover reduction does not automatically survive: allowing fractions of each type to be seeded may remove the integrality gap that drives the discrete reduction. Establishing whether it survives, or finding a tractable formulation, is the point of the mirror.
This is plausible for the authors because it keeps their underlying decision—where to seed to maximize expected information spread—and their exact fairness constraint. The contact rates are part of the type description, just as prices or costs would be; they are not an arbitrary information loss. Also, the paper’s distributions over seed sets and independent node probabilities do not already make its society continuous: the paper still has a finite set of named graph nodes. In this mirror, it is the population that is represented by masses. Diffusion remains the influence model.
The mirror covers Theorem 4.1’s deterministic IMdp result, in the sparse-block, finite-horizon regime. It does not claim to mirror all three variants, the price-of-fairness lemmas or the experiments. It raises useful follow-up questions: does the Set Cover hardness survive fractional type seeding; is there an algorithm for fixed \(|T|\) or fixed \(H\); and how do finite high-multiplicity block instances approximate this recurrence as \(N\) grows?
The weakest point is that the paper accepts an arbitrary input graph, while this mirror assumes exchangeable users with type-level contact rates. An observed social network may have too many distinct interaction profiles for that assumption to be useful. More seriously, fractional seeding may dissolve precisely the discrete hardness in the anchor. Those are real limitations, but they do not make the question a different objective: they identify the regime and the central complexity question that the continuous mirror should test.
Theorem 4.1 is a valid computational anchor: it gives a named hardness result for IMdp. The paper’s randomized seed-set variants do not make its population continuous, and the listed analytic work on diffusion would not by itself settle this computational question. So the negative case has to turn on whether the proposed population model still captures the problem the theorem concerns.
The proposed block model has a real representational gap. In the paper, the graph is fixed input and randomness comes from diffusion. In Block-Continuum IMdp\(_H\), the type interaction rates describe an exchangeable random network, and the recurrence uses those rates as a closure for the dynamics. Pairwise rates and type masses do not determine expected spread on an arbitrary fixed graph: path overlap, bottlenecks, hubs, and other neighborhood structure can change reachability while leaving those summaries unchanged. To preserve that structure in the type definition, one may need to encode increasingly detailed neighborhoods, so the number of types can grow with the population. The high-multiplicity advantage then weakens.
A graphon-style version is a stronger candidate because it retains a continuum of interactions. Yet a dense kernel with a positive per-capita seed budget can make reachability saturate quickly; a sparse scaling avoids that effect but requires local network structure beyond a finite matrix of rates. Finite step kernels return to the block-model restriction. These concerns do not rule out useful sparse-network limits, but they make the mirror depend on a chosen network limit as much as on continuizing the population.
The theorem’s Set Cover reduction also does not carry over automatically. Its gap uses an integral seed set and a fixed incidence graph. Fractional seed mass changes the feasible interventions and can remove the zero-versus-positive distinction used in the reduction. That change in answer is allowed by the programme; it is not itself an objection. It does mean the continuous problem needs its own motivation and complexity study, rather than inheriting the theorem’s significance from its label as a mirror of Theorem 4.1.
The strongest case against is therefore one of scope: the proposed model is a plausible, potentially worthwhile study of fair influence maximization on sparse block networks, while its connection to the paper’s general fixed-graph hardness problem is narrow. I cannot honestly turn that into the universal claim that no scenario is worth the programme’s time. The proponent has supplied a defensible high-multiplicity scenario; the negative case is strongest as a warning about what that scenario represents, and weak as a rejection of the mirror altogether.
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.