Answer: —
Theorem 17 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateNo online algorithms are $o(\tfrac{\log m}{\log\log m} + \log \rho)$-competitive for combinatorial auctions.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(m\) items, value bounds \(v_{\min},v_{\max}\), and at most \(\tau\) complete buyer types, an instance is an ordered online stream of cohorts with rational masses and type valuations \(v_t:2^{[m]}\to\{0\}\cup[v_{\min},v_{\max}]\). Supply is normalized to one unit per item. Each infinitesimal mass unit receives an integral bundle, so the online policy chooses a distribution over bundles for each arriving mass and must keep aggregate use of each item at most one. What is the best competitive ratio \(\alpha^*(m,\rho,\tau)\) achievable by a causal policy against the offline optimum, where \(\rho=v_{\max}/v_{\min}\)?
Fix \(m\geq1\), \(\tau\geq1\), and rational \(0<v_{\min}\leq v_{\max}\); write \(\rho=v_{\max}/v_{\min}\). There are no production costs and each item has supply one.
A society is represented by its support: the list of its types with positive total mass, each mass a positive binary rational. The support size is at most \(\tau\); this counts actual buyer types, not possible valuation functions. Total mass is unrestricted and need not sum to one.
Each type \(t\) has an explicitly tabulated rational valuation \(v_t:2^{[m]}\to\{0\}\cup[v_{\min},v_{\max}]\), with \(v_t(\varnothing)=0\); no monotonicity or other structural assumption is imposed.
The society arrives as a finite ordered stream of \(N\) cohorts \((t_i,q_i)\), with positive rational masses. Initially a policy knows only \(m,\tau,v_{\min},v_{\max}\); each cohort reveals its mass and complete valuation on arrival. Future types, total type masses, and the stopping time are unknown; types may recur.
For cohort \(i\), the policy irrevocably assigns nonnegative masses \(x_{i,S}\) to integral bundles \(S\subseteq[m]\), with \(\sum_S x_{i,S}=q_i\). Every prefix must satisfy \(\sum_i\sum_{S\ni j}x_{i,S}\leq1\) for each item \(j\). Welfare is \(W=\sum_{i,S}v_{t_i}(S)x_{i,S}\); \(\operatorname{OPT}\) maximizes the same welfare with full knowledge of the stream and the same mass allocation constraints.
Allow randomized causal policies against streams fixed independently of their randomness. Define \(\alpha^*(m,\rho,\tau)\) as the infimum of \(\alpha\geq1\) for which a policy guarantees \(\mathbb E[W]\geq\operatorname{OPT}/\alpha\) on every such stream, with no additive loss. There is no computational restriction; state any running times in \(m,\tau,N,L\), where \(L\) is the total binary input length.
What is the optimal worst-case competitive ratio \(\alpha^*(m,\rho,\tau)\) for this continuous online allocation problem?
For discrete buyers with unrestricted type support, even randomized algorithms cannot achieve \(o(\log m/\log\log m+\log\rho)\)-competitiveness. [Huang–Kim](https://arxiv.org/html/1411.4384)
For infinitesimal buyers with strictly convex differentiable production costs, optimal competitive ratios allowing additive loss are characterized; this does not characterize the finite-support, hard-capacity problem above. No exact characterization for that problem was verified. [Huang–Kim](https://arxiv.org/html/1411.4384)
The exact value of $\alpha^*(m,\rho,\tau)$ remains unresolved in this argument. However, the dependence on $m$ and $\rho$ for one recurring type can be determined up to universal constant factors.
Define
$$
R=\min\{m,\rho\},
\qquad
h(R)=1+\frac{\ln R}{\ln(2+\ln R)}.
$$
I prove
$$
\boxed{
\frac{h(R)}{100}
\le
\alpha^*(m,\rho,1)
\le
4h(R).
}
$$
Thus
$$
\boxed{
\alpha^*(m,\rho,1)
=
\Theta\left(
1+\frac{\ln\min\{m,\rho\}}
{\ln(2+\ln\min\{m,\rho\})}
\right).
}
$$
In particular, $\alpha^*(m,\rho,1)=1$ whenever $m=1$ or $\rho=1$.
There is also a new explicit upper bound for arbitrary support size. For integer $\tau\ge1$, define
$$
U_\tau(R)=
\begin{cases}
\tau,&R=1,\\[2mm]
\displaystyle
\min_{k\in\mathbb Z_{\ge1}}
\max\left\{
\tau(k+1),\left\lceil R^{1/k}\right\rceil
\right\},
&R>1.
\end{cases}
$$
Then
$$
\boxed{
\alpha^*(m,\rho,\tau)\le U_\tau(R)\le4\tau h(R).
}
$$
The policies proving these upper bounds are deterministic, causal, and feasible for finite cohorts. Their guarantees have no additive loss.
If $\tau$ is not integral, replace it throughout by $\lfloor\tau\rfloor$.
Divide every valuation by $v_{\min}$. Both online and offline welfare scale by the same positive factor, so competitive ratios are unchanged. Henceforth every positive valuation lies in $[1,\rho]$.
We allocate only positive-valued bundles. Any remaining cohort mass receives the empty bundle. This preserves the required cohort mass equality and consumes no additional capacity.
Fix a type with valuation $v$. If all its valuations are zero, it contributes no welfare and receives only empty bundles. Otherwise, let
$$
\mathcal B=\{S\subseteq[m]:v(S)>0\},
\qquad
p=\max_{S\in\mathcal B}v(S).
$$
Every bundle in $\mathcal B$ is nonempty.
Define its full-capacity packing polytope
$$
\mathcal P=
\left\{
a\in\mathbb R_{\ge0}^{\mathcal B}:
\sum_{S\ni j}a_S\le1
\text{ for every }j\in[m]
\right\}.
$$
For every $a\in\mathcal P$,
$$
\sum_Sa_S
\le
\sum_S|S|a_S
=
\sum_{j=1}^m\sum_{S\ni j}a_S
\le m.
$$
Consequently, $\mathcal P$ is compact.
For cumulative buyer mass $q\ge0$, define
$$
F(q)=
\max\left\{
\sum_Sv(S)a_S:
a\in\mathcal P,\ \sum_Sa_S\le q
\right\}.
$$
The maximum exists because its feasible set is nonempty and compact.
This is exactly the offline optimum for a stream consisting only of this type with total mass $q$. Indeed, any stream allocation aggregates to a feasible vector in this program. Conversely, if the cohort masses are $q_i$ and $\sum_iq_i=q>0$, an aggregate packing $a$ can be assigned by giving cohort $i$ the masses
$$
x_{i,S}=\frac{q_i}{q}a_S
$$
and assigning its remaining mass to the empty bundle. Each prefix uses at most the final packing’s item loads.
The following properties will be used.
Monotonicity and concavity. The function $F$ is nondecreasing. If packings are feasible at masses $q$ and $q'$, their convex combination is feasible at the corresponding convex combination of these masses. Therefore $F$ is concave.
Continuity and decreasing average welfare. We have $F(0)=0$ and $F(q)\le pq$. For $0<a<b$, scaling an optimal packing at $b$ by $a/b$ gives
$$
F(a)\ge\frac abF(b).
$$
Thus $F(q)/q$ is nonincreasing on $(0,\infty)$. Moreover,
$$
0\le F(b)-F(a)
\le
\left(1-\frac ab\right)F(b)
\le p(b-a).
$$
Hence $F$ is continuous, including at zero.
Saturation mass. Let
$$
F_\infty=\max_{a\in\mathcal P}\sum_Sv(S)a_S
$$
and let $q_*$ be the minimum total mass among packings attaining $F_\infty$. Both optimizations attain their optima. We have
$$
F(q_*)=F_\infty,\qquad q_*\le m,
$$
and $F(q)<F_\infty$ whenever $q<q_*$.
For every $q\in(0,q_*)$, an optimal packing defining $F(q)$ has total mass exactly $q$. To prove this, suppose an optimum had mass $b<q$. Mix it with a welfare-maximizing packing of mass $q_*$. A sufficiently small positive mixture still has mass at most $q$, but has strictly larger welfare because $F(q)<F_\infty$. This is a contradiction. At $q_*$, the defining minimum-mass optimum also has mass exactly $q_*$.
Initial linear region. Let $q_0$ be the maximum mass packable using only bundles of value $p$. Then
$$
F(q)=pq\qquad(0\le q\le q_0).
$$
The upper bound is $F(q)\le pq$; attainability follows by scaling a maximum-mass packing of value-$p$ bundles.
Also,
$$
F_\infty\ge pq_0,
\qquad
F_\infty\le pq_*,
$$
so $q_0\le q_*$.
Define the terminal average welfare
$$
a_*=\frac{F_\infty}{q_*}
$$
and the average-welfare range
$$
D=\frac p{a_*}.
$$
Since positive valuations are at least one, $a_*\ge1$. A unit mass of a value-$p$ bundle is feasible, so $F_\infty\ge p$. Consequently,
$$
1\le D
\le\rho,
\qquad
D=\frac{pq_*}{F_\infty}\le q_*\le m.
$$
Therefore
$$
\boxed{D\le R=\min\{m,\rho\}.}
$$
If $D=1$, then $a_*=p$, and the inequalities above imply $q_*=q_0$.
The central idea is to plan allocations for several possible cumulative masses using the revealed valuation table.
Lemma. Suppose
$$
q_0<q_1<\cdots<q_\ell=q_*
$$
are masses with optimal packing profiles $a^{(i)}$ of total mass exactly $q_i$. Write
$$
b_i=\frac{F(q_i)}{q_i}.
$$
Suppose a real number $c\ge1$ satisfies
$$
c\ge\ell+1,
\qquad
b_0=p,
\qquad
b_i\ge\frac{b_{i-1}}c
\quad(1\le i\le\ell).
$$
Then there is a causal policy for this type whose welfare at every cumulative mass $q$ is at least $F(q)/c$.
Each item’s total consumption by this policy is at most $(\ell+1)/c$.
Proof. Serve the scaled profiles
$$
\frac1c a^{(0)},\frac1c a^{(1)},\ldots,\frac1c a^{(\ell)}
$$
consecutively as buyer mass arrives.
Batch $i$ has mass $q_i/c$. During that batch, distribute arriving mass proportionally to $a^{(i)}$. Thus the welfare rate per unit buyer mass is $b_i$. Once all batches are complete, give subsequent mass the empty bundle.
A finite cohort can cross several batch boundaries: assign its respective portions according to those batches and give any remainder the empty bundle. This directly defines a permissible allocation to the finite cohort.
Let
$$
T_i=\frac1c\sum_{h=0}^iq_h,
\qquad T_{-1}=0.
$$
Because the masses increase and $c\ge\ell+1$,
$$
T_i\le\frac{i+1}{c}q_i\le q_i.
$$
During batch zero, the policy’s welfare is $pq$, which is at least $F(q)/c$.
Now consider batch $i\ge1$, at cumulative mass
$$
T_{i-1}\le q\le T_i.
$$
Put $b=q_{i-1}$. At the batch’s start, the accumulated welfare is at least $F(b)/c$, and $T_{i-1}\le b$.
If $q\le b$, monotonicity gives
$$
W(q)\ge\frac{F(b)}c\ge\frac{F(q)}c.
$$
If $q>b$, the constant welfare rate in this batch gives
$$
W(q)\ge\frac{F(b)}c+b_i(q-b).
$$
Since $F(q)/q$ is nonincreasing,
$$
F(q)\le\frac{F(b)}bq
=
F(b)+b_{i-1}(q-b).
$$
Using $b_i\ge b_{i-1}/c$ proves $W(q)\ge F(q)/c$.
After the last batch, accumulated welfare is at least
$$
\frac{F(q_\ell)}c=\frac{F_\infty}c,
$$
which also suffices for every later mass.
Finally, each complete scaled profile consumes at most $1/c$ of every item. Every partial profile consumes no more than its complete profile. Thus every prefix uses at most $(\ell+1)/c$ of each item. $\square$
Fix an integer $c\ge2$.
If $D=1$, use just the profile at $q_*=q_0$.
If $D>1$, set
$$
\ell=\left\lceil\log_cD\right\rceil.
$$
For each $1\le i<\ell$, choose $q_i$ satisfying
$$
\frac{F(q_i)}{q_i}=\frac p{c^i},
$$
and put $q_\ell=q_*$.
These intermediate masses exist: the continuous, nonincreasing function $F(q)/q$ takes the value $p$ at $q_0$ and the value $a_*$ at $q_*$. The intermediate target values lie strictly between them. Their strict decrease also ensures
$$
q_0<q_1<\cdots<q_\ell.
$$
The corresponding averages satisfy
$$
b_i=\frac{b_{i-1}}c\quad(1\le i<\ell)
$$
and, because $D\le c^\ell$,
$$
b_\ell=a_*
\ge\frac p{c^\ell}
=\frac{b_{\ell-1}}c.
$$
Therefore the concatenation lemma applies whenever $c\ge\ell+1$.
Define
$$
c(R)=
\begin{cases}
1,&R=1,\\
\min\{c\in\mathbb Z_{\ge2}:R\le c^{c-1}\},&R>1.
\end{cases}
$$
For $R>1$, take $c=c(R)$. Since $D\le R$,
$$
\ell=\left\lceil\log_cD\right\rceil\le c-1.
$$
Thus the lemma supplies a feasible $c(R)$-competitive policy:
$$
\boxed{\alpha^*(m,\rho,1)\le c(R).}
$$
If $R=1$, then $D=1$. The single unscaled profile at $q_*=q_0$ obtains $F(q)$ at every cumulative mass $q$. Hence
$$
\boxed{\alpha^*(m,\rho,1)=1\quad\text{when }R=1.}
$$
Suppose $R>1$. Choose integers $k\ge1$ and $c$ satisfying
$$
c\ge\tau(k+1),
\qquad
R\le c^k.
$$
When a type first appears, construct its profiles as above and serve its subsequent cohorts using its own concatenation schedule scaled by $1/c$. Its number of profiles is at most
$$
1+\left\lceil\log_cD\right\rceil\le k+1.
$$
Therefore it consumes at most $(k+1)/c$ of every item. Since at most $\tau$ actual types appear, total consumption at every prefix is at most
$$
\frac{\tau(k+1)}c\le1.
$$
Let $Q_t$ be the final mass of type $t$, and let $F_t$ be its single-type offline curve. The lemma gives
$$
W_t\ge\frac{F_t(Q_t)}c.
$$
The joint offline allocation restricted to type $t$ is feasible for the single-type problem with full capacities. Consequently,
$$
\operatorname{OPT}\le\sum_tF_t(Q_t).
$$
Summing the policy’s welfare yields
$$
W\ge\frac1c\sum_tF_t(Q_t)
\ge\frac{\operatorname{OPT}}c.
$$
Minimizing over $k$ gives
$$
\boxed{\alpha^*(m,\rho,\tau)\le U_\tau(R).}
$$
For $R=1$, every nonzero type has $D=1$. Give each type its single profile scaled by $1/\tau$. The same argument gives competitive ratio $\tau$.
Finally, for $R>1$, the choice
$$
k=c(R)-1,\qquad c=\tau c(R)
$$
satisfies the required inequalities. Thus, including the case $R=1$,
$$
\boxed{U_\tau(R)\le\tau c(R).}
$$
All these policies know only the prescribed parameters before the stream begins. They compute a type’s profiles when that type first appears and never use its future mass or the stopping time.
The upper-bound construction can use rational profiles and allocations throughout.
First compute $F_\infty$ by a linear program over $\mathcal P$. Then compute $q_*$ by minimizing total mass subject to attaining welfare $F_\infty$. Compute $q_0$ by maximizing mass using only value-$p$ bundles.
For an intermediate target average $a$ satisfying
$$
a_*<a<p,
$$
solve
$$
\max\left\{
\sum_Sx_S:
x\in\mathcal P,\
\sum_Sv(S)x_S\ge a\sum_Sx_S
\right\}.
$$
Let its optimum mass be $q$.
No feasible packing in this program can have mass at least $q_*$: such a packing would have average welfare at most $F_\infty/q_*=a_*<a$. Hence $q<q_*$.
An optimal packing for $F(q)$ has mass exactly $q$. If $F(q)>aq$, mixing that packing with the saturation packing by a sufficiently small positive amount would increase its mass while retaining average welfare at least $a$. This contradicts maximality of $q$. Therefore
$$
F(q)=aq,
$$
and the program supplies the required optimal profile.
Here every target average is $p/c^i$, a rational number.
An elementary finite implementation is available by enumerating vertices. Each relevant polytope has nonnegativity constraints, $m$ item constraints, and at most one additional welfare constraint or equality. Every vertex has at most $m+1$ positive coordinates: otherwise those coordinates admit a nonzero perturbation preserving all active additional constraints, contradicting extremality.
Enumerate supports of size at most $m+1$ and full-rank selections of active constraints. Solve the resulting linear systems, discard infeasible candidates, and select the first optimal candidate in a fixed enumeration. Singular systems are discarded; every vertex has a representation using a full-rank selection.
There are at most
$$
2^{O(m^2)}
$$
candidate systems per program. For a rational system of dimension $s\le m+1$ with coefficient bit lengths at most $B$, clearing all denominators and applying Cramer’s rule bounds solution-coordinate bit lengths by
$$
O(s^3B+s\log s).
$$
The program for $q_*$ uses the already computed $F_\infty$; all subsequent level programs use the original valuations and $p/c^i$. Thus these finitely many preprocessing steps produce profiles of polynomial bit length.
For $R>1$, put
$$
k_0=\left\lceil\log_2R\right\rceil.
$$
Taking $k=k_0$ and $c=\tau(k_0+1)$ is feasible. Hence the minimization defining $U_\tau(R)$ need only consider $1\le k\le k_0$, and each type needs at most $k_0+1$ profiles.
During the stream, maintain each type’s cumulative input mass and its position in the precomputed schedule. A sum of input rationals has a common denominator whose bit length is at most the sum of their denominator bit lengths. Likewise, the finitely many precomputed batch endpoints have polynomial bit length. All allocation computations therefore retain polynomial bit length over the finite stream.
This gives an exact rational implementation with total running time bounded by
$$
\boxed{
2^{O(m^2)}\operatorname{poly}(m,\tau,N,L).
}
$$
No optimization program uses loads produced by a preceding optimization program.
The following construction improves the dependence obtained from the square-root valuation family.
Proposition. For every integer $k\ge2$, if
$$
m\ge(2k)^k,
\qquad
\rho\ge k^k,
$$
then, for every $\tau\ge1$,
$$
\boxed{\alpha^*(m,\rho,\tau)\ge k/4.}
$$
The proof applies to randomized causal policies against fixed streams.
Set
$$
B=2k,\qquad A=k,\qquad M=B^k,
\qquad
a=\frac{\ln A}{\ln B}\in(0,1).
$$
Use $M$ items and a single type with valuation
$$
v(S)=
\begin{cases}
A^\ell,&|S|=B^\ell
\text{ for some }\ell\in\{0,\ldots,k\},\\
0,&\text{otherwise}.
\end{cases}
$$
On every positive-valued bundle,
$$
v(S)=|S|^a.
$$
All tabulated values are integers in $[1,A^k]$.
Give this type cohorts of masses
$$
q_0=1,\qquad
q_i=B^i-B^{i-1}\quad(1\le i\le k).
$$
The cumulative mass through cohort $i$ is
$$
Q_i=B^i.
$$
For any positive-valued allocation, let $P$ be its allocated mass and $R'$ its total item usage. Concavity of $s^a$, applied with weights proportional to the allocated masses, gives
$$
W=\sum_S|S|^ax_S
\le P^{1-a}(R')^a.
$$
At cumulative available mass $Q$, we have $P\le Q$ and $R'\le M$. Hence
$$
W\le Q^{1-a}M^a.
$$
At prefix $i$, allocate mass $Q_i$ uniformly over bundles of size $B^{k-i}$. Every item’s load is
$$
\frac{Q_iB^{k-i}}M=1.
$$
The welfare is
$$
V_i=Q_iA^{k-i}
=A^k(B/A)^i
=A^k2^i
=M^aQ_i^{1-a}.
$$
This aggregate allocation can be split proportionally among the available cohorts. Therefore
$$
\boxed{\operatorname{OPT}_i=V_i.}
$$
Let $W_i$ be the policy’s random welfare in cohort $i$, and let $R_i$ count item usage only in its positive-valued allocations. The preceding concavity inequality within that cohort gives
$$
W_i\le q_i^{1-a}R_i^a.
$$
Let
$$
Z_i=\mathbb E[W_i],
\qquad
p'=\frac1a>1.
$$
Since $r^a$ is concave and $0\le R_i\le M$, Jensen’s inequality gives
$$
Z_i
\le q_i^{1-a}\bigl(\mathbb E[R_i]\bigr)^a.
$$
Consequently,
$$
\frac{Z_i^{p'}}{q_i^{p'-1}}\le\mathbb E[R_i].
$$
Summing and using the hard capacities,
$$
\boxed{
\sum_{i=0}^k\frac{Z_i^{p'}}{q_i^{p'-1}}\le M.
}
$$
Suppose the policy is $\alpha$-competitive. Causality implies that its allocations on a prefix have the same distribution whether or not later cohorts appear. Applying competitiveness to every stopped prefix gives
$$
\sum_{h=0}^iZ_h\ge\frac{V_i}{\alpha}.
$$
Define
$$
d_0=\frac{V_0}{\alpha},
\qquad
d_i=\frac{V_i-V_{i-1}}{\alpha}
=\frac{V_i}{2\alpha}\quad(i\ge1).
$$
Then
$$
H_i=\sum_{h=0}^i(Z_h-d_h)\ge0.
$$
We claim
$$
\sum_i\frac{Z_i^{p'}}{q_i^{p'-1}}
\ge
\sum_i\frac{d_i^{p'}}{q_i^{p'-1}}.
$$
To prove this, put
$$
\lambda_i=\left(\frac{d_i}{q_i}\right)^{p'-1}.
$$
The ratios are
$$
\frac{d_0}{q_0}=\frac{A^k}{\alpha},
\qquad
\frac{d_i}{q_i}
=
\frac{A^{k-i}}{2\alpha(1-1/B)}
\quad(i\ge1).
$$
They decrease: the first ratio drops by a factor $B-1$, and subsequent ratios drop by a factor $A$. Thus $\lambda_i$ is nonnegative and nonincreasing.
Summation by parts gives
$$
\sum_{i=0}^k\lambda_i(Z_i-d_i)
=
\lambda_kH_k+
\sum_{i=0}^{k-1}(\lambda_i-\lambda_{i+1})H_i
\ge0.
$$
Convexity of $z^{p'}/q_i^{p'-1}$ gives the tangent inequality
$$
\frac{Z_i^{p'}}{q_i^{p'-1}}
\ge
\frac{d_i^{p'}}{q_i^{p'-1}}
+
p'\lambda_i(Z_i-d_i).
$$
Summing proves the claim.
Since
$$
V_i=M^aQ_i^{1-a},
$$
we have
$$
\frac{V_i^{p'}}{Q_i^{p'-1}}=M.
$$
Therefore
$$
\frac{d_0^{p'}}{q_0^{p'-1}}=\frac M{\alpha^{p'}}
$$
and, for every $i\ge1$,
$$
\frac{d_i^{p'}}{q_i^{p'-1}}
=
\frac M{\alpha^{p'}}
\frac{2^{-p'}}{(1-1/B)^{p'-1}}.
$$
Combining the resource inequality and the preceding minimization yields
$$
\alpha
\ge
\left(
1+
k\frac{2^{-p'}}{(1-1/B)^{p'-1}}
\right)^a
\ge
\frac{k^a}{2}.
$$
Finally,
$$
k^{1-a}
=
\exp\left(
\frac{\ln2\,\ln k}{\ln(2k)}
\right)
\le2.
$$
Hence $k^a\ge k/2$, giving
$$
\boxed{\alpha\ge k/4.}
$$
For larger $m$, give value zero to every bundle involving an unused item. For the original valuation scale, multiply the table by $v_{\min}$. The assumptions $m\ge B^k$ and $\rho\ge A^k$ make the resulting instance admissible. It uses exactly one actual type. $\square$
Here are explicit comparisons establishing the announced constants.
Write $T=\ln R$. For $T\ge1$, set
$$
d=\left\lceil\frac{4T}{\ln(T+2)}\right\rceil.
$$
For $u\ge1$, the inequality $\ln u\le\sqrt u$ follows by minimizing $\sqrt u-\ln u$, whose minimum occurs at $u=4$ and is positive.
Consequently,
$$
d\ge\frac{4T}{\sqrt{T+2}}\ge\sqrt{T+2},
$$
where the last inequality uses $T\ge1$. Thus
$$
\ln d\ge\frac12\ln(T+2).
$$
Also $d\ge2$, so
$$
(d-1)\ln d
\ge
\frac d4\ln(T+2)
\ge T.
$$
Therefore $R\le d^{d-1}$ and
$$
c(R)\le d
\le1+\frac{4T}{\ln(T+2)}
\le4h(R).
$$
For $0<T<1$, $R<e<9=3^2$, so $c(R)\le3\le4h(R)$. At $T=0$, $c(R)=1$. Hence
$$
\boxed{c(R)\le4h(R).}
$$
Suppose $T\ge64$ and choose
$$
k=\left\lfloor\frac{T}{2\ln(T+2)}\right\rfloor.
$$
The inequality
$$
\ln(T+2)\le\sqrt{T+2}\le T/4
$$
ensures that the expression inside the floor is at least two. Thus
$$
k\ge\frac{T}{4\ln(T+2)}.
$$
Also $2k\le T$, so
$$
k\ln(2k)
\le
\frac{T}{2\ln(T+2)}\ln(T+2)
=\frac T2.
$$
It follows that
$$
(2k)^k\le e^{T/2}\le R.
$$
Since $m\ge R$ and $\rho\ge R$, the lower-bound proposition applies:
$$
\alpha^*(m,\rho,1)
\ge\frac k4
\ge\frac{T}{16\ln(T+2)}.
$$
The same inequalities imply $T/\ln(T+2)\ge4$, so
$$
h(R)\le\frac{2T}{\ln(T+2)}.
$$
Therefore the lower bound is at least $h(R)/32$.
For $0\le T<64$, use $\alpha^*\ge1$. The elementary bound $\ln2\ge2/3$, obtained by integrating the tangent lower bound for the convex function $1/x$ on $[1,2]$, gives
$$
h(R)\le1+\frac{64}{\ln2}\le97.
$$
Thus $\alpha^*\ge h(R)/100$ in this range as well.
Together with the upper comparison,
$$
\boxed{
\frac{h(R)}{100}
\le
\alpha^*(m,\rho,1)
\le
4h(R).
}
$$
The single-type dependence on $m$ and $\rho$ is now established up to universal constant factors. Its exact value is not determined, except when $R=1$.
For larger support, the explicit bound $U_\tau(R)$ is proved, but no matching lower bound is established here. The one-type construction supplies the lower bound $h(R)/100$ for every $\tau$, because those instances are still admissible. It does not determine the additional effect of multiple actual types.
Accordingly, these results substantially advance the task but do not give the exact general function $\alpha^*(m,\rho,\tau)$.
⟨structured verdict parsed — rendered above⟩
The output establishes valid upper and lower bounds, including matching asymptotic bounds for one recurring type. It does not determine the optimal competitive ratio for general support size, and it explicitly acknowledges this limitation. The appropriate overall status is partial.
I found no false central step. There is one minor omission in the justification of the special case $D=1$. The main unresolved issue is the requested characterization of $\alpha^*(m,\rho,\tau)$.
The normalization by $v_{\min}>0$ preserves competitive ratios and makes every positive valuation belong to $[1,\rho]$.
Assigning unused mass to the empty bundle is permissible: it restores the required cohort mass equality without welfare or capacity effects.
The packing polytope $\mathcal P$ is closed and bounded. The displayed bound
$$
\sum_S a_S\le m
$$
uses the fact that every positive-valued bundle is nonempty. Thus compactness and attainment of the optimization problems are justified.
The identification of $F(q)$ with the single-type offline optimum is correct. In the reverse direction, proportional distribution among cohorts preserves their mass constraints, and every prefix uses at most the aggregate packing’s final item loads.
The stated properties of $F$ are valid:
The initial linear region and the bounds
$$
1\le D\le\min\{m,\rho\}
$$
are also correct. In particular, $a_*\ge1$ uses the positive-valuation restriction, while $F_\infty\ge p$ follows from the feasibility of allocating unit mass to a maximum-valued bundle.
Minor issue. The sentence asserting that the preceding inequalities imply $q_*=q_0$ when $D=1$ is too compressed. Those displayed scalar inequalities establish $q_0\le q_*$; the reverse inequality requires an equality-condition justification.
Minimum clarification: Explicitly justify $q_*\le q_0$ when $F_\infty=pq_*$. This is a routine clarification and does not undermine the special-case conclusion.
The lemma is correct under its stated hypotheses.
Serving each scaled profile proportionally gives the stated batch mass and welfare rate. A finite cohort can be partitioned at batch boundaries, so the construction is valid for finite cohorts rather than requiring infinitesimal arrivals.
The endpoint estimate
$$
T_i\le\frac{i+1}{c}q_i\le q_i
$$
correctly uses increasing profile masses and $c\ge\ell+1$.
At the start of batch $i$, the already completed profile $i-1$ alone contributes $F(q_{i-1})/c$. Thus the asserted accumulated-welfare lower bound is justified.
Both cases in the welfare comparison are valid:
After the final batch, its contribution alone guarantees $F_\infty/c$. The capacity bound follows by summing complete scaled-profile loads; partial profiles cannot increase that bound.
No unjustified induction or future-information assumption occurs here.
For $D>1$, every intermediate target average lies strictly between $p$ and $a_*$. Continuity supplies the required masses, and the strictly decreasing target values force their increasing order.
The last adjacent-rate inequality follows correctly from $D\le c^\ell$. When $\ell=1$, it uses $b_0=p$, so that boundary case is covered.
The definition of $c(R)$ ensures
$$
\left\lceil\log_c D\right\rceil\le c-1,
$$
which satisfies the concatenation lemma’s profile-count condition.
For multiple types, each type uses at most $(k+1)/c$ of each item. Summing over at most $\tau$ actual types therefore establishes prefix feasibility. Restricting a joint offline allocation to one type gives a feasible allocation for that type’s full-capacity benchmark, so
$$
\operatorname{OPT}\le\sum_t F_t(Q_t)
$$
is valid. Summing the single-type guarantees proves the stated upper bound $U_\tau(R)$.
The construction is causal: a type’s valuation is available when its schedule is computed, and the schedule does not depend on future mass or stopping time. All-zero types can receive empty bundles throughout.
The treatment of nonintegral $\tau$ is appropriate because support size is integral.
Subject to the minor clarification above, the exact single-type conclusion for $R=1$ and the arbitrary-support upper bound for $R=1$ are valid.
The implementation argument is sound.
For an intermediate target average, the auxiliary program has positive feasible mass and an attained maximum. Its average constraint excludes masses at least $q_*$. The strict-average mixing argument then correctly establishes
$$
F(q)=aq.
$$
Consequently, an optimizer of that program supplies an optimal profile for the selected mass.
The vertex-support bound is valid: there are at most $m+1$ constraints other than nonnegativity, so a vertex cannot have more than $m+1$ positive coordinates. Enumerating supports and full-rank active-constraint selections therefore includes every required vertex.
With at most $2^m$ bundle variables, the stated enumeration bound $2^{O(m^2)}$ is sufficient. The rational-coordinate bit-length bound is conservative but valid. Using the previously computed scalar $F_\infty$ in the saturation-mass program causes only polynomial bit-length growth.
The cutoff
$$
k_0=\left\lceil\log_2R\right\rceil
$$
is justified: the displayed choice at $k_0$ is feasible, while every larger $k$ has a larger compulsory term $\tau(k+1)$ than that candidate’s value.
The finite-stream arithmetic argument also supports polynomial bit lengths for cohort allocations. Thus the claimed running-time bound
$$
2^{O(m^2)}\operatorname{poly}(m,\tau,N,L)
$$
is supported.
This is an implementation result for the proposed policies; it does not establish efficient computation of the exact optimal competitive ratio.
The construction is admissible:
The concavity inequality
$$
W\le P^{1-a}(R')^a
$$
is valid for positive allocated mass. With no positive-valued allocation, the resulting welfare bound holds trivially.
The uniform allocation over bundles of size $B^{k-i}$ has total mass $Q_i$ and item load exactly one. Its welfare matches the concavity upper bound. Therefore the claimed prefix optima $\operatorname{OPT}_i=V_i$ are exact.
The expected resource inequality is correct. Jensen’s inequality applies because $0<a<1$ and $R_i$ is bounded. Raising the resulting nonnegative inequality to $p'=1/a$ gives the stated resource requirement. Hard capacities imply that the summed expected positive-allocation item usage is at most $M$.
Applying competitiveness to every stopped prefix is legitimate: those streams are fixed independently of the policy’s randomness, and causality makes their prefix allocation distributions agree.
The minimum-resource argument is also valid. The first ratio $d_i/q_i$ decreases by the stated factor $B-1$, and later ratios decrease by $A$. Hence the tangent coefficients $\lambda_i$ are nonnegative and nonincreasing. The summation-by-parts identity has the correct boundary term and signs, and the convex tangent inequalities yield the claimed comparison.
The resource evaluation and constants check correctly:
$$
\alpha\ge
\left(
1+k\frac{2^{-p'}}{(1-1/B)^{p'-1}}
\right)^a
\ge\frac{k^a}{2},
$$
and $k^{1-a}\le2$ implies $\alpha\ge k/4$.
Thus the lower bound applies to randomized causal policies as claimed.
The upper comparison correctly establishes $c(R)\le4h(R)$, including the small-$T$ and $T=0$ cases.
For $T\ge64$, the selected integer $k$ satisfies the proposition’s hypotheses. The floor estimate, the bound on $(2k)^k$, and the comparison with $h(R)$ all have the stated directions.
For $0\le T<64$, the estimate $h(R)\le97$ makes the trivial bound $\alpha^*\ge1$ sufficient for the announced constant $100$.
Therefore the matching single-type order
$$
\alpha^*(m,\rho,1)=\Theta(h(R))
$$
is supported. The same lower bound remains valid for every larger support allowance because one-type streams remain admissible.
Major issue: the requested general optimum is not determined.
For multiple types, the output supplies an upper bound and a lower bound inherited from one-type instances. It does not establish matching dependence on $\tau$. Even for one type, it establishes constant-factor asymptotics rather than the exact ratio outside $R=1$.
These limitations are accurately acknowledged by the prover. They make this genuine partial progress, not a refuted proof.
Minimum additional work needed: Establish the missing optimality characterization for general $\tau$, and determine the exact single-type ratio if an exact general function is claimed. Expositional clarification alone cannot close these gaps.
⟨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.