| paper | d4-conf-ijcai-2016-0255 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 3
statement extracted from the paper’s text layer
Given media \(V\), a finite supported audience-type set \(T\) with rational masses \(\mu_t>0\) summing to \(1\), slot limits \(b_v\), costs \(c(v,j)\), and success probabilities \(q_{vti}\), draw independent Bernoulli outcomes \(\omega_{vti}\) for each eligible type, medium, and slot; each outcome applies to all mass of type \(t\). A policy buys slots sequentially, observes the outcomes of purchased slots, and adapts later purchases to that feedback. For \(x_v\) slots bought on medium \(v\), define reached fraction \(F_\omega(x)=\sum_{t\in T}\mu_t\mathbf{1}\{\exists v,\ i\le x_v:\omega_{vti}=1\}\) and cost \(C(x)=\sum_{v\in V}\sum_{j=1}^{x_v}c(v,j)\). Compute a policy whose expected reached fraction is at least \((1-1/e)\mathrm{OPT}_{\mathrm{exp}}(k)\), where \(\mathrm{OPT}_{\mathrm{exp}}(k)\) is the best policy whose expected cost over its own randomization is at most \(k\) for each full outcome realization; the policy must satisfy that same expected-cost bound and always have realized cost at most \(2k\).
A distribution over finitely many audience types, each with mass \(\mu_t\) and a response profile; decision variables are sequential slot purchases across media, the objective is reached population mass, and feedback consists of type-level slot outcomes shared by each type’s mass.
Theorem 3’s expected-budget guarantee and Theorem 4’s hard-budget guarantee cover adaptive reach in the shared-outcome type-mass model. The mirror leaves the independent-customer continuum limit and the paper’s empirical comparisons outside its scope.
The strongest mirror is the paper’s adaptive budget allocation problem with a large audience represented by a small distribution of audience types. Think of a national advertiser with millions of potential customers but a few dozen or hundred response profiles, defined by features such as region, platform, and prior engagement. A type \(t\) has mass \(\mu_t\), the fraction of the audience it represents. Its full profile records which media can reach it and its response probabilities for each medium’s successive slots. The number of people can be enormous while the support size \(\tau\) stays modest.
Here is the co-modification that makes this a genuinely continuous-population version: a campaign-slot outcome is shared across the mass of a type. If the slot succeeds for type \(t\), that type’s mass is reached. Such a shared outcome can represent a segment-level delivery or reach event. It preserves the paper’s adaptive allocation question while making the objective a fraction of society.
Lead mirror — Type-Mass Adaptive Reach with an Expected Budget. An instance consists of a finite media set \(V\), a supported type set \(T\) with rational masses \(\mu_t>0\) summing to \(1\), slot limits \(b_v\), costs \(c(v,j)\), and rational success probabilities \(q_{vti}\) for each eligible type \(t\), medium \(v\), and slot \(i\). For each triple \((v,t,i)\), draw an independent Bernoulli outcome \(\omega_{vti}\) with success probability \(q_{vti}\); that outcome applies to all mass of type \(t\). A policy buys slots over time, observes the outcomes of the slots it buys, and chooses later purchases based on that feedback. If it buys \(x_v\) slots of medium \(v\), its reached fraction is
\[ F_\omega(x)= \sum_{t\in T}\mu_t\, \mathbf{1}\!\left\{\exists v,\ i\le x_v: \omega_{vti}=1\right\}, \qquad C(x)=\sum_{v\in V}\sum_{j=1}^{x_v}c(v,j). \]
The question is to produce an executable adaptive policy \(\pi\), with \(x\le b\), whose expected reached fraction is at least \((1-1/e)\,\mathrm{OPT}_{\mathrm{exp}}(k)\). Here \(\mathrm{OPT}_{\mathrm{exp}}(k)\) is the best value of any policy that, for every full outcome realization \(\omega\), has expected cost over its own randomization at most \(k\). The returned policy must itself have that expected-cost bound, and its realized cost must never exceed \(2k\).
This mirrors Theorem 3, proved in this paper. The theorem says that for any adaptive monotone submodular objective over an integer lattice, its proposed policy achieves a \((1-1/e)\) approximation against every feasible adaptive policy. Its output respects \(x\le b\), has expected cost at most \(k\) for each full realization, and never spends more than \(2k\). In the mirror, \(F_\omega\) is weighted stochastic coverage: reached audience mass replaces the number of influenced customers. The type-level success outcomes give precisely the diminishing-return structure the theorem uses. Theorem 3 is my strongest anchor.
A second, useful mirror is Type-Mass Adaptive Reach with a Hard Budget. It has the same instance, feedback, and benchmark, but asks for a policy that always spends at most \(k\), while achieving at least \((e-1)/(2e)\,\mathrm{OPT}_{\mathrm{exp}}(k)\). This is Theorem 4, also proved here. It gives that guarantee against every expected-budget-feasible policy, while its own output always satisfies both \(x\le b\) and \(C(x)\le k\). This is a distinct question: it captures the value of a strict spend cap at a weaker approximation ratio.
For both questions, the computational parameters are the number of media, support size \(\tau\), total available slots, and input bit length—not the number of people represented by the masses. The marginal value of a proposed allocation can be computed by scanning the supported types and the listed slot probabilities. The expected direction is therefore Class A for these approximation tasks: the paper proves a generic adaptive submodular result that extends directly to this weighted type-mass coverage objective. The exact complexity of finding an optimal adaptive policy is a further question; these theorems do not settle it.
The weakest point is the shared type-level shock. In the paper’s original bipartite model, trials are independent customer by customer. Simply taking an infinite-population limit of those trials would generally make the observed reached fraction deterministic conditional on the allocation, erasing much of the value of adaptive feedback. The mirror I am proposing is therefore not that naïve limit: it is the segment-level delivery regime, where a type’s members share a campaign outcome. That is a real change to the stochastic model. It remains plausible as a mirror because the authors state Theorems 3 and 4 for the general adaptive monotone submodular framework, not only for independent individual-customer trials, and because a segment-level reach event is a recognizable campaign-planning object. The high-multiplicity bridge is exact for the segment model: discrete segment counts \(n_t\) correspond to \(\mu_t=n_t/n\), and the objective becomes reached people divided by \(n\).
A natural follow-up is to formalize the independent-individual version and determine whether, as multiplicities grow, adaptive feedback vanishes or retains useful information under richer customer types. That would test how far this mirror extends beyond the shared-shock regime.
Theorem 3 and Theorem 4 do not leave a new computational question for the proposed type-mass model. With a shared outcome for each type and slot, its objective is
\[ f_\omega(x)=\sum_{t\in T}\mu_t\, \mathbf{1}\{\text{some purchased slot reaches type }t\}. \]
That is a weighted coverage function in the paper’s own framework of adaptive monotone submodular functions over an integer lattice. Theorem 3 gives the \((1-1/e)\) guarantee against the stated expected-budget benchmark, with expected cost at most \(k\) and realized cost at most \(2k\). Theorem 4 gives the hard-budget guarantee. The type weights change the objective’s coefficients; they do not require a new algorithmic result. Marginal values can be evaluated over the \(\tau\) supported types, so the proponent’s parameterization is available directly. These two anchors are therefore applications of results already proved in the paper, not open mirrors for ChoCo to chart.
There is a more faithful continuum model, but it loses the feature those anchors are meant to study. In the paper, trial outcomes are independent for individual customers. If a type contains a continuum of such customers, the fraction reached after any fixed set of slots is deterministic: for type \(t\), it is \(\mu_t\) times the corresponding success probability. Observing that fraction supplies no random feedback, so an adaptive policy has no new information on which to condition. The resulting problem is a nonadaptive weighted budget allocation problem, closely matching the nonadaptive model and algorithms the paper already discusses.
One could preserve useful feedback by introducing a shared campaign shock, as the proposed mirror does. That is a plausible advertising scenario, but the uncertainty then resides in a finite set of type-level random events, not in independent outcomes across a large population. The masses scale the value of those events. This may be a sensible application of the paper’s theorem, but it is already covered by its general result; it does not reveal a new continuous-population complexity landscape. More elaborate latent-state models could escape the theorem, but their computational interest would come from the new uncertainty structure, not from making the society continuous.
So the strongest case against is that the natural independent-trial limit removes adaptivity, while the feedback-preserving version is already handled by Theorems 3 and 4. The case is not airtight: a high-multiplicity advertising audience with few response types is entirely plausible, and a direct type-mass formulation could still be useful to practitioners. But its usefulness would be as a compact application of known results, rather than a worthwhile new mirror for this programme.
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.