| paper | d4-journals-geb-2012-0104 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
Proposition 8 gives an explicit asymptotic outcome formula, but does not claim an algorithm, complexity bound, or hardness result, so it cannot anchor a computational mirror. Minimum-cost advertising is a recognizable follow-up that uses the paper’s degree-class fractions, but it adds an optimization problem rather than mirroring a computational result established here.
fails bit a — no named computational result to mirror
The proposed optimization uses Proposition 8’s fixed-policy adoption formula; the paper’s other results analyze cascade thresholds, equilibria, and limiting network statistics, not advertising-policy computation.
The strongest plausible mirror is degree targeted minimum advertising. A convincing regime is a large customer population in a sparse random social network: many customers share a degree class, threshold rule, and advertising price, while the number of classes is small relative to the population. The advertiser observes degree but not individual identity and can target a fraction \(\alpha_d\) of each degree class. The mass of targeted customers is \(p_d\alpha_d\), and the advertiser pays \(c_d\) per targeted customer.
There is an important limit to this case: the paper has no named result establishing a computational complexity classification such as membership in P or NP hardness. Its numbered results are asymptotic probability theorems. The closest named anchor is Proposition 8, proved here through the more general Theorem 10. It says that, for a degree sequence satisfying Condition 1 and a degree based advertising strategy \(\alpha\), the final number of buyers is \((1-h_1(\hat z;\alpha,p,\pi))n+o_p(n)\), provided \(\hat z=0\), or \(\hat z\in(0,1]\) and \(g(z;\alpha,p,\pi)<0\) on some interval immediately to the left of \(\hat z\). Here \(\hat z\) is the largest root in \([0,1]\) of \(g(z;\alpha,p,\pi)=0\), where
\(h(z;\alpha,p,\pi)=\sum_d(1-\alpha_d)p_d\sum_{r\ge d-\lfloor dq\rfloor}r b_{dr}(1-\pi+\pi z)\),
\(g(z;\alpha,p,\pi)=\lambda(p)z(1-\pi+\pi z)-h(z;\alpha,p,\pi)\), and
\(h_1(z;\alpha,p,\pi)=\sum_d(1-\alpha_d)p_d\sum_{r\ge d-\lfloor dq\rfloor}b_{dr}(1-\pi+\pi z)\).
The paper defines \(b_{dr}\) as the binomial probabilities and \(\lambda(p)=\sum_d dp_d\). This is a named result about an explicit limiting outcome, not a theorem about computational complexity, so it does not strictly satisfy the requested anchor criterion.
A prover-ready problem suggested by that result is Minimum Mass Advertising for a Cascade Target. An instance gives a finite rational degree distribution \(p_d\), rational \(q,\pi\), per person advertising costs \(c_d\), a target adoption fraction \(\rho\), and a budget \(B\). Ask whether there is a policy \(\alpha\in[0,1]^{\Delta+1}\) with \(\sum_d c_dp_d\alpha_d\le B\) for which the Proposition 8 formula predicts a final buyer fraction of at least \(\rho\). A solution is such a policy. Restricting to regular instances where Proposition 8’s root condition holds keeps the question tied to its proved limit.
The paper gives a strong reason the authors would recognize this question: Section 2.4 explicitly has a firm choose degree class fractions and says strategy optimization needs the payoff as a function of \(\alpha\); Proposition 8 supplies that response function. The paper stops at evaluating a fixed strategy, so choosing a least cost strategy is a genuine additional question. My provisional expectation is Class C, since the root selected by the diffusion response makes the type level optimization nonconvex, and no embedding from a discrete advertising problem is apparent. That is a research hypothesis, not a hardness claim. Natural follow ups are whether fixed support or bounded degree makes the problem tractable, and whether approximate target guarantees admit efficient algorithms.
The weakest point is also decisive for grading: the paper already uses population fractions and derives their limiting cascade behavior. Continuity is not a new mirror here, and the optimization problem is not one of the paper’s named complexity results. So this is the best positive extension I see, but it cannot honestly be presented as a fully anchor compliant case under the stated rules.
The central objection is that the paper has no named computational result to mirror. Proposition 8 and Theorem 10 give asymptotic predictions for a *fixed* advertising policy; the other numbered results likewise concern cascade probabilities, equilibria, and limiting fractions. None classifies a computational problem or gives an algorithmic guarantee.
The strongest proposed question is still sensible as a policy-design problem:
\[ \min_{\alpha}\sum_d c_d p_d\alpha_d \quad\text{subject to}\quad 1-h_1(\hat z(\alpha);p,\pi)\ge \rho. \]
But it adds an optimization objective to Proposition 8; it does not continuize a problem from the paper. The paper already describes the advertiser’s choice as fractions \(\alpha_d\) of degree classes and derives the response to those fractions. The firm’s optimization may be worthwhile research, but the population-mass representation is already in the model. There is no discrete computational result here whose high-multiplicity version this question supplies.
Adding threshold, price, or efficacy classes makes the policy-design problem richer, but not a stronger mirror: it remains optimization over type-level fractions in an aggregate random-graph model. An instance-specific campaign problem would be a more direct discrete counterpart, but its outcome can depend on which agents are connected to pivotal regions. Degree and threshold types alone lose that information; encoding enough network position to preserve it can make types instance-specific, defeating the proposed small-support mass model.
This is not an argument that advertising optimization has no value, or that the paper’s analytic limits settle its computational complexity. The authors explicitly motivate optimizing advertising strategies, so the follow-up is recognizable. The negative case is narrower: that follow-up is an additional optimization problem, not a worthwhile *continuous mirror* of a computational result in this paper. A stronger claim that no useful research question could be built from it would go beyond what the paper supports.
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.