| paper | d4-conf-aaai-2022-1673 |
| 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: The decision problem is in \(\mathrm{P}\); an exact maximizing trigger vector is computable in time polynomial in \(m,\tau,L\). · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 1
Given a finite set of peer-effect types \(T\), rational population masses \(\mu_t>0\) summing to one, and finite rational distributions \(\nu_t\) over observed influence-outcome pairs \((I,Y)\), choose a trigger \(r_t\) for each type to maximize \(\sum_{t\in T}\mu_t\bigl(\mathbb{E}_{\nu_t}[Y\mid I\ge r_t]-\mathbb{E}_{\nu_t}[Y\mid I<r_t]\bigr)\), with both conditional sets nonempty.
Types represent recurring cohorts sharing the modeled features, neighborhood context, and threshold response. Each type carries mass \(\mu_t\) and a finite rational distribution \(\nu_t\) over influence and outcome observations; the decision is a trigger vector maximizing the population-weighted CAPE objective.
The mirror extends Theorem 1’s node-threshold estimation claim to cohorts; it leaves the empirical diffusion-size predictions, model comparisons, and unnumbered runtime statement outside.
The strongest honest positive case is for a continuous threshold-estimation problem over repeated peer-effect cohorts. But there is a limit to the case: this paper gives no named computational-complexity result of the kind the brief requires as an anchor.
The only numbered result in the supplied text is Theorem 1, proved here. It says that for any node \(v\) in the Linear Threshold Model, whose outcome is \(1\) exactly when its neighbors’ activation influence reaches the true threshold \(\theta_v\), the trigger \(\hat\theta_v\) maximizing the causal effect estimate—mean outcome above the trigger minus mean outcome below it, conditional on the node’s features and \(Z_v\)—is the true threshold. The theorem is an estimation claim, not a result that a problem is in P, NP-hard, or in another complexity class. The text does give an unnumbered runtime statement for ST-Learner: if the base learner predicts in \(O(d)\) time, trigger search takes \(O(d|B|)\). That is useful algorithmic information, but it is not a named result of the required kind. So there are no qualifying anchors here.
A plausible mirror, offered as a candidate rather than as an anchored complexity result, is Mass-CAPE Trigger Estimation. Its instance is a finite set of peer-effect types \(T\), each with rational population mass \(\mu_t\), and for each type a rational distribution \(\nu_t(i,y)\) over observed activation influences \(i\) and outcomes \(y\in\{0,1\}\). A type represents users sharing the features and local-neighborhood characteristics the model uses, with a common threshold response to influence. The question is to choose one trigger \(r_t\) per type to maximize the population-weighted CAPE:
\[
\sum_{t\in T}\mu_t\left(
\mathbb{E}_{\nu_t}[Y\mid I\ge r_t]
-
\mathbb{E}_{\nu_t}[Y\mid I<r_t]
\right).
\]
A solution is the trigger vector attaining that maximum. In a large platform, the intended regime might be millions of users but only hundreds or thousands of recurring feature and neighborhood cohorts; mass is the fraction of users in each cohort.
This is close to the paper’s node-threshold estimation task: it keeps the threshold as the unknown, uses the same above-versus-below-trigger objective, and aggregates over a population of comparable nodes. A referee could plausibly recognize it as a high-multiplicity version of that task. With finite input support, sorting the influence values and scanning candidate triggers appears polynomial in the support size. That would make it a tractable mirror, though a modest one: the paper does not prove this population-level claim.
The weak point is substantial. Theorem 1 reasons about an individual node’s deterministic threshold response; it does not establish that maximizing a pooled, population-weighted objective recovers thresholds for heterogeneous cohorts. Even within a cohort, the threshold may not be identifiable if the observed influence values leave a gap around it. And while repeated cohorts make a high-multiplicity regime plausible, the paper’s network setting may require so much local-neighborhood detail that the number of types grows with the population. Finally, this is threshold estimation for peer effects, not clearly a computational-social-choice problem. The mirror may be a sensible continuous analogue of part of the paper, but it does not supply the kind of named hardness or tractability anchor the programme is designed to chart.
The only anchor is Theorem 1, and it is not a computational-complexity result. It identifies a node’s threshold as the trigger maximizing a causal-effect objective; it gives no complexity classification, reduction, or algorithmic bound for a computational problem. The causal-tree and ST-Learner sections describe estimation procedures, and the \(O(d|B|)\) statement is a runtime observation, not a named tractability result. So the paper offers no result of the kind ChoCo is meant to mirror.
The proponent’s Mass-CAPE problem is the strongest salvage, but its stated objective separates: \(\sum_t \mu_t g_t(r_t)\) is maximized by maximizing each \(g_t\) independently, since every supported type has \(\mu_t>0\). That is the same trigger search repeated for each cohort. If instead all types must share one trigger, the objective no longer separates, but the candidates are still the finitely many observed influence values; sorting them and scanning the resulting averages solves the problem. Population masses change the weights, not the computational structure.
A more faithful cohort version can require each type to share a deterministic threshold and have observations on both sides of it. Then Theorem 1’s identification claim can apply type by type, but the continuous problem is still a collection of one-dimensional searches. If thresholds vary within a cohort, a maximizing pooled trigger is generally just the best split in that cohort; it need not recover anyone’s threshold. Refining types until thresholds and relevant contexts are shared restores the interpretation, but may leave as many types as nodes.
The network makes richer mirrors difficult to rescue. A node’s diffusion outcome depends on its links and the evolving activations of its neighbors, so a distribution over node features and influence values alone does not preserve the interactions. Keeping enough rooted network context can make types essentially unique. A graphon or other continuum network model is possible, but it changes the task into studying diffusion dynamics under additional structural assumptions. Turning that into a computational problem such as seed selection would add a new decision problem the paper does not analyze.
I would reject this paper as a worthwhile anchored ChoCo case: its theorem is not a complexity result, and the closest population version is a routine weighted threshold scan. That does not prove no interesting extension can be imagined; the honest negative case is strongest for the programme’s stated complexity agenda, not for every conceivable continuum model of peer effects.
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.