d4-conf-ijcai-2016-0255 (d4-conf-ijcai-2016-0255)

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 society is given by its support: a list \(T\) of \(\tau\) types with positive binary-rational masses \(\mu_t\) summing to \(1\); \(\tau\) is the support size, not the number of possible types.
There are \(m=|V|\) media, slot limits \(b_v\in\mathbb Z_{\ge0}\), a binary-rational budget \(k>0\), and explicitly listed binary-rational costs \(c(v,j)\ge0\) and probabilities \(q_{vti}\in[0,1]\), for \(1\le j,i\le b_v\). Ineligible medium–type pairs have probability zero. Assume \(\sum_{j=1}^{b_v}c(v,j)\le k\) for every medium. Put \(B=\sum_v b_v\), and let \(L\) be the total input bit length.
Independently draw \(\omega_{vti}\sim\operatorname{Bernoulli}(q_{vti})\); each outcome applies to all mass of type \(t\). A randomized adaptive policy starts at \(x=0\), buys only the next slot of a medium with \(x_v<b_v\), immediately observes all its type outcomes, and may stop; purchases cannot be undone.
For its terminal allocation, define \(F_\omega(x)=\sum_{t\in T}\mu_t\mathbf1\{\exists v,\ 1\le i\le x_v:\omega_{vti}=1\}\) and \(C(x)=\sum_{v\in V}\sum_{j=1}^{x_v}c(v,j)\).
Call a policy feasible if \(\mathbb E_r[C(x_{\omega,\pi,r})]\le k\) for every full outcome realization \(\omega\), where \(r\) is its internal randomness. Define \(\mathrm{OPT}_{\mathrm{exp}}(k)=\sup_{\pi\text{ feasible}}\mathbb E_{\omega,r}[F_\omega(x_{\omega,\pi,r})]\); comparator policies have no additional realized-cost cap.

Is there an algorithm, with construction and execution time polynomial in \(m,\tau,B,L\), producing an executable adaptive policy with \(\mathbb E_{\omega,r}[F_\omega(x)]\ge(1-1/e)\mathrm{OPT}_{\mathrm{exp}}(k)\), \(\mathbb E_r[C(x)]\le k\) for every \(\omega\), and \(C(x)\le2k\) on every run, or is attaining this guarantee NP-hard?

For finitely many individual customers with independent trials and the same per-medium cost restriction, a polynomial-time adaptive policy achieves this approximation and both cost guarantees. [Hatano, Fukunaga, and Kawarabayashi](https://www.ijcai.org/Proceedings/16/Papers/507.pdf)
No separate result explicitly treating the supported rational-mass model with outcomes shared by each type was located.

Partial result: the full guarantee for a stochastic subclass

The general polynomial-time-versus-hardness question remains unresolved here. I prove the requested guarantee for a subclass that includes every instance with at most one slot per medium, with arbitrary supported rational masses and arbitrary probabilities.

The subclass also permits multiple slots: after any initial free slots, each type’s success probability per unit cost must be nonincreasing along each medium. The proof compares against the task’s full comparator class, including policies without a realized-cost cap.

I also give a polynomial-size LP upper bound for general inputs and prove that its gap from the optimum is unbounded.

1. Precisely stated positive result

For each medium $v$, suppose there is an integer $z_v$ with $0\le z_v\le b_v$ such that

$$ c(v,i)=0\quad\text{for }i\le z_v, \qquad c(v,i)>0\quad\text{for }i>z_v. $$

Assume additionally that, for every type $t$,

$$ \frac{q_{vt,i}}{c(v,i)} \ge \frac{q_{vt,i+1}}{c(v,i+1)} \qquad (z_v<i<b_v). $$

Thus all free slots form an initial prefix, and the remaining probability-to-cost ratios decrease coordinatewise.

Theorem. Under these additional hypotheses, there is an algorithm with construction and worst-case execution time polynomial in $m,\tau,B,L$ producing an adaptive policy satisfying

$$ \mathbb E_{\omega,r}[F_\omega(x)] \ge (1-1/e)\mathrm{OPT}_{\mathrm{exp}}(k), $$

$$ \mathbb E_r[C(x)]\le k \quad\text{for every full realization }\omega, $$

and

$$ C(x)\le 2k \quad\text{on every run}. $$

When $b_v\le1$ for every medium, the additional hypotheses impose no restriction: a zero-cost slot is an initial free prefix, and a positive-cost singleton has no ratio-ordering condition to check.

The unrestricted-item analogue is fractional-budget adaptive greedy; see [Parthasarathy, Theorem 3](https://proceedings.mlr.press/v125/parthasarathy20a/parthasarathy20a.pdf). The argument below proves the comparison needed here directly and supplies a bounded-randomness implementation.

2. A valid conditional comparison with arbitrary adaptive policies

An observable history $H$ records the purchased slots, their order, and their outcomes. Throughout the probabilistic arguments, histories have positive probability.

Let $S(H)$ be its purchased slots, $U(H)$ its unreached types, and

$$ f(H)=\sum_{t\notin U(H)}\mu_t. $$

For an unpurchased slot $a=(v,i)$, define

$$ g(a\mid H)=\sum_{t\in U(H)}\mu_t q_{vti}. $$

This is its conditional expected incremental reward if the slot could be purchased immediately, irrespective of whether its predecessors have been purchased.

Indeed, the event specifying $H$ depends only on outcomes already observed. Independence of the trials therefore leaves every unobserved trial with its original probability. A currently unreached type contributes its mass exactly when this new trial succeeds.

Suppose that all zero-cost slots have already been purchased. Define

$$ \rho_{\mathrm{all}}(H) = \max_{a\notin S(H)} \frac{g(a\mid H)}{c_a}, $$

where $c_a=c(v,i)$, and the maximum is defined as zero if no slots remain.

Lemma. For every feasible comparator $\pi$, run from the empty allocation,

$$ \mathbb E_{\omega,r}[F_\omega(Y_\pi)\mid H] \le f(H)+k\rho_{\mathrm{all}}(H). $$

Here $Y_\pi$ denotes the comparator’s terminal allocation on the same full realization.

Proof. Starting after $H$, simulate $\pi$ from its original empty history. When $\pi$ requests a slot already in $S(H)$, supply its stored outcome without buying it again. Otherwise, purchase the requested slot and supply its outcome.

This simulation respects the prefix rule. If a requested slot is beyond the prefix purchased in $H$, its predecessors have already been requested by the simulated comparator and consequently are already available.

At any subsequent simulation history, the unreached types form a subset of $U(H)$. Hence, for every newly purchased slot $a$, its conditional expected incremental reward is at most

$$ g(a\mid H) \le c_a\rho_{\mathrm{all}}(H). $$

Summing these inequalities by conditional expectation over at most $B$ purchases gives

$$ \mathbb E[\text{additional covered mass}\mid H] \le \rho_{\mathrm{all}}(H) \mathbb E[\text{new purchase cost}\mid H]. $$

The new purchase cost is at most the original comparator’s cost on every realization and every choice of its internal randomness. Moreover, feasibility gives

$$ \mathbb E_{\omega,r}[C(Y_\pi)\mid H] = \mathbb E_\omega\!\left[ \mathbb E_r[C(Y_\pi)\mid\omega]\mid H \right] \le k. $$

The terminal union of $H$ and the simulated comparator’s purchases covers every type covered by the comparator. Its reward is therefore at least $F_\omega(Y_\pi)$, proving the lemma. $\square$

This argument never conditions a fixed-prefix reward on an adaptively chosen terminal prefix length.

Why the theorem’s ordering condition matters

After all initial free prefixes have been purchased, let $x$ be the allocation at history $H$. If $i>x_v$, the ordering assumption gives

$$ \frac{g((v,i)\mid H)}{c(v,i)} = \sum_{t\in U(H)} \mu_t\frac{q_{vti}}{c(v,i)} \le \sum_{t\in U(H)} \mu_t\frac{q_{vt,x_v+1}}{c(v,x_v+1)}. $$

Thus the highest density among all unpurchased slots is attained by an available next slot. Consequently,

$$ \rho_{\mathrm{all}}(H) = \max_{v:x_v<b_v} \frac{g((v,x_v+1)\mid H)}{c(v,x_v+1)}. $$

This equality supplies the connection between the valid comparison lemma and an executable greedy policy.

3. The policy and its cost guarantees

Fix a lexicographic order on slots for breaking ties.

Purchase every initial free prefix first. Then repeatedly choose an available next slot maximizing its conditional expected gain divided by its cost.

Let $s$ be the cost already spent and $c$ the selected slot’s cost.

• If no slots remain, or $s=k$, stop.
• If $s+c\le k$, buy the slot, observe its outcomes, and continue.
• If $s+c>k$, buy it with probability $p'$ and then stop, where

$$ 0\le p'\le p:=\frac{k-s}{c}. $$
Section 5 specifies $p'$ using polynomially many fair random bits.

For a fixed full realization $\omega$, all decisions before the final coin are deterministic. On a crossing branch,

$$ \mathbb E_r[C(x)\mid\omega] = s+p'c \le s+pc = k. $$

Every selected slot satisfies $c\le k$, because the entire cost of its medium is at most $k$. Thus the crossing purchase has realized cost

$$ s+c<2k. $$

Branches without a crossing purchase have cost at most $k$. These arguments apply to every full realization, including realizations of probability zero.

4. Approximation with an exact final coin

First analyze the ideal policy using $p'=p$. Write

$$ O=\mathrm{OPT}_{\mathrm{exp}}(k). $$

4.1 Continuous interpolation of greedy execution

For analysis only, continue the deterministic greedy rule without a budget limit until all slots have been purchased.

View a positive-cost slot as taking time equal to its cost, with its outcome revealed upon completion. The initial free purchases occur at time zero.

For a fixed time $t$, let $H_t$ be the history of completed purchases. If a slot is in progress, let $s_t$ be its starting time and put

$$ a_t=t-s_t, \qquad \rho_t=\rho_{\mathrm{all}}(H_t). $$

If execution has finished, set $a_t=\rho_t=0$. Define

$$ W(t)=\mathbb E[f(H_t)+a_t\rho_t], \qquad R(t)=\mathbb E[\rho_t]. $$

For each possible $H_t$, the event specifying that history depends only on its observed outcomes: both the next slot and its cost are determined by the history. Thus the conditional comparison lemma applies to these histories.

The greedy decision tree is finite. Its interval endpoints are cumulative purchase costs. Between consecutive endpoints, $W$ is affine and

$$ W'(t)=R(t) $$

except at the finitely many endpoints.

Also, $W$ is continuous. At completion of a slot of cost $c$, the interpolated gain immediately before completion is $c\rho_t$, exactly its conditional expected actual gain. Averaging over the revealed outcome therefore matches the expected reward immediately after completion.

Let

$$ A=W(0) $$

be the expected reward of the initial free purchases. In particular, $A\ge0$.

At time $k$, fractional interpolation matches the exact final coin:

$$ W(k)=\mathbb E[F_\omega(x_{\mathrm{ideal}})]. $$

Indeed, an in-progress slot starting at cost $s<k$ is purchased with probability $(k-s)/c$, contributing expected gain $(k-s)\rho_t$.

4.2 Differential comparison

For every feasible comparator, Section 2 gives

$$ \mathbb E[F_\omega(Y_\pi)] \le \mathbb E[f(H_t)]+kR(t). $$

Taking the supremum over comparators yields

$$ O \le W(t)-\mathbb E[a_t\rho_t]+kR(t). $$

Therefore, almost everywhere,

$$ W'(t)+\frac{W(t)}k \ge \frac Ok+\frac{\mathbb E[a_t\rho_t]}k. $$

Multiplying by $e^{t/k}$ and integrating from zero to $k$ gives

$$ W(k) \ge (1-e^{-1})O+\frac Ae + \frac1{ek} \int_0^k e^{t/k}\mathbb E[a_t\rho_t]\,dt. $$

All the extra terms are nonnegative, so this already proves the ideal policy’s approximation guarantee.

4.3 A positive margin for finite randomness

To implement the final coin with boundedly many fair bits, we need a quantified margin.

Let $D$ be the product of the denominators of $k$ and all positive slot costs, and put

$$ \delta=\frac1D. $$

Every cumulative purchase cost and $k$ is an integer multiple of $\delta$. Hence every nonempty greedy interval intersected with $[0,k]$ has length at least $\delta$.

On a single outcome path, let these interval lengths be $h_\ell$ and their densities be $\rho_\ell$. Then

$$ \int_0^k a_t\rho_t\,dt = \frac12\sum_\ell \rho_\ell h_\ell^2 \ge \frac{\delta}{2}\sum_\ell\rho_\ell h_\ell. $$

Taking expectations and using $W'=R$ gives

$$ \int_0^k\mathbb E[a_t\rho_t]\,dt \ge \frac{\delta}{2}(W(k)-A). $$

Since $e^{t/k}\ge1$, the preceding differential bound implies

$$ W(k) \ge (1-e^{-1})O+\frac Ae + \frac{\delta}{2ek}(W(k)-A). $$

Set $\theta=\delta/(2ek)$. Because $k$ is a positive integer multiple of $\delta$, we have $\delta\le k$, and therefore

$$ \frac1e-\theta\ge0. $$

It follows that

$$ W(k)\ge(1-e^{-1})O+\theta W(k). $$

Using $W(k)\ge(1-e^{-1})O$ once more,

$$ W(k) \ge (1-e^{-1})O + \frac{1-e^{-1}}{2e}\frac{\delta}{k}O. $$

The elementary inequalities $2<e<3$ imply

$$ \frac{1-e^{-1}}{2e}>\frac1{12}. $$

For completeness, $e>2$ follows from its power series, while $e<3$ follows by comparing $1/n!$ with $1/2^{n-1}$ for $n\ge2$, with strict inequality for some terms.

Thus

$$ W(k) \ge \left(1-\frac1e+\frac{\delta}{12k}\right)O. $$

The margin can be exponentially small numerically, but its binary description has polynomial length.

5. Bounded randomness and polynomial time

If $B=0$, or every listed probability is zero, stopping immediately is optimal. Otherwise some slot has $q_{vti}>0$.

Buying that medium’s full prefix is feasible, since its total cost is at most $k$. It gives expected reward at least $\mu_t q_{vti}$. A positive input rational is at least $2^{-L}$, so

$$ O\ge\mu_t q_{vti}\ge2^{-2L}. $$

The number

$$ n=kD $$

is a positive integer. Choose

$$ a=2L+\left\lceil\log_2(24n)\right\rceil $$

and use the final purchase probability

$$ p'=\frac{\lfloor2^ap\rfloor}{2^a}. $$

This coin uses exactly $a$ fair random bits: draw a uniform integer from $\{0,\ldots,2^a-1\}$ and compare it with $\lfloor2^ap\rfloor$.

Rounding down the one final coin loses at most $2^{-a}$ expected reward, because total mass is one. Moreover,

$$ 2^{-a} \le \frac{2^{-2L}}{24kD} = \frac{\delta}{24k}2^{-2L} \le \frac{\delta}{24k}O. $$

Combining this loss with Section 4 gives

$$ \mathbb E[F_\omega(x)] \ge \left(1-\frac1e+\frac{\delta}{24k}\right)O \ge (1-1/e)O. $$

The cost guarantees hold because $p'\le p$.

Finally, $D$, $n$, and $a$ have polynomial bit length. Each density calculation uses

$$ g((v,i)\mid H)=\sum_{t\in U(H)}\mu_t q_{vti}, $$

with one summand per listed type. Products, sums, and comparisons have polynomial bit complexity. There are at most $B$ purchases, and each selection examines at most $m$ available slots. The policy stores the current prefixes and reached types; it does not construct the potentially exponential decision tree used in the proof.

This completes the theorem.

6. A general LP upper bound—and an unbounded gap

The following bound applies without the theorem’s additional hypotheses.

Introduce variables $p_{vi}$ for slot purchase probabilities and $z_t$ for type coverage probabilities. Consider the LP maximizing

$$ \sum_{t\in T}\mu_t z_t $$

subject to

$$ 0\le p_{vi}\le1, \qquad p_{v,i+1}\le p_{vi}, $$

$$ 0\le z_t\le1, \qquad z_t\le\sum_v\sum_{i=1}^{b_v}q_{vti}p_{vi}, $$

and

$$ \sum_v\sum_{i=1}^{b_v}c(v,i)p_{vi}\le k. $$

Proposition. Its optimal value is an upper bound on $\mathrm{OPT}_{\mathrm{exp}}(k)$.

Proof. For any feasible policy, set $p_{vi}$ equal to the probability that slot $(v,i)$ is bought, and $z_t$ equal to the probability that type $t$ is reached.

The prefix inequalities follow because buying slot $i+1$ requires buying slot $i$. Integrating the pointwise expected-cost constraint over $\omega$ proves the LP’s budget constraint.

The event that a slot is bought is independent of that slot’s previously unobserved outcome. To see this, fix the internal randomness and all other trials. Changing the slot’s outcome cannot change whether it is purchased: the two executions coincide until that purchase, and purchases cannot be undone. Consequently,

$$ \Pr((v,i)\text{ bought and }\omega_{vti}=1) = p_{vi}q_{vti}. $$

The union bound gives the constraint on $z_t$. The LP objective is exactly the policy’s expected reward. Taking the supremum proves the proposition. $\square$

This is a bounded rational LP with $B+\tau$ variables and polynomial encoding length, so polynomial-time rational linear programming computes its optimum.

An explicit unbounded gap

Let $M\ge2$ be a power of two. Take $M$ media and $M$ types, each of mass $1/M$, and set $k=1$. Medium $v$ reaches only its corresponding type.

Each medium has $M+1$ slots:

$$ c(v,1)=\frac12, \qquad c(v,i)=\frac1{2M}\quad(2\le i\le M+1), $$

$$ q_{v,t_v,1}=0, \qquad q_{v,t_v,i}=1\quad(2\le i\le M+1). $$

All other probabilities are zero. Every medium’s total cost is one.

On the unique positive-probability realization, reaching a type requires buying at least the first two slots of its medium, at cost

$$ a_M=\frac{M+1}{2M}. $$

If $N$ types are reached, every run on that realization satisfies $C\ge a_MN$. Hence every feasible comparator satisfies

$$ \mathbb E[F] = \frac{\mathbb E[N]}M \le \frac1{Ma_M} = \frac2{M+1}. $$

Equality is achievable: buy the first two slots of one medium, and do so for a second distinct medium with probability

$$ \frac{M-1}{M+1}. $$

Its expected cost is exactly one on every full realization. Therefore,

$$ \mathrm{OPT}_{\mathrm{exp}}(1)=\frac2{M+1}. $$

In the LP, set every $p_{vi}=1/M$ and every $z_t=1$. The total cost is one, and each type’s probability-sum constraint has right-hand side

$$ M\cdot\frac1M=1. $$

Thus the LP optimum is one, and

$$ \frac{\mathrm{LP}}{\mathrm{OPT}_{\mathrm{exp}}(1)} = \frac{M+1}{2}. $$

The gap is unbounded. This relaxation alone cannot supply a constant-factor comparison with the optimum.

7. Why the general case remains open

The proof above requires the unrestricted maximum individual-slot density to be attained by an available slot. Arbitrary input sequences need not satisfy this property.

Replacing unrestricted individual-slot density by fixed-prefix density also fails. Consider one type of mass one, one medium, two slots, and $k=1$, with

$$ (c_1,c_2)=\left(\frac12,\frac12\right), \qquad (q_1,q_2)=\left(\frac12,1\right). $$

At the empty history, both fixed prefixes have expected gain divided by cost equal to one. But buying the first slot and buying the second only after failure gives expected reward one and expected cost

$$ \frac12+\frac12\cdot\frac12=\frac34. $$

Thus the proposed comparison

$$ \text{adaptive expected gain} \le \text{maximum fixed-prefix density} \cdot \text{adaptive expected cost} $$

would assert $1\le3/4$.

The unrestricted individual-slot comparison proved in Section 2 remains valid: the second slot has density two. The difficulty is that this slot is initially inaccessible. Accounting for such later opportunities, while retaining the pointwise expected-budget guarantee, is the unresolved part.

⟨structured verdict parsed — rendered above⟩

The output establishes a correct polynomial-time result for its stated subclass, a valid LP upper bound for general inputs, and an unbounded gap for that LP. It does not resolve the unrestricted algorithm-versus-hardness question in USER_TASK, as the prover explicitly acknowledges.

I found no false substantive step in the subclass proof. There is one minor clarification concerning the independence of the comparator’s randomness in the conditional comparison lemma.

• Scope and additional hypotheses

The positive theorem assumes that all zero-cost slots form initial prefixes and that, after those prefixes,
$$ \frac{q_{vt,i}}{c(v,i)} \ge \frac{q_{vt,i+1}}{c(v,i+1)} $$
for every type and every consecutive pair of remaining slots.

These are additional restrictions absent from USER_TASK. The assertion that they impose no restriction when every medium has at most one slot is correct, including empty media and zero-cost singleton slots.

Major scope issue: proving this restricted theorem does not establish either alternative requested for arbitrary input sequences. This is an acknowledged limitation, rather than an incorrect claim of completeness.

Minimum additional work needed: resolve the unrestricted guarantee or prove the requested hardness result. Further clarification of the existing subclass proof cannot close this scope gap.

• Conditional gains and the comparison lemma

The formula
$$ g(a\mid H)=\sum_{t\in U(H)}\mu_tq_{vti} $$
is correct. Observing outcomes of purchased slots does not change the distribution of unobserved trials. Sharing an outcome across all mass of a type changes the contribution to $\mu_t$; it does not invalidate independence between distinct listed trials.

The simulation respects the prefix rule. A requested slot outside the prefix already purchased in $H$ has all its predecessors available because the simulated comparator must previously have requested them.

For each new purchase, the currently unreached types are a subset of $U(H)$. Its conditional expected incremental reward is therefore at most $g(a\mid H)$. Summing over at most $B$ purchases is legitimate, and every newly purchased slot has positive cost under the lemma’s premise that all zero-cost slots were already purchased.

The new-purchase cost is pathwise bounded by the comparator’s original cost. The terminal union also pathwise covers everything covered by the comparator. These observations justify the reward comparison without imposing a realized-cost cap on the comparator.

Minor clarification: the comparator must use fresh internal randomness independent of the process generating $H$. Otherwise, conditioning on $H$ can reveal the comparator’s random choices, and the displayed identity
$$ \mathbb E_{\omega,r}[C(Y_\pi)\mid H] = \mathbb E_\omega\!\left[ \mathbb E_r[C(Y_\pi)\mid\omega]\mid H \right] $$
need not hold.

This does not undermine the application in Section 4: the unlimited greedy history there is generated deterministically from observed outcomes, and a comparator can be run with independent randomness.

Minimum clarification needed: explicitly state that the simulated comparator uses a fresh seed independent of $\omega$ and of the history-generating process.

• Connecting unrestricted density to an available slot

The coordinatewise ratio assumption correctly yields
$$ \frac{g((v,i)\mid H)}{c(v,i)} \le \frac{g((v,x_v+1)\mid H)}{c(v,x_v+1)} $$
whenever $i>x_v$. All denominators here are positive because the initial free prefixes have already been purchased.

Taking the maximum therefore gives the claimed equality between unrestricted maximum density and maximum available-next-slot density. Empty media and exhausted media create no exception.

This is precisely where the proof needs its additional ordering assumption.

• Policy feasibility and realized-cost bound

For a fixed full realization, purchases before the final coin are deterministic. On a crossing branch,
$$ \mathbb E_r[C(x)\mid\omega]=s+p'c\le k $$
follows directly from $p'\le(k-s)/c$.

Each slot costs at most $k$ because costs are nonnegative and the total cost of its medium is at most $k$. Since a crossing branch has $s<k$,
$$ s+c<2k. $$

Runs without a crossing purchase cost at most $k$. The reasoning applies to every full realization, including those of probability zero. The policy also respects the prefix rule and never undoes purchases.

• Continuous interpolation and approximation with the exact coin

The unlimited greedy decision tree is finite. Between its finitely many cumulative-cost endpoints, completed histories and selected densities remain fixed, so
$$ W'(t)=R(t) $$
holds away from those endpoints.

Continuity of $W$ at a completion follows from conditional expectation: the interpolation contributes $c\rho_t$, exactly the selected slot’s expected incremental reward given its starting history. Averaging over its newly revealed outcomes matches the post-completion reward.

Conditioning on $H_t$ does not expose an unfinished slot’s outcomes. Its starting time and selected cost are determined by the completed history, so the comparison lemma remains applicable.

The identification
$$ W(k)=\mathbb E[F_\omega(x_{\mathrm{ideal}})] $$
is correct, including the cases where execution ends before $k$ or a purchase finishes exactly at $k$.

The comparison lemma gives
$$ O\le W(t)-\mathbb E[a_t\rho_t]+kR(t). $$
The resulting differential inequality and integrating-factor calculation are correct. Taking the supremum over comparator policies does not require the supremum to be attained.

• Quantified margin and bounded randomness

The lattice argument is valid. The denominator product $D$ makes every slot cost, cumulative purchase cost, and $k$ an integer multiple of $\delta=1/D$. Thus every positive-length purchase interval clipped to $[0,k]$ has length at least $\delta$.

On each such interval,
$$ \int a_t\rho_t\,dt=\frac{\rho_\ell h_\ell^2}{2}. $$
The resulting inequality
$$ \int_0^k\mathbb E[a_t\rho_t]\,dt \ge \frac{\delta}{2}(W(k)-A) $$
follows from the already established derivative identity. Time after all purchases finish contributes zero.

The algebra eliminating $A$ is correct because
$$ \frac1e-\frac{\delta}{2ek}\ge0. $$
The constant estimate
$$ \frac{1-e^{-1}}{2e}>\frac1{12} $$
also follows from the stated bounds on $e$.

If any listed probability is positive, purchasing its medium’s full prefix is feasible and establishes
$$ O\ge2^{-2L}. $$
The rounding loss is at most $2^{-a}$ because only one final purchase probability is rounded and total reward is at most one. The chosen number of bits makes this loss smaller than the proved margin.

The zero-slot and all-zero-probability cases are handled correctly.

• Polynomial construction and execution

The denominator product has polynomial bit length, and
$$ \log_2(kD) $$
is polynomially bounded by the input length. Consequently, the number $a$ of fair random bits is polynomially bounded in value, not merely representable with polynomially many bits.

Exact gain sums, density comparisons, and final-coin calculations have polynomial bit complexity. At most $B$ purchases occur, with at most $m$ candidates examined at each selection. The implementation stores prefixes and reached types rather than enumerating the analysis decision tree.

The construction and worst-case execution claims therefore follow.

The reference to Parthasarathy is contextual rather than a theorem application on which this proof depends. Its cited theorem does concern fractional-budget adaptive greedy; the output supplies its own comparison and analysis. [Parthasarathy, Theorem 3](https://proceedings.mlr.press/v125/parthasarathy20a/parthasarathy20a.pdf)

• General LP upper bound

The prefix inequalities are necessary for purchase probabilities. Integrating the pointwise expected-cost constraint correctly gives the LP budget constraint.

A slot’s purchase event is independent of its own unobserved outcome. Fixing internal randomness and all other trials makes this explicit: changing that outcome cannot change whether the slot is purchased, since it is unavailable to the policy before purchase.

Thus
$$ \Pr((v,i)\text{ bought and }\omega_{vti}=1)=p_{vi}q_{vti}, $$
and the union bound supplies the coverage constraint. The LP objective equals the policy’s expected reward.

The LP is feasible, bounded, and rational, with polynomially many variables, constraints, and coefficient bits. Its claimed polynomial-time solvability is applicable. This establishes an efficiently computable upper bound, not an approximation algorithm.

• Unbounded LP-gap example

All probabilities are deterministic, so there is exactly one positive-probability outcome realization. Reaching any type requires expenditure at least
$$ a_M=\frac{M+1}{2M}. $$
Hence the stated upper bound on the comparator optimum is correct.

The proposed randomized schedule attains equality:
$$ a_M\left(1+\frac{M-1}{M+1}\right)=1, $$
and its expected covered mass is $2/(M+1)$. Its purchase schedule does not depend on outcomes, so the expected-cost condition holds even on zero-probability realizations.

The LP assignment has total cost one and coverage right-hand side one for each type. Its objective is one, which is optimal because total mass is one. Therefore the gap is indeed
$$ \frac{M+1}{2}. $$

This disproves a constant-factor comparison between this LP and the optimum. It does not prove hardness of the original problem.

• Fixed-prefix-density counterexample and remaining conclusion

Both fixed prefixes have density one. The adaptive policy reaches the type surely and costs
$$ \frac12+\frac12\cdot\frac12=\frac34 $$
in expectation. The proposed density-times-expected-cost comparison would therefore be false.

This example correctly identifies a failure of that comparison. It violates the subclass’s ordering condition, so it does not contradict the positive theorem.

The genuine progress is the subclass theorem, the general upper bound, and the two demonstrated limitations. The unrestricted guarantee and its possible NP-hardness remain unsettled.

⟨structured verdict parsed — rendered above⟩