| paper | d4-conf-aaai-2018-0366 |
| 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 polynomial-time algorithm returns a feasible rational control satisfying $\mathcal M(x)\ge(1-1/e-\epsilon)\mathrm{OPT}$ under the stated uniqueness promise. · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 5
statement extracted from the paper’s text layer
Given \(\tau\) types with rational masses \(\mu_a\), nonnegative rational biases \(b_a\), a symmetric nonnegative rational interaction matrix \(K\), and a budget \(B\), consider populations of size \(N\) whose type proportions approach \(\mu\), with type-\(a\) agents interacting with type-\(b\) agents at strength \(K_{ab}/N\). Choose fractions \(x_a\in[0,1]\) of each type to pin active, subject to \(\sum_a\mu_a x_a\le B\). For free-agent type magnetizations \(r_a\in[-1,1]\), set \(q_a=x_a+(1-x_a)r_a\), and let \(r^*(x)\) be the unique maximizer of \(\frac12\sum_{a,b}\mu_a\mu_b K_{ab}q_aq_b+\sum_a\mu_a b_aq_a+\sum_a\mu_a(1-x_a)s(r_a)\), where \(s\) is binary entropy. Define \(\mathcal M(x)=\sum_a\mu_a q_a^*(x)\). Determine whether an algorithm polynomial in \(\tau\), input bit length \(L\), and \(1/\epsilon\) can return feasible \(x\) with \(\mathcal M(x)\ge(1-1/e-\epsilon)\mathrm{OPT}\), or establish a complexity barrier for this approximation problem.
A thermodynamic block-Ising population: agents share one of \(\tau\) complete behavioral and interaction types, have masses \(\mu_a\), biases \(b_a\), and interactions \(K_{ab}/N\). The decision pins a fraction \(x_a\) of each type active under a per-capita budget; the objective is the limiting normalized total activity \(\mathcal M(x)\), defined by the unique mean-field variational maximizer.
The mirror covers Theorem 5's monotonicity and submodularity result and its associated greedy approximation for activation under \(J\ge0\) and \(b_0\ge0\). It leaves Theorem 3's conditional projected-gradient guarantee, the Plefka approximation algorithms, other network regimes, and the experiments aside.
The strongest honest anchor is Theorem 5, proved in this paper. It says that when every Ising interaction is nonnegative and every initial bias is nonnegative, total activity \(M\) is a monotone, submodular function of the set \(V\) of nodes forced active. The proof uses the GHS inequality, stated as Theorem 4 and cited from Griffiths, Hurst, and Sherman (1970). The paper then applies the standard greedy bound: under a cardinality budget, repeatedly activating the node with the largest marginal increase gives a \(1-1/e\) approximation. That approximation is the consequence drawn from Theorem 5 and the greedy algorithm, not a separate numbered theorem.
Block-Mean-Field Ising Influence Maximization is the continuous-population problem I would put to a prover. An instance has \(\tau\) types with rational masses \(\mu_a\), where \(\sum_a\mu_a=1\); nonnegative rational base biases \(b_a\); a symmetric nonnegative rational interaction matrix \(K\); a population-share budget \(B\); and an accuracy parameter \(\epsilon\). Consider populations of \(N\) agents, with type proportions tending to \(\mu\). Each type-\(a\) agent has bias \(b_a\), and an agent of type \(a\) interacts with one of type \(b\) with strength \(K_{ab}/N\). Thus agents in a type share their full problem-relevant description: bias, interactions by type, and unit activation cost.
The decision is a vector \(x\in[0,1]^\tau\), where \(x_a\) is the fraction of type \(a\) pinned active. It must satisfy \(\sum_a\mu_a x_a\le B\). For free agents, let \(r_a\in[-1,1]\) denote the type’s mean spin, and write \(q_a=x_a+(1-x_a)r_a\) for its overall mean spin. In the thermodynamic limit, the mean-field objective is
\[ \mathcal M(x)=\sum_a\mu_a q_a^*(x), \]
where \(r^*(x)\) maximizes
\[ \frac12\sum_{a,b}\mu_a\mu_bK_{ab}q_aq_b +\sum_a\mu_a b_aq_a +\sum_a\mu_a(1-x_a)s(r_a), \]
and \(s(r)=-\frac{1+r}{2}\ln\frac{1+r}{2}-\frac{1-r}{2}\ln\frac{1-r}{2}\) is the binary entropy. Restricting to instances with a unique maximizer makes the objective unambiguous. The problem is to return a feasible \(x\) with \(\mathcal M(x)\ge(1-1/e-\epsilon)\mathrm{OPT}\), or establish the complexity barrier to doing so.
A plausible regime is a large online service whose many customers fall into a modest number of behavioral and network roles. Users in a role have similar baseline activity and respond to role-level interaction patterns; the platform can spend its budget guaranteeing activation for a fraction of each role. Millions of users and tens or hundreds of types is a sensible high-multiplicity regime. The block interaction kernel and per-capita budget are co-modifications needed to define that population limit. This preserves the paper’s question—how to maximize system activity by choosing whom to activate—rather than merely making its control vector continuous.
I expect the approximation question to be Class A in this regime. The finite models satisfy Theorem 5, so their type-level activation counts have diminishing returns; the natural next result is that this property survives as a continuous diminishing-returns objective, enabling a continuous-greedy or discretized approximation. That extension still needs proof. In particular, Theorem 5 does not establish a bit-polynomial algorithm for evaluating the limiting Gibbs response, so an end-to-end runtime bound in \(\tau\), input bit length, and \(1/\epsilon\) is an important further question. I would not claim polynomial-time exact optimization.
The weakest point is the block-mean-field restriction. The paper treats arbitrary finite networks, while this mirror needs many exchangeable agents with interactions summarized by a small type matrix; an arbitrary sparse network may require nearly one type per agent. The paper also has no named NP-hardness or complexity-classification result to anchor a hardness-transfer claim. Its continuous per-node influence setting is not itself a continuous population. Still, Theorem 5 gives a strong, specific bridge: in a credible high-multiplicity regime, its activation decision and activity objective have a population-limit analogue, and the paper’s submodularity result suggests a concrete approximation question.
Theorem 5 is the proponent’s strongest anchor, but its computational content is narrower than the greedy guarantee suggests. The theorem proves monotonicity and submodularity; the \(1-1/e\) bound follows if marginal values can be evaluated. Yet computing \(M(V)\) exactly requires the Gibbs average over \(2^n\) states, and the paper estimates it by Monte Carlo in its larger experiments. Its \(O(nH)\) greedy procedure counts objective evaluations, not bit-polynomial work. So Theorem 5 does not give the kind of end-to-end complexity result that a continuous mirror could directly extend.
There is also a real modelling gap. In a general network, a node’s interactions with named neighbors are part of its description. Nodes with different neighborhoods are different types, so the number of types can grow with \(n\). Keeping a small number of types requires block exchangeability and interactions scaled as \(K_{ab}/N\). That is a coherent regime, but it changes the network architecture and puts the problem into a thermodynamic mean-field model. The theorem’s result on arbitrary finite networks does not itself establish a computational result for that model.
Those objections do not defeat the proponent’s repaired mirror. A large platform with a modest number of behavioral and interaction roles is plausible, and block interactions are a natural way to model it. For that regime, one can ask how hard it is to optimize activation proportions under a per-capita budget. Finite block models inherit Theorem 5’s submodularity, and their normalized objectives may have a meaningful population limit. The remaining difficulty—whether the limiting objective can be evaluated and optimized efficiently—is a legitimate computational question, not a reason the mirror is ill-posed.
So the negative case is weak at its hardest point. I would argue that Theorem 5 is not a direct complexity result, and that its population mirror requires a restrictive network regime. But the authors’ subject matter makes that regime credible, and those objections do not show that the question falls outside their problem. Under the stated standard, I cannot honestly say this anchor has been defeated.
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.