Answer: Yes. A deterministic nonanticipative measurable subset-valued policy guarantees $1-1/e$ on every allowed continuous stream, and the optimal uniform competitive ratio is $1-1/e$. The attaining construction uses countably many allocation changes; finite implementations achieve $1-1/e-\varepsilon$ in polynomial time.
Theorem 1 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateUnder the small bid assumption, the video-ad allocation problem admits a polynomial-time (1 −1/e −ϵ)- competitive algorithm for any constant ϵ > 0, and a pseudo- polynomial time (1 −1/e)-competitive algorithm. Although the competitive ratio given in the above depends on Rmax, Goel et al. did not describe how it depends on Rmax explicitly. In the subsequent section, we analyze the compet- itive ratio of an algorithm that extends the one of Goel et al., describing its dependence on Rmax.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a unit-mass ordered stream \(\theta(u)\), \(u\in[0,1]\), of finite-support request types \(\theta=(T_\theta,(b_i(\theta))_{i\in N})\), with fixed ad lengths \(t_i\), each infinitesimal request must receive an integral set \(S(u)\subseteq N\) satisfying \(\sum_{i\in S(u)}t_i\le T_{\theta(u)}\). Advertiser \(i\)'s total spend is \(\int_0^1 b_i(\theta(u))\mathbf{1}[i\in S(u)]\,du\le B_i\), and revenue is the integral of the total payments. For finite, rationally encoded stream profiles whose future is hidden from the policy, determine whether a nonanticipative policy can guarantee revenue at least \((1-1/e)\) times the offline optimum in the limit where per-request bids are negligible relative to budgets scaled with population size; also determine the best achievable ratio if that guarantee fails.
Let \(N=\{1,\ldots,m\}\) be advertisers with fixed lengths \(t_i>0\) and normalized budgets \(B_i>0\). A request type is \(\theta=(T_\theta,(b_i(\theta))_{i\in N})\), with \(T_\theta\ge0\) and \(b_i(\theta)\ge0\); all numerical input is binary rational.
A society is given by its support: the list of the \(\tau\) types with positive binary-rational masses summing to \(1\). Here \(\tau\) is the support size, not the number of possible types. Its ordered stream \(\theta(u)\), \(u\in[0,1]\), is encoded by \(k\) constant-type blocks with rational endpoints and those aggregate masses. Let \(L\) be the total input bit length; state running times in \(m,\tau,L,k\) and any accuracy parameters.
The stream is adversarial. A deterministic policy knows the advertisers, lengths, budgets and unit horizon initially, but learns request types only as they arrive; support, aggregate masses, future block boundaries and future types are hidden. Its irrevocable allocation at \(u\) depends only on this initial information and the observed prefix.
An allocation is a measurable map \(S(u)\subseteq N\), with \(\sum_{i\in S(u)}t_i\le T_{\theta(u)}\) almost everywhere; the empty set is allowed. Advertiser \(i\)'s cumulative spend \(\int_0^v b_i(\theta(u))\mathbf1[i\in S(u)]\,du\) must never exceed \(B_i\), for every \(v\in[0,1]\). Payments equal bids, and revenue is \(\operatorname{REV}(S)=\int_0^1\sum_{i\in S(u)}b_i(\theta(u))\,du\). Let \(\operatorname{OPT}\) be the supremum revenue of feasible measurable allocations knowing the entire stream.
The infinitesimal regime uses population size \(q\): physical budgets are \(qB_i\), individual bids remain \(b_i(\theta)\), and revenues are divided by \(q\). Thus \(\max_{i,\theta}b_i(\theta)/(qB_i)\to0\) as \(q\to\infty\); the displayed integrals define the limiting problem.
Can a deterministic nonanticipative policy guarantee \(\operatorname{REV}\ge(1-1/e)\operatorname{OPT}\) for every such continuous stream? If not, what is the supremum achievable worst-case competitive ratio?
For discrete video-ad allocation, under infinitesimal bids relative to budgets, polynomial-time policies attain \(1-1/e-\varepsilon\) for every fixed \(\varepsilon>0\), and a pseudo-polynomial-time policy attains the limiting ratio \(1-1/e\). [Source](https://www.ijcai.org/proceedings/2017/0060.pdf)
For fractional AdWords, which has a single allocation slot per request rather than a knapsack constraint, a \((1-1/e)\)-competitive policy is known under adversarial arrivals. [Source](https://arxiv.org/pdf/1308.5444)
No result settling exactly the continuous stream problem defined above was located.
Yes. A deterministic nonanticipative policy can guarantee
$$
\operatorname{REV}\ge \left(1-\frac1e\right)\operatorname{OPT}
$$
on every stream in the question. The optimal uniform competitive ratio is therefore $1-1/e$.
The exact policy constructed below is a measurable policy with countably many allocation changes, potentially accumulating at the start of each observed constant-type interval. Such allocations are permitted by the stated model. This construction does not establish a finite running-time implementation of the exact guarantee.
I also give a finite implementation attaining $1-1/e-\varepsilon$ in time polynomial in $m,\tau,L,k,\varepsilon^{-1}$ and the binary encoding length of $\varepsilon$.
Competitive ratios here are uniform over all finite instances, including arbitrary $m$. For $m=1$, allocating whenever feasible until exhaustion is optimal.
Write $X_i(u)$ for advertiser $i$’s spend divided by $B_i$. Define
$$
g(x)=\frac{e^x-1}{e-1},
\qquad
C=\frac{e}{e-1}.
$$
For $0\le x\le1$,
$$
g(0)=0,\qquad g(1)=1,\qquad
g'(x)+1-g(x)=C.
$$
For a normalized spending vector $x\in[0,1]^m$, define
$$
\Phi(x)=\sum_{i=1}^m B_i\int_0^{x_i}(1-g(s))\,ds.
$$
Its gradient has coordinates
$$
\frac{\partial\Phi}{\partial x_i}(x)=B_i(1-g(x_i)).
$$
For a type $\theta$, let $\mathcal F_\theta$ be its finite family of feasible subsets, including the empty set. Define
$$
z_\theta(x)=
\max_{S\in\mathcal F_\theta}
\sum_{i\in S}b_i(\theta)(1-g(x_i)).
$$
This function is nonnegative and coordinatewise nonincreasing on $[0,1]^m$.
The key condition for a constant-type interval $[a,b]$ is
$$
\Phi(X(b))-\Phi(X(a))
\ge
(b-a)z_\theta(X(b)).
$$
We will construct a deterministic subset-valued schedule satisfying this inequality for every possible stopping time $b$, using only the type observed at $a$, the current spending, and the remaining horizon.
First, I prove that this condition suffices.
Let $[a_\ell,a_{\ell+1}]$, for $0\le\ell<k'$, be the maximal constant-type intervals of the stream. Adjacent encoded blocks of the same type can be merged, so $k'\le k$. Set
$$
\bar\alpha_i=g(X_i(1)).
$$
For any feasible offline subset $A$ during interval $\ell$, monotonicity of spending gives
$$
\begin{aligned}
\sum_{i\in A}b_i(\theta_\ell)
&=
\sum_{i\in A}\bar\alpha_i b_i(\theta_\ell)
+
\sum_{i\in A}(1-\bar\alpha_i)b_i(\theta_\ell)\\
&\le
\sum_{i\in A}\bar\alpha_i b_i(\theta_\ell)
+
z_{\theta_\ell}(X(a_{\ell+1})).
\end{aligned}
$$
Indeed, $\bar\alpha_i\ge g(X_i(a_{\ell+1}))$.
Integrating this inequality for any feasible offline allocation and using its budget constraints yields
$$
\operatorname{OPT}
\le
\sum_i B_i g(X_i(1))
+
\sum_{\ell=0}^{k'-1}
(a_{\ell+1}-a_\ell)
z_{\theta_\ell}(X(a_{\ell+1})).
$$
This holds for the supremum defining $\operatorname{OPT}$; an offline maximizer is unnecessary.
If the displayed block condition holds, the sum telescopes:
$$
\operatorname{OPT}
\le
\sum_iB_i g(X_i(1))+\Phi(X(1))-\Phi(X(0)).
$$
Initially $X(0)=0$ and $\Phi(0)=0$. The identity defining $C$ gives, for every $x\in[0,1]$,
$$
g(x)+\int_0^x(1-g(s))\,ds=Cx.
$$
Consequently,
$$
\operatorname{OPT}
\le C\sum_iB_iX_i(1)
=C\operatorname{REV}.
$$
Thus it remains to construct the block schedules.
Fix a current type $\theta$, an initial state $x^0\in[0,1]^m$, and a hypothetical continuation duration $D>0$. In this section, the type remains fixed throughout $[0,D]$.
For $S\in\mathcal F_\theta$, define its normalized spending rate by
$$
(v_S)_i=\frac{b_i(\theta)}{B_i}\mathbf1[i\in S].
$$
Let
$$
K=\operatorname{conv}\{v_S:S\in\mathcal F_\theta\},
\qquad
V=\left(\sum_i\left(\frac{b_i(\theta)}{B_i}\right)^2\right)^{1/2}.
$$
Every vector in $K$ is nonnegative and has Euclidean norm at most $V$.
We use a relaxed trajectory $x:[0,D]\to[0,1]^m$ satisfying, almost everywhere,
$$
x'(s)\in
\operatorname*{arg\,max}_{v\in K}
\nabla\Phi(x(s))\cdot v,
\qquad
x(0)=x^0.
$$
This trajectory is only a reference used to construct the actual subset-valued schedule.
Here is an explicit existence argument.
Extend $g$ by its exponential formula to all real arguments. Partition $[0,D]$ into equal steps of length $\Delta$, and at each step choose a maximizing vector in $K$ at the current state. Linearly interpolate the resulting Euler trajectory.
The feasible family is closed under deletion. Therefore, if $v\in K$, replacing its $i$th coordinate by zero leaves a vector in $K$: apply deletion of $i$ to every subset in a convex decomposition of $v$.
If the current coordinate satisfies $x_i>1$, then $B_i(1-g(x_i))<0$. Maximization consequently forces $v_i=0$. An Euler trajectory can therefore overshoot the bound $1$ in coordinate $i$ by at most
$$
\Delta\,\frac{b_i(\theta)}{B_i}.
$$
Its coordinates never decrease, and its velocity norm is at most $V$.
The Euler trajectories are uniformly bounded and uniformly Lipschitz. By Arzelà–Ascoli, a sequence with $\Delta\to0$ has a uniformly convergent subsequence. Their derivatives have a weakly convergent subsequence in $L^2$. Denote the limits by $x$ and $v$.
Integration against interval indicators gives
$$
x(s)=x^0+\int_0^s v(r)\,dr.
$$
The limit lies in $[0,1]^m$ by the overshoot bound. Also, $v(s)\in K$ almost everywhere: each linear inequality defining the compact polytope $K$ passes to the weak limit after integration against nonnegative test functions.
For each vertex $w=v_S$ of $K$, the Euler maximization inequalities are
$$
\nabla\Phi(x_\Delta(\text{left endpoint}))\cdot v_\Delta
\ge
\nabla\Phi(x_\Delta(\text{left endpoint}))\cdot w.
$$
The gradient coefficients converge uniformly. Integrating against nonnegative test functions and passing to the weak limit proves
$$
\nabla\Phi(x(s))\cdot v(s)
\ge
\nabla\Phi(x(s))\cdot w
$$
almost everywhere, simultaneously for all finitely many vertices. Thus $v=x'$ satisfies the required maximization rule.
Uniqueness makes the reference trajectory a deterministic function of the currently known information.
Define the strictly convex function
$$
\Psi(x)=\sum_i B_i\int_0^{x_i}g(s)\,ds.
$$
Then
$$
\nabla\Phi(x)=B-\nabla\Psi(x),
$$
where $B$ is the vector of budgets.
Suppose $x$ and $y$ are two reference trajectories with the same initial state. Their maximization inequalities imply
$$
\bigl(\nabla\Psi(x)-\nabla\Psi(y)\bigr)\cdot(x'-y')
\le0
$$
almost everywhere.
On $[0,1]^m$, the Hessian of $\Psi$ is uniformly positive definite. Specifically, with
$$
\lambda=\frac{\min_i B_i}{e-1}>0,
\qquad
M=\frac{e\max_i B_i}{e-1},
$$
its least eigenvalue is at least $\lambda$, and its Hessian is Lipschitz with constant at most $M$ in Euclidean norm.
Consider the Bregman divergence
$$
\mathcal D(x,y)
=
\Psi(x)-\Psi(y)-\nabla\Psi(y)\cdot(x-y).
$$
It satisfies
$$
\mathcal D(x,y)\ge\frac{\lambda}{2}\|x-y\|^2.
$$
Differentiating along the trajectories and using the preceding maximization inequality gives
$$
\begin{aligned}
\mathcal D'
&=
(\nabla\Psi(x)-\nabla\Psi(y))\cdot x'
-
(\nabla^2\Psi(y)y')\cdot(x-y)\\
&\le
\bigl(
\nabla\Psi(x)-\nabla\Psi(y)
-\nabla^2\Psi(y)(x-y)
\bigr)\cdot y'\\
&\le
\frac{MV}{2}\|x-y\|^2
\le
\frac{MV}{\lambda}\mathcal D.
\end{aligned}
$$
The Taylor remainder bound uses the stated Hessian Lipschitz constant, and $\|y'\|\le V$. Since $\mathcal D(0)=0$, Gronwall’s inequality gives $\mathcal D\equiv0$. Hence $x=y$.
Write
$$
z(s)=z_\theta(x(s)).
$$
The chain rule and the maximization rule give
$$
\frac{d}{ds}\Phi(x(s))=z(s)
$$
almost everywhere.
We also need the following derivative identity:
$$
z'(s)
=
-\sum_i B_i g'(x_i(s))(x_i'(s))^2
$$
almost everywhere.
To verify it, define, for each feasible subset $S$,
$$
f_S(s)=\sum_{i\in S}b_i(\theta)(1-g(x_i(s))).
$$
These functions, and their finite maximum $z$, are absolutely continuous. On the set where $f_S=z$, their derivatives agree almost everywhere: an absolutely continuous function has derivative zero almost everywhere on its zero set.
At almost every $s$, decompose the maximizing velocity as
$$
x'(s)=\sum_S\lambda_S v_S,
\qquad
\lambda_S\ge0,\qquad \sum_S\lambda_S=1.
$$
Any subset with $\lambda_S>0$ is a maximizer, because its objective value cannot exceed $z(s)$ and their convex average equals $z(s)$. Therefore
$$
\begin{aligned}
z'(s)
&=\sum_S\lambda_S f_S'(s)\\
&=
-\sum_i b_i(\theta)g'(x_i(s))x_i'(s)
\sum_{S\ni i}\lambda_S\\
&=
-\sum_i B_i g'(x_i(s))(x_i'(s))^2.
\end{aligned}
$$
For a zero bid, both the corresponding rate and its contribution vanish.
Thus $z$ is nonincreasing. Whenever $z(s)>0$, the maximizing velocity is nonzero, so $z'(s)<0$ almost everywhere on that set.
If $z(0)>0$, it follows that for every $s>0$,
$$
\begin{aligned}
F(s)
&:=
\Phi(x(s))-\Phi(x^0)-s z_\theta(x(s))\\
&=
\int_0^s(z(r)-z(s))\,dr
>0.
\end{aligned}
$$
For completeness, continuity ensures $z>0$ on an initial interval, where it strictly decreases. This gives a strictly positive integral for every sufficiently small $s>0$; monotonicity of $z$ preserves positivity for larger $s$.
This strictly positive slack permits replacement of the reference trajectory by a subset-valued schedule.
Continue with the fixed type, state $x^0$, and duration $D$.
If $z_\theta(x^0)=0$, select the empty set throughout. The state remains fixed and the required block inequality holds with equality.
Suppose instead that $z_\theta(x^0)>0$. Let $x$ be the reference trajectory from Section 3.
For $0\le s\le D$ and $y\in[0,1]^m$, define
$$
G(s,y)=\Phi(y)-\Phi(x^0)-s z_\theta(y).
$$
There is a finite constant $Q>0$ such that
$$
|G(s,y)-G(s,\widetilde y)|
\le Q\|y-\widetilde y\|
$$
uniformly over this domain. One valid choice is
$$
Q=
\left(\sum_iB_i^2\right)^{1/2}
+
D\frac{e}{e-1}
\left(\sum_i b_i(\theta)^2\right)^{1/2}.
$$
Indeed, $\|\nabla\Phi\|\le\|B\|$, while every function in the finite maximum defining $z_\theta$ has gradient norm at most $e\|b(\theta)\|/(e-1)$.
Partition $(0,D]$ into dyadic shells
$$
I_n=[D2^{-(n+1)},D2^{-n}],
\qquad n=0,1,\ldots.
$$
By Section 3, $F(s)=G(s,x(s))$ is continuous and strictly positive for $s>0$. Hence
$$
\delta_n=\min_{s\in I_n}F(s)>0.
$$
Subdivide each shell into finitely many equal intervals, with mesh small enough that every resulting interval $[r,t]$ satisfies
$$
QV(t-r)\le\frac{\delta_n}{2}.
$$
For each such interval, the average reference velocity
$$
\bar v_{r,t}=\frac{x(t)-x(r)}{t-r}
$$
belongs to $K$. Choose a convex decomposition
$$
\bar v_{r,t}=\sum_{S\in\mathcal F_\theta}\lambda_S v_S.
$$
Make the choice deterministic by fixing an ordering of subsets and selecting the lexicographically least feasible coefficient vector. This exists because the coefficient set is a nonempty compact polytope.
Within $[r,t]$, select these subsets in that fixed order, allocating duration $(t-r)\lambda_S$ to subset $S$.
Let $y(s)$ be the resulting normalized spending trajectory. It matches the reference at every subdivision endpoint:
$$
y(r)=x(r),\qquad y(t)=x(t).
$$
Although there are infinitely many intervals before any positive shell, this assertion follows by telescoping their increments; the contribution from intervals tending to zero has norm at most $V$ times their total duration and tends to zero.
Both trajectories are coordinatewise nondecreasing. On $[r,t]$, each lies in the coordinate box between $x(r)$ and $x(t)$. Consequently,
$$
\|y(s)-x(s)\|\le V(t-r).
$$
Also, throughout this interval,
$$
0\le y_i(s)\le x_i(t)\le1.
$$
Thus every prefix budget constraint holds, and every selected subset is knapsack feasible.
For $s\in[r,t]\subseteq I_n$,
$$
\begin{aligned}
G(s,y(s))
&\ge G(s,x(s))-QV(t-r)\\
&\ge\frac{\delta_n}{2}>0.
\end{aligned}
$$
Therefore the actual subset-valued schedule satisfies, for every $s\in(0,D]$,
$$
\Phi(y(s))-\Phi(x^0)
\ge s z_\theta(y(s)).
$$
The schedule is measurable: it is constant on a countable collection of subintervals. Its allocation changes are locally finite away from zero, with possible accumulation only at zero.
At time zero, and whenever a new type is observed, let:
Construct the schedule of Section 4 for the hypothetical continuation of this current type over duration $D$. Follow it until the type changes or the horizon ends. At an observed type change, restart from the actual current state.
This is nonanticipative. The hypothetical continuation uses only the current type, budgets, lengths, current spending and known unit horizon. It uses no support information, masses, future types or future boundaries.
Every actual constant-type interval ends at some elapsed time $s\le D$. Section 4 establishes the necessary inequality at every such stopping time. Thus the block condition of Section 2 holds on every maximal constant-type interval.
The allocation is measurable and budget feasible, because there are finitely many observed type intervals and each constituent schedule has those properties. Section 2 now proves
$$
\boxed{
\operatorname{REV}\ge
\left(1-\frac1e\right)\operatorname{OPT}.
}
$$
The construction can require infinitely many allocation changes accumulating at an observed type change. This is allowed by the task’s definition of a measurable allocation; allocation boundaries themselves were not required to be rational or finitely numerous.
The exact construction above is an existence result for the stated policy class. It has a countable event schedule and does not provide a finite total bit-operation running time.
For a finite implementation, the following budget-level policy gives an arbitrarily close guarantee.
Fix an integer $h\ge1$ and rational $\eta\in(0,1)$. Define
$$
c=1+\frac1h,
\qquad
a_j=\frac{c^j-1}{c^h-1}
\quad(0\le j\le h),
\qquad
C_h=\frac{c^h}{c^h-1}.
$$
These prices satisfy
$$
h(a_{j+1}-a_j)+1-a_j=C_h.
$$
Maintain $j_i=\lfloor hX_i\rfloor$, with exhausted advertisers assigned level $h$. At each observed type change or budget-level crossing, choose a feasible subset whose discounted value
$$
W=\sum_{i\in S}b_i(\theta)(1-a_{j_i})
$$
is at least $1-\eta$ times the maximum $z$. Continue until an observed type change, a selected advertiser reaches its next level, or the horizon ends. Remove exhausted advertisers before further positive spending.
There are at most
$$
E=k+mh
$$
constant-subset intervals.
Set $\bar\alpha_i=a_{\lfloor hX_i(1)\rfloor}$. The same monotone-price comparison used in Section 2, now with the instantaneous maximum, proves
$$
\operatorname{OPT}\le
\sum_iB_i\bar\alpha_i+\int_0^1z(u)\,du.
$$
Write
$$
X_i(1)=\frac{J_i}{h}+\rho_i,
\qquad
0\le\rho_i<\frac1h,
$$
with $\rho_i=0$ if $J_i=h$. The completed levels contribute
$$
\frac{B_i}{h}\sum_{j=0}^{J_i-1}(1-a_j)
$$
to integrated selected discounted revenue, and the incomplete level contributes $B_i\rho_i(1-a_{J_i})$. Thus
$$
\begin{aligned}
B_i\bar\alpha_i+\int_0^1
b_i(\theta(u))(1-a_{j_i(u)})\mathbf1[i\in S(u)]\,du
&=
B_i\left(
\frac{C_hJ_i}{h}+\rho_i(1-a_{J_i})
\right)\\
&\le C_hB_iX_i(1).
\end{aligned}
$$
Here the completed-level identity follows from the displayed recurrence, and the residual inequality uses $1-a_{J_i}\le1<C_h$.
Since $(1-\eta)z\le W$, summing gives
$$
(1-\eta)\operatorname{OPT}
\le
\sum_iB_i\bar\alpha_i+\int_0^1W(u)\,du
\le C_h\operatorname{REV}.
$$
Therefore
$$
\operatorname{REV}\ge
(1-\eta)\left(1-(1+1/h)^{-h}\right)\operatorname{OPT}.
$$
The inequalities
$$
1-\frac1{2h}\le h\log(1+1/h)\le1
$$
follow by integrating $1-x\le1/(1+x)\le1$ over $[0,1/h]$. Since $e^{-x}$ is $1$-Lipschitz for $x\ge0$,
$$
1-(1+1/h)^{-h}
\ge1-\frac1e-\frac1{2h}.
$$
For rational $\varepsilon\in(0,1)$, choose
$$
h=\lceil\varepsilon^{-1}\rceil,
\qquad
\eta=\varepsilon/2.
$$
Because the factor $1-(1+1/h)^{-h}$ is at most $1$, the resulting guarantee is at least
$$
1-\frac1e-\frac1{2h}-\eta
\ge1-\frac1e-\varepsilon.
$$
At an event, discard individually infeasible advertisers. Let $p_i$ be the remaining discounted profits and $P=\max_i p_i$.
If $P=0$, select the empty set. Otherwise round profits downward in units of
$$
\frac{\eta P}{m}.
$$
A dynamic program stores the minimum actual rational length for each rounded profit total. Each item has rounded profit at most $m/\eta$, so there are $O(m^2/\eta)$ totals and $O(m^3/\eta)$ transitions.
Rounding loses at most $\eta P$ on any subset. Since the maximum singleton profit $P$ is at most the optimal profit, the returned subset has at least $1-\eta$ times optimal discounted value.
Here is the denominator-growth bound needed for exact rational event updates.
Let $Q_{\mathrm{den}}$ be the product of denominators of all rational numerical instance inputs. Let $Q_{\mathrm{num}}$ be the product of all positive bid numerators, and put
$$
Q=Q_{\mathrm{den}}Q_{\mathrm{num}}.
$$
These products are used only for analysis; the policy need not know future inputs. Their logarithms are $O(L)$.
After $e$ events, a common denominator for current time and all unnormalized spends can be chosen to divide
$$
D_e=hQ_{\mathrm{den}}Q^e.
$$
This follows inductively:
All introduced factors divide $Q$, establishing the induction. Hence
$$
\log D_e=O((e+1)L+\log h).
$$
Spends are bounded by input budgets, so their numerator bit lengths satisfy the same bound with an additional $O(L)$ term.
The prices $a_j$ have bit length $O(h\log(h+1))$. If $\lambda_\eta$ is the binary encoding length of $\eta$, all event arithmetic has bit length bounded by a polynomial in
$$
H=(E+1)L+h\log(h+1)+\lambda_\eta+\log(m+1).
$$
The approximate implementation therefore has bit-operation running time
$$
O\!\left(
E\left(\frac{m^3}{\eta}+m\right)\operatorname{poly}(H)
\right).
$$
With the choices above, this is
$$
\boxed{
\operatorname{poly}
\bigl(m,\tau,L,k,\varepsilon^{-1},\lambda_\varepsilon\bigr),
}
$$
where $\lambda_\varepsilon$ is the binary encoding length of $\varepsilon$. There is no additional dependence on the support size beyond the encoded input; the policy does not receive the support.
Exact subset enumeration instead gives the finite-level policy a running time bounded by
$$
E\,2^m\operatorname{poly}(m,H).
$$
Fix any deterministic nonanticipative policy and an integer $m\ge1$. Give every advertiser length $1$ and budget $1$.
Construct $m$ phases, each lasting $1/m$. Every phase has capacity $1$. If its active advertiser set is $A$, its bids are
$$
b_i=
\begin{cases}
m,&i\in A,\\
0,&i\notin A.
\end{cases}
$$
Initially all advertisers are active. After each phase except the last, remove an active advertiser having minimum cumulative spend.
Because the policy is deterministic and nonanticipative, this recursive construction specifies one fixed stream for that policy. Spending comparisons determine only advertiser labels. All numerical inputs remain rational, and $\tau=k=m$.
In each phase, allocate exclusively to the advertiser removed at its end; in the last phase, allocate to the last remaining advertiser. Each advertiser spends exactly its unit budget during its assigned phase.
Hence
$$
\operatorname{OPT}=m,
$$
since this revenue equals the sum of all budgets.
Let $r_n$ denote online revenue in the phase with $n$ active advertisers. At most one advertiser fits, so
$$
0\le r_n\le1.
$$
Let $a_n$ be the average cumulative spend of active advertisers just before that phase. Their average afterward is $a_n+r_n/n$. Removing a minimum-spend advertiser cannot decrease the average, so
$$
a_{n-1}\ge a_n+\frac{r_n}{n}
\qquad(n\ge2).
$$
Initially $a_m=0$, and the final advertiser’s total spend is at most $1$. Therefore
$$
\sum_{n=1}^m\frac{r_n}{n}\le1.
$$
Write $R=\sum_n r_n$. Subject to $0\le r_n\le1$ and fixed total $R$, the weighted sum is minimized by filling the largest indices first. Indeed, moving positive mass from a smaller index to an unfilled larger index strictly decreases it. Thus
$$
\sum_{n=1}^m\frac{r_n}{n}
\ge
\int_0^R\frac{dx}{m-\lfloor x\rfloor}.
$$
For $0\le x<m$,
$$
\frac1{m-\lfloor x\rfloor}
\ge\frac1{m+1-x}.
$$
Consequently,
$$
1\ge
\log\left(\frac{m+1}{m+1-R}\right),
$$
which implies
$$
R\le(m+1)\left(1-\frac1e\right).
$$
Since $\operatorname{OPT}=m$,
$$
\frac{\operatorname{REV}}{\operatorname{OPT}}
\le
\left(1-\frac1e\right)\left(1+\frac1m\right).
$$
Letting $m$ grow excludes every uniform competitive ratio strictly greater than $1-1/e$.
Together with the exact policy proved above, this establishes
$$
\boxed{
\sup_P\inf_{\mathcal I:\operatorname{OPT}(\mathcal I)>0}
\frac{\operatorname{REV}_P(\mathcal I)}
{\operatorname{OPT}(\mathcal I)}
=
1-\frac1e,
}
$$
and this supremum is attained in the measurable-policy class specified by the question.
⟨structured verdict parsed — rendered above⟩
The argument is sound in substance and resolves the competitive-ratio question. The exact measurable policy attains $1-1/e$, and the adversarial construction excludes every larger uniform ratio. I found no major mathematical issue. Two minor expositional omissions remain.
The identities for $g$ and $C$ are correct, including
$$
g(x)+\int_0^x(1-g(s))\,ds=Cx.
$$
The function $z_\theta$ is nonnegative because the empty set is feasible, and it is coordinatewise nonincreasing because bids are nonnegative.
The offline comparison is valid: final prices dominate prices at each block endpoint, and multiplying offline spending by the nonnegative final prices permits use of the advertiser budgets. This applies to every feasible offline allocation, so taking the supremum is justified without assuming that an offline maximizer exists.
The block inequalities telescope correctly and yield
$$
\operatorname{OPT}\le C\operatorname{REV}.
$$
Deletion closure of the feasible family justifies zeroing any coordinate of a vector in $K$. Consequently, a negative objective coefficient forces the corresponding maximizing velocity coordinate to vanish. The stated Euler overshoot bound is correct, including when a coordinate initially equals $1$.
The Euler trajectories have the uniform boundedness and Lipschitz bounds needed for the asserted compactness. Their derivatives are bounded in $L^2$, and weak convergence identifies the derivative of the uniform limit through integration against interval indicators.
Passing the polytope inequalities and maximizing inequalities to the weak limit is valid. The coefficients in the maximizing inequalities converge uniformly, and there are only finitely many vertex comparisons. The resulting trajectory remains in $[0,1]^m$ and satisfies the differential inclusion almost everywhere.
Minor issue: the precise compactness theorem statements are omitted; see the feedback below.
The maximization inequalities give the claimed sign:
$$
\bigl(\nabla\Psi(x)-\nabla\Psi(y)\bigr)\cdot(x'-y')\le0.
$$
The constants $\lambda$ and $M$ correctly bound the least Hessian eigenvalue and the Hessian Lipschitz constant on $[0,1]^m$.
The differentiation of the Bregman divergence is correct. Its Taylor remainder bound and the velocity bound give the displayed differential inequality. The divergence is absolutely continuous and nonnegative, with initial value zero, so the stated Gronwall application is valid.
Thus uniqueness supplies the determinism required of the reference trajectory.
Minor issue: Gronwall’s inequality is named without stating its precise applicable form.
Each $f_S$ is absolutely continuous, as is their finite maximum. The assertion about derivatives agreeing almost everywhere on equality sets is valid.
At almost every time, a convex decomposition of a maximizing velocity can assign positive weight only to maximizing subsets. The resulting computation correctly establishes
$$
z'(s)=-\sum_i B_i g'(x_i(s))(x_i'(s))^2.
$$
Zero bids cause no division problem in this computation.
Since a positive maximizing value requires a nonzero velocity, the derivative is strictly negative almost everywhere where $z$ is positive. Continuity at the initial time and monotonicity thereafter justify
$$
F(s)>0
$$
for every positive continuation time when $z(0)>0$. This crucial strictness claim is established, rather than assumed.
The stated $Q$ is a valid uniform Lipschitz bound for $G$. Each dyadic shell is compact and lies away from zero, so its minimum slack $\delta_n$ is strictly positive.
The average reference velocity belongs to $K$. The coefficient polytope is nonempty and compact, and lexicographic minimization provides a deterministic coefficient choice.
Endpoint matching across the infinitely many intervals approaching zero is justified by the stated vanishing-duration bound. Within each subdivision interval, both trajectories lie in the same coordinate box. The resulting distance bound and budget bound are correct.
Consequently, the construction preserves the block inequality at every positive stopping time. The schedule has countably many constant pieces and is locally finite away from its initial time.
Minor issue: allocation values at shared endpoints are not explicitly assigned.
The hypothetical continuation uses the current observed type and the remaining unit horizon; it does not require knowledge of the actual continuation duration. The guarantee at every stopping time therefore handles every possible next type change.
Uniqueness of the reference trajectory and deterministic coefficient selection make the construction deterministic. Restarting from actual cumulative spending preserves the budget constraints. Finitely many actual type intervals suffice to preserve measurability of the composite allocation.
Countably many switches accumulating at an interval’s start are permitted by the stated allocation model. A finite implementation is not required for this exact existence claim.
The price recurrence is correct. The completed-level identity and the incomplete-level contribution are also correct, including exhaustion at level $h$.
The monotone-price offline comparison remains valid. The step
$$
(1-\eta)\operatorname{OPT}
\le \sum_i B_i\bar\alpha_i+\int_0^1W(u)\,du
$$
correctly uses both the approximate maximization condition and nonnegativity of the price term.
Removing exhausted advertisers does not reduce the maximum discounted value: their discounted contributions are zero, and deletion preserves feasibility.
The logarithmic bounds, Lipschitz estimate, and choices of $h$ and $\eta$ correctly yield $1-1/e-\varepsilon$. The event bound $E=k+mh$ is valid.
Discarding individually infeasible advertisers is valid because lengths are positive. The rounded-profit dynamic program has the stated number of totals and transitions.
The rounding loss is at most $\eta P$, and $P$ is a feasible singleton profit, so the multiplicative approximation guarantee follows.
The denominator-growth accounting correctly includes both division by a bid and multiplication by current bids. The products used in the analysis need not be known to the policy. Their bit lengths are bounded by the total input length.
The price encoding bound and event-state bounds support the claimed polynomial bit-operation runtime for the approximate implementation. The output appropriately distinguishes this from the exact construction, for which it supplies no finite runtime.
The adaptive construction specifies a fixed valid stream once the deterministic policy is fixed. Only advertiser labels depend on policy behavior; numerical data and phase masses remain rational. The active sets are distinct, giving $\tau=k=m$.
The offline allocation spends each advertiser’s budget in its assigned phase, proving $\operatorname{OPT}=m$.
Removing a minimum-spend active advertiser cannot decrease the remaining average. Together with the final advertiser’s budget, this proves
$$
\sum_{n=1}^m\frac{r_n}{n}\le1.
$$
The weighted-sum minimization, integral comparison, logarithmic calculation, and resulting revenue bound are correct. Taking arbitrarily large finite $m$ excludes every ratio strictly greater than $1-1/e$.
The minimum requested clarification is:
No additional mathematical argument is needed. The established result is a sharp competitive guarantee with a polynomial-time approximate implementation; the exact attaining policy is an existence construction with no finite runtime supplied.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.