| paper | d4-conf-aaai-2018-0704 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 1
statement extracted from the paper’s text layer
Given a finite type set \(T\), rational type-mass arrival rates over a horizon, ads with type-specific click and continuation probabilities, and a finite typed independent-cascade model with a specified population scaling and limiting diffusion law, allocate each arriving type mass among integral ad sequences without observing prior cascades. What competitive ratio can an online policy achieve against an offline allocation that knows the full arrival stream, and can a greedy mass-allocation policy attain \(1/2\) with efficient approximation in the number of types, ads, input bit length, and requested accuracy?
A nonadaptive typed population with rational mass arrivals; types share ad-response parameters and type-pair diffusion parameters. The decision variables are mass allocations to ad sequences at each arrival, and the objective is expected advertiser revenue from the limiting typed cascade, compared with the offline optimum.
The fixed-graph marginal gains depend on neighborhood overlap, which type-level diffusion profiles need not preserve; the proposed block model changes that network regime, and Theorem 1 does not establish the same guarantee there.
fatal: False
The surviving mirror covers the nonadaptive competitive result in Theorem 1. Theorem 2's full-feedback result and Theorem 3's partial-feedback result are left aside because their individual-realization feedback is not captured by the proposed type-mass state; the experiments and exact marginal-evaluation issue are also outside this mirror.
The strongest honest mirror is for large, exchangeable platform audiences: millions of users fall into a modest number \(\tau\) of audience types, with users of a type sharing their ad click and continuation probabilities and their probabilistic diffusion profile across types. For example, the platform might choose among dozens of measured audience segments. The mass of a type is its fraction of the audience. An assignment of \(30\%\) of a type to one sequence and \(70\%\) to another means that each actual user still receives an ordinary, integral sequence; only the type-level assignment is fractional.
A common instance for the mirrors below has a finite type set \(T\), rational masses \(\mu_t\), ads \(A\), rational \(q_i(t)\), \(c_i(t)\), and \(r_i\), and a finite description of each ad’s type-symmetric independent-cascade model. Users arrive as a stream of type-labelled mass. At each arrival, the policy assigns that mass among the available ad sequences. For a sequence \(\sigma\), the probability that type \(t\) shares ad \(i\) in slot \(k\) is \(q_i(t)\prod_{j<k}c_{\sigma(j)}(t)\). Each ad’s cascade model gives the expected influenced mass from its resulting seeds, so the objective is \(\sum_{i\in A}r_i\,\mathbb{E}[\text{influenced mass for }i]\). The type description includes the parameters used by the problem; random cascade outcomes remain random outcomes, not additional personal characteristics.
Lead mirror — Continuous Nonadaptive Social Ad Sequencing. A policy sees each arriving type and prior assignments, but not the cascades they produced. It must assign the arriving mass among integral ad sequences to maximize expected revenue. The online question is to find the best competitive ratio against an offline allocation that knows the complete arrival stream. This mirrors Theorem 1, proved in the paper: Algorithm 1 chooses for each arriving user the sequence with greatest expected marginal gain, computes that sequence by dynamic programming, and achieves a \(1/2\)-competitive ratio. The proposed continuous question is whether the corresponding greedy policy over infinitesimal arrivals achieves the same guarantee, and whether it can be computed or approximated efficiently in the number of types, ads, input bit length, and requested accuracy. I expect Class A, under the typed cascade model above: the per-type sequence choice remains finite, and the discrete guarantee offers a plausible route to the continuum guarantee by refinement of the mass stream.
Full-feedback mirror — Continuous Adaptive Social Ad Sequencing. Use the same instance and objective, but allow the policy to observe the full diffusion realization after earlier assignments before choosing the next sequence. Ask for the optimal adaptive online policy and its competitive ratio against the best adaptive policy that knows the full arrival stream but not future random outcomes. This mirrors Theorem 2, established in the paper using its adaptive-submodularity result and a theorem of Golovin and Krause: Algorithm 2 greedily maximizes expected marginal revenue given the observed realization and achieves a \(1/2\)-competitive ratio. I also expect Class A, provided the type-level feedback state and marginal gains have a finite, usable representation. The further question is how much feedback state must be retained to implement the policy without returning to individually labelled users.
Partial-feedback mirror — Continuous Partially Adaptive Social Ad Sequencing. Again use the same objective and assignment rules, but specify an observation map that reveals only part of each cascade. For each arriving mass element, let \(\alpha_t\) be a lower bound on the conditional probability that the most pessimistic full realization consistent with its partial observation is the actual realization, and set \(\alpha=\min_t\alpha_t\). Ask for the best policy and guarantee as a function of this observation model and \(\alpha\). This mirrors Theorem 3, proved in the paper: the greedy policy achieves \(\alpha/(1+\alpha)\)-competitiveness under partial feedback. This too looks Class A when the observation model and \(\alpha\) are compactly represented; the meaningful boundary question is what guarantee remains as \(\alpha\) approaches zero.
The paper contains no numbered hardness theorem, so these are algorithmic anchors. It does mention that computing an exact marginal gain is \(\#P\)-hard, citing Chen et al. That is an important qualification for all three mirrors: a tractability claim should distinguish exact marginal evaluation from efficient estimation or approximation. The results in the paper establish competitive guarantees, not a polynomial-time exact evaluation of every cascade expectation.
The scenario is plausible because social platforms already operate on large audiences divided into behavior and network-exposure segments. It also stays close to the paper’s problem: the decision is still which ad sequence to show each arriving user, and the payoff still comes from the ensuing social cascades. It does not continuize the ad itself or merely add uncertainty to a finite profile; it makes the audience population the mass object.
My weakest point is the network. The paper allows user-specific probabilities and models influence on an individual social graph. A finite type system preserves that problem only when the relevant click, continuation, and diffusion profiles really are shared or have a compact block representation. If the value of a user depends on unique neighbours or network position that cannot be captured by a modest number of types, the mirror loses part of the authors’ question. The proposed regime is therefore an exchangeable, typed platform audience, not a claim that every social network admits this compression.
The paper does have computational results to mirror: Theorems 1–3 give competitive ratios for online algorithms. So the negative case cannot rest on an absence of named results. Its strongest point is that all three results rely on the same feature of the model: the value of assigning a sequence to user \(u\) depends on \(u\)’s position in a particular social graph and on which other vertices have already been influenced.
For Theorem 1, the relevant marginal gain \(\Delta^i_S(u)\) is not determined by a user’s click and continuation probabilities, or even by their number of links into each audience segment. Two users with the same segment-level profile can have neighborhoods that overlap very differently with the current cascade, giving them different marginal gains. To preserve those gains exactly, a type must include enough of the user’s network role to distinguish such cases; on an irregular graph, that can make the number of types grow with the number of users. The proposed block or exchangeable network is the strongest repair: it may yield a sensible continuous model, but it replaces the paper’s fixed-graph problem with a graph-limit model. The \(1/2\) theorem does not by itself establish that its offline benchmark, marginals, or competitive guarantee pass to that limit. The paper also says exact marginal evaluation is \(\#P\)-hard, so its dynamic program is not an exact polynomial-time algorithm without an oracle or an estimation step.
The adaptive anchors face a sharper mismatch. Theorem 2’s feedback is the realization of individual live and blocked edges, and the observed cascade identifies particular vertices. A finite type-level state generally does not retain enough information to determine future marginal influence. Under an exchangeable network model, one could instead observe aggregate cascade statistics, but that is a different feedback model; if those statistics concentrate, the individual feedback that motivates the adaptive result may disappear, while retaining its fluctuations requires tracking more than type masses.
Theorem 3’s \(\alpha\) has the same difficulty in a more explicit form. It is defined through the probability that a particular pessimistic full realization is the actual realization. In a continuum of independent edge outcomes, any one exact realization will generally have probability zero, so the stated guarantee degenerates. Defining pessimism over aggregate states could avoid that, but the proof’s comparison concerns reachability in particular realizations; aggregate counts alone need not preserve it.
That is a substantial case against the proposed three mirrors as finite-type continuizations of these theorems. It does not establish the requested universal negative. A nonadaptive mirror on a carefully specified exchangeable or block network remains plausible, and the paper’s subject makes that scenario credible. I cannot honestly claim that no worthwhile continuous mirror exists; the negative case is strongest against the adaptive anchors and weakest against the nonadaptive one.
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.