Answer: —
Theorem 2 — class: algorithmic
Given finite assignment and resource sets, rational rewards and resource uses, per-capita budgets, a finite horizon \(T\), and an explicit finite rational distribution for each stage’s arrival-mass vector \(\Xi_t\), choose offline assignment masses \(x_e\) before arrivals and online assignment masses \(z_{e,t}\) after observing the current arrivals and past history. Each person receives an integral assignment, while aggregate masses may be fractional; all assignments must obey shared resource budgets at every stage. What is the best competitive ratio achievable in polynomial time against a clairvoyant fluid allocator that sees the full arrival path?
Let \(E^1\) be repeatable offline assignments and \(E^2=\bigsqcup_{j\in J}E^2_j\) online assignments available to type \(j\); put \(m=|E^1|+|E^2|\). Rewards \(w_e>0\), resource uses \(a_{e,k}\in[0,1]\), and per-capita budgets \(b_k>0\) are binary rationals. Every offline assignment consumes some resource; there are no offline supply constraints beyond budgets.
Partition the \(K\) resources into nonempty sets \(\mathcal K_1,\mathcal K_2\), with \(a_{e,k}\in\{0,1\}\) on \(\mathcal K_1\). Each assignment uses at most \(\ell_i\) resources in \(\mathcal K_i\); assume \(\ell=\ell_1+\ell_2\ge1\) and \(B=\min_{k\in\mathcal K_2}b_k>2\). Budgets and aggregate allocations may be fractional for either resource class.
A society is given by its support: the list of the \(\tau\) types with positive mass, each with its mass as a binary rational; \(\tau\) is the support size, not the number of possible types. Use one mass unit as the population reference for all budgets and allocations.
For each \(t\in\{1,\ldots,T\}\), an explicit finite distribution with positive rational probabilities specifies \(\Xi_t\in\mathbb Q_{\ge0}^{J}\), with \(\sum_j\Xi_{j,t}=1\). These vectors are sampled independently across stages; \(\tau\) counts types having positive mass in some listed outcome. Let \(S\) be the total number of listed outcomes and \(L\) the total input bit length.
Before any arrivals, choose \(x_e\ge0\) for \(e\in E^1\). After observing \(\Xi_t\) and the past, irrevocably choose \(z_{e,t}\ge0\), satisfying \(\sum_{e\in E^2_j}z_{e,t}\le\Xi_{j,t}\). Unassigned mass is rejected immediately. These masses partition atomless populations into people receiving one whole assignment or rejection.
For every realized history and every \(t\), require \(\sum_{e\in E^1}a_{e,k}x_e+\sum_{s=1}^{t}\sum_{e\in E^2}a_{e,k}z_{e,s}\le b_k\) for every resource \(k\). Reward is \(\sum_{e\in E^1}w_ex_e+\sum_{t=1}^{T}\sum_{e\in E^2}w_ez_{e,t}\).
Let \(\mathrm{OPT}(\Xi_1,\ldots,\Xi_T)\) maximize this reward under the same constraints, allowing even \(x\) to depend on the entire arrival path. A policy's competitive ratio is \(\inf_{\mathcal I}\mathbb E[\mathrm{ALG}(\mathcal I)]/\mathbb E[\mathrm{OPT}(\mathcal I)]\), over instances with positive denominator and the specified parameter values; expectation includes policy randomness. Polynomial time means total running time polynomial in \(m,\tau,K,T,S,L\).
What is the best worst-case competitive ratio achievable by polynomial-time policies for this fluid allocation problem, as a function of \(\ell_1,\ell_2,B,T\)?
For discrete assignments and independent single-person arrivals, a polynomial-time policy guarantees \((1-\varepsilon)/(4\ell)\), where \(\varepsilon=2\max\{1/(B-2),\ell_2\exp(-B/12+1/6)\}\), against an LP upper bound on expected clairvoyant reward. [Xu et al.](https://www.ijcai.org/proceedings/2020/0581.pdf)
For fractional vertex-weighted stochastic matching with independent, nonidentically distributed arrivals, a \(0.718\) guarantee and a \(0.75\) upper bound are known; this is a restricted allocation model. [Tang et al.](https://arxiv.org/abs/2204.06851)
No result settling the full fluid model above was identified in the search.
The best competitive ratio for the full model remains unresolved. I prove an improved lower bound, two stronger upper-bound constructions, and the exact special cases stated below.
Let
$$
R_{\mathrm{poly}}(\ell_1,\ell_2,B,T)
$$
denote the supremum of competitive ratios of policies whose total running time is polynomial in the parameters specified in the question. The sparsity parameters are interpreted as nonnegative integers, and $T$ is a positive integer.
Define
$$
Q_B(\beta)
=
\exp\left(
-\frac{B}{\beta}
\bigl(\log(1/\beta)-1+\beta\bigr)
\right),
\qquad 0<\beta<1,
$$
and
$$
\Psi(\ell_1,\ell_2,B)
=
\sup_{0<\beta<1}
\left[
\frac{\beta-\ell_2Q_B(\beta)}
{1+\ell_1\beta}
\right]_+.
$$
Here $[u]_+=\max\{u,0\}$.
The general lower bound proved here is
$$
R_{\mathrm{poly}}(\ell_1,\ell_2,B,T)
\ge
\max\left\{
\frac1{\ell_1+\ell_2+1},
H(\ell_1,B,T),
\Psi(\ell_1,\ell_2,B)
\right\},
$$
where
$$
H(\ell_1,B,T)
=
\begin{cases}
1/(T+1),&\ell_1\ge1,\\
B/(B+T),&\ell_1=0.
\end{cases}
$$
The new lower bound $\Psi$ yields, for every fixed $\ell_2$,
$$
\lim_{B\to\infty}
R_{\mathrm{poly}}(1,\ell_2,B,T)=\frac12
$$
uniformly over positive integer horizons $T$.
The upper-bound constructions establish two additional facts:
$$
R_{\mathrm{poly}}(0,1,B,T)
\le
1-\frac1{8\sqrt B}.
$$
Thus a guarantee with loss of order $1/B$, uniformly over $T$, is impossible in this restricted case.
All upper bounds hold without computational restrictions.
Merge identical listed outcomes within each stage. Let $O_t$ be the resulting outcome set, with probabilities $p_{t,o}$ and arrival vectors $\xi^{t,o}$. An observed vector then identifies its outcome.
For an allocation vector $v$, write
$$
A_k(v)=\sum_e a_{e,k}v_e.
$$
Consider the LP
$$
\max\quad
\sum_{e\in E^1}w_ex_e
+
\sum_{t,o}p_{t,o}
\sum_{e\in E^2}w_ey_e^{t,o},
$$
subject to nonnegativity and
$$
\sum_{e\in E_j^2}y_e^{t,o}\le\xi_j^{t,o}
\qquad\text{for every }j,t,o,
$$
$$
A_k(y^{t,o})\le b_k
\qquad\text{for every }k,t,o,
$$
$$
A_k(x)+
\sum_{t,o}p_{t,o}A_k(y^{t,o})
\le b_k
\qquad\text{for every }k.
$$
Let its optimum be $V$, and fix an optimal solution $(x^*,y^*)$.
Claim.
$$
V\ge\mathbb E[\mathrm{OPT}].
$$
Proof. The arrival-path space is finite. On every path choose a clairvoyant optimum. Set $x$ equal to its expected offline allocation and set
$$
y_e^{t,o}
=
\mathbb E[z_{e,t}^{\mathrm{OPT}}\mid O_t=o].
$$
Conditional expectation preserves type-supply constraints. Every individual stage consumes at most $b_k$ on every path, because consumption is nonnegative and total consumption is feasible. This establishes the outcome-specific resource constraints. Taking expectations of final consumption establishes the aggregate constraints.
The objective of this projected solution is exactly $\mathbb E[\mathrm{OPT}]$. Consequently, $V$ is an upper bound. $\square$
The LP has at most $|E^1|+S|E^2|$ variables and polynomially many constraints. Every offline variable is bounded because its assignment has a positive resource coefficient: if $a_{e,k}>0$, then $x_e\le b_k/a_{e,k}$. Every online variable is at most one. All coefficients have polynomial encoding length. Thus the standard polynomial-time theorem for rational linear programming applies.
Fix rational constants $0<c\le\beta<1$. Choose the offline allocation $cx^*$.
Before stage $t$, let $r_{k,t}$ be the remaining budget, and put
$$
F_{e,t}
=
\min\left\{
1,\
\min_{\substack{k\in\mathcal K_1\\a_{e,k}>0}}
\frac{r_{k,t}}{\beta b_k}
\right\}.
$$
An empty inner minimum imposes no restriction.
Let $G_{e,t}$ equal one when
$$
r_{k,t}\ge\beta
$$
for every second-class resource used by $e$, and zero otherwise. Define
$$
H_{e,t}=F_{e,t}G_{e,t},
\qquad
q_{e,t}=\mathbb E[H_{e,t}].
$$
The expectation is over past arrivals under the policy already specified at earlier stages.
Suppose constants $d_{e,t}\ge c/\beta$ have been fixed. On observing outcome $o$, allocate
$$
z_{e,t}
=
\frac{c}{d_{e,t}}\,y_e^{t,o,*}H_{e,t}.
$$
This policy is feasible on every history, irrespective of the accuracy of the constants $d_{e,t}$.
Indeed, $c/d_{e,t}\le\beta$, so type supply is respected. For a first-class resource $k$, every assignment using it satisfies
$$
z_{e,t}\le
\frac{r_{k,t}}{b_k}y_e^{t,o,*}.
$$
Therefore
$$
\sum_e a_{e,k}z_{e,t}
\le
\frac{r_{k,t}}{b_k}A_k(y^{t,o,*})
\le r_{k,t}.
$$
For a second-class resource $k$, if $r_{k,t}<\beta$, all allocations using it are zero. Otherwise the entire stage consumes at most $\beta$, since
$$
\sum_e y_e^{t,o,*}\le1,
\qquad
a_{e,k}\le1,
\qquad
z_{e,t}\le\beta y_e^{t,o,*}.
$$
Thus its consumption is also at most $r_{k,t}$.
We next lower-bound $q_{e,t}$. Assume inductively that preceding stages satisfy
$$
\mathbb E[z_{e,s}\mid O_s=o]\le c\,y_e^{s,o,*}.
$$
Write $U_{k,t}=b_k-r_{k,t}$. The LP gives
$$
\mathbb E[U_{k,t}]
\le
c\left(
A_k(x^*)+
\sum_{s<t,o}p_{s,o}A_k(y^{s,o,*})
\right)
\le cb_k.
$$
For $u\in[0,1]$ and $\beta\le1$,
$$
1-\min\{1,(1-u)/\beta\}\le u.
$$
When $u\le1-\beta$, the left side is zero. Otherwise the desired inequality is equivalent to
$$
u-(1-\beta)\le\beta u,
$$
which follows from $u\le1$.
Applying this inequality to each first-class resource used by $e$ yields
$$
\mathbb E[1-F_{e,t}]\le\ell_1c.
$$
For a second-class resource $k$, put
$$
D=A_k(x^*),
\qquad
V_s=A_k(y^{s,O_s,*}).
$$
The variables $V_s$ are independent, lie in $[0,1]$, and satisfy
$$
\sum_{s<t}\mathbb E[V_s]\le b_k-D.
$$
The interval bound follows from total arriving mass one and coefficients at most one.
Because $c\le\beta$ and all online allocations are pointwise at most $\beta y^*$,
$$
U_{k,t}\le
\beta\left(D+\sum_{s<t}V_s\right).
$$
Consequently,
$$
r_{k,t}<\beta
\quad\Longrightarrow\quad
D+\sum_{s<t}V_s>b_k/\beta-1.
$$
For $\theta>0$, convexity gives
$$
e^{\theta v}\le1+v(e^\theta-1)
\qquad(0\le v\le1).
$$
Independence and exponential Markov inequality imply
$$
\begin{aligned}
\Pr(r_{k,t}<\beta)
&\le
\exp\left(
\theta+\theta D-\theta b_k/\beta
+(e^\theta-1)(b_k-D)
\right)\\
&\le
\exp\left(
\theta+b_k(e^\theta-1-\theta/\beta)
\right).
\end{aligned}
$$
The last step uses $\theta-(e^\theta-1)\le0$ and $D\ge0$.
Taking $\theta=\log(1/\beta)$ gives
$$
\Pr(r_{k,t}<\beta)
\le
\frac1\beta
\exp\left(
-\frac{b_k}{\beta}
\bigl(\log(1/\beta)-1+\beta\bigr)
\right)
\le
\frac{Q_B(\beta)}{\beta}.
$$
The final inequality uses $b_k\ge B$ and
$$
\log(1/\beta)-1+\beta>0.
$$
Using
$$
FG\ge1-(1-F)-(1-G)
$$
and a union bound over the second-class resources used by $e$, we conclude
$$
q_{e,t}
\ge
1-\ell_1c-\frac{\ell_2Q_B(\beta)}{\beta}.
$$
In particular, if
$$
0<c\le
\frac{\beta-\ell_2Q_B(\beta)}
{1+\ell_1\beta},
$$
then
$$
q_{e,t}\ge c/\beta.
$$
Since $H_{e,t}$ depends only on the past, stage independence gives
$$
\mathbb E[z_{e,t}\mid O_t=o]
=
c\,y_e^{t,o,*}\frac{q_{e,t}}{d_{e,t}}.
$$
Thus the ideal choice $d_{e,t}=q_{e,t}$ would give expected allocation exactly $cy_e^{t,o,*}$, closing the induction.
Exact computation of $q_{e,t}$ by enumerating histories is unnecessary.
Fix rational $\delta\in(0,1)$ and let
$$
\eta=\delta c/6.
$$
Construct the constants before actual arrivals, proceeding through stages in order. Once the earlier constants have been fixed, simulate independent arrival prefixes under that policy and estimate every $q_{e,t}$ by a sample mean $\widehat q_{e,t}$.
Round upward on a dyadic mesh of size at most $\eta$ and set
$$
d_{e,t}
=
\max\left\{
c/\beta,\
\text{upward rounding of }\widehat q_{e,t}+\eta
\right\}.
$$
If preceding estimates were accurate and
$$
|\widehat q_{e,t}-q_{e,t}|\le\eta,
$$
then the availability argument gives
$$
q_{e,t}\le d_{e,t}\le q_{e,t}+3\eta.
$$
Since $q_{e,t}\ge c/\beta\ge c$,
$$
1-\delta/2
\le
\frac{q_{e,t}}{d_{e,t}}
\le1.
$$
Therefore
$$
c(1-\delta/2)y_e^{t,o,*}
\le
\mathbb E[z_{e,t}\mid O_t=o]
\le
cy_e^{t,o,*}.
$$
Here are the computational details.
A simulated prefix can be sampled with a fixed number of random bits. Inverse-CDF sampling on a sufficiently fine dyadic grid gives total variation error at most $\eta/2$ for the prefix distribution. Since $H_{e,t}\in[0,1]$, this changes its expectation by at most $\eta/2$. Polynomially many bits suffice: a grid with stagewise errors summing to at most $\eta/2$ can be chosen using $S$ and $\eta$.
For $N_{\mathrm{sim}}$ independent simulated prefixes, Hoeffding’s inequality gives
$$
\Pr\left(
|\widehat q_{e,t}-\mathbb E[\widehat q_{e,t}]|>\eta/2
\right)
\le
2e^{-N_{\mathrm{sim}}\eta^2/2}.
$$
Taking
$$
N_{\mathrm{sim}}
=
O\left(
\eta^{-2}\log\frac{mT+1}{\delta}
\right)
$$
makes the probability of any inaccurate estimate at any stage at most $\delta/2$. Fresh samples justify this bound conditional on previously fixed preprocessing constants.
All stored constants have polynomial encoding length because of dyadic rounding. With those constants fixed, each resource update is piecewise affine with rational coefficients: a clipping minimum selects either a constant or one normalized remaining budget, and a blocking indicator selects zero or one. There are polynomially many possible coefficients, indexed by stages, listed outcomes, assignments, and resources. A common denominator for these coefficients has polynomial bit length; after at most $T$ updates, denominators divide its $T$th power times the initial denominator. Thus simulations and actual allocations use polynomial-bit rational arithmetic.
Conditional on any accurate preprocessing result, expected reward is at least
$$
c(1-\delta/2)V.
$$
Actual arrivals are independent of preprocessing randomness. On inaccurate preprocessing results the policy remains feasible and has nonnegative reward. Hence
$$
\mathbb E[\mathrm{ALG}]
\ge
(1-\delta/2)^2cV
\ge
(1-\delta)c\,\mathbb E[\mathrm{OPT}].
$$
The running time is polynomial in the input parameters, $1/\delta$, and $1/c$. The reciprocal dependence on $c$ is handled by the sparsity guarantee proved next: candidate guarantees below $1/(K+1)$ can be discarded, while every retained candidate has $1/c\le K+1$.
For completeness, the same simulation argument proves the baseline guarantee.
Put
$$
h=\min\{\ell_1+\ell_2,K\},
\qquad
c_0=\frac1{h+1}.
$$
Choose offline allocation $c_0x^*$ and use
$$
g_{e,t}
=
\min_{k:a_{e,k}>0}\frac{r_{k,t}}{b_k},
$$
with $g_{e,t}=1$ for resource-free assignments. Allocate
$$
z_{e,t}
=
\frac{c_0}{d_{e,t}}y_e^{t,o,*}g_{e,t},
\qquad d_{e,t}\ge c_0.
$$
The outcome-specific resource constraints imply feasibility.
Under the inductive expected-allocation upper bound,
$$
\begin{aligned}
\mathbb E[g_{e,t}]
&\ge
1-\sum_{k:a_{e,k}>0}
\frac{\mathbb E[U_{k,t}]}{b_k}\\
&\ge1-hc_0=c_0.
\end{aligned}
$$
The simulation construction above, now with minimum constant $c_0$, gives competitive ratio $(1-\delta)c_0$ in polynomial time. In particular,
$$
R_{\mathrm{poly}}\ge
\frac1{\ell_1+\ell_2+1}.
$$
For the mixed-resource bound, rational $\beta$ and rational $c$ strictly below the positive expression in Section 3.1 suffice. Their attainable ratios approach $\Psi$.
This can also be implemented uniformly. For any fixed rational $\beta$, compute a downward rational approximation to the expression with error at most a prescribed constant times $c_0$. The required precision is polynomial in the input length and $\log(1/\delta)$; standard polynomial-time approximation of $\log$ and $\exp$ supplies it, with sufficiently small exponential terms replaced by certified upper bounds. If the candidate is below $c_0$, use the baseline policy. Otherwise $1/c\le K+1$, so the simulation bound is polynomial in the specified input parameters. Continuity in $\beta$ and density of rational choices then establish the stated supremal bound $\Psi$.
Fix $\ell_1,\ell_2$ and $\beta<1$. Because
$$
\log(1/\beta)-1+\beta>0,
$$
we have $Q_B(\beta)\to0$ as $B\to\infty$. Consequently,
$$
\liminf_{B\to\infty}
R_{\mathrm{poly}}(\ell_1,\ell_2,B,T)
\ge
\frac{\beta}{1+\ell_1\beta}.
$$
The bound is independent of $T$. Letting $\beta$ increase to one gives the uniform lower bound
$$
\liminf_{B\to\infty}
R_{\mathrm{poly}}(\ell_1,\ell_2,B,T)
\ge
\frac1{\ell_1+1}.
$$
Section 5 proves $R_{\mathrm{poly}}\le1/2$ whenever $\ell_1\ge1$. Thus, for $\ell_1=1$ and fixed $\ell_2$,
$$
R_{\mathrm{poly}}(1,\ell_2,B,T)\longrightarrow\frac12
$$
uniformly over $T$.
For $\ell_1=0$ and fixed $\ell_2$, the same argument gives convergence to one, also uniformly over $T$, since no policy can outperform the clairvoyant optimum on a realized path.
Let $D$ be the optimal reward using offline assignments alone. For each stage and outcome, let $H_t(o)$ be the optimal reward using that stage alone with the full budgets.
Every clairvoyant solution satisfies
$$
\mathrm{OPT}\le D+\sum_tH_t(O_t),
$$
because each component is separately feasible with the full budgets.
Choose $1/(T+1)$ times an optimal offline allocation. At each stage choose $1/(T+1)$ times an optimal standalone allocation for its observed outcome. Each of these $T+1$ components consumes at most $b_k/(T+1)$, so the policy is feasible and guarantees $1/(T+1)$. All standalone problems are polynomial-size rational LPs.
If $\ell_1=0$, define $U_t(o)$ by assigning each arriving type to its highest-reward available assignment while ignoring budgets. Types with no available assignment are rejected and contribute zero. Such a stage allocation consumes at most one unit of every resource.
Use the scaling factor
$$
c_B=\frac{B}{B+T}.
$$
Choose $c_B$ times an optimal offline allocation and, at each stage, $c_B$ times the allocation defining $U_t(o)$. Each second-class resource has total consumption at most
$$
c_Bb_k+c_BT
\le
c_Bb_k(1+T/B)=b_k.
$$
First-class consumption is zero. Since
$$
\mathrm{OPT}\le D+\sum_tU_t(O_t),
$$
this policy guarantees $B/(B+T)$.
Use one active resource with capacity $C\ge1$. There is one offline assignment with unit cost and unit reward.
At one online stage, with probability $p$, a unit mass arrives with a unit-cost assignment of reward $1/p$. Otherwise only an unassignable type arrives. Other stages contain only the unassignable type.
For every offline choice $x\in[0,C]$, expected policy reward is at most
$$
x+\min\{1,C-x\}\le C.
$$
Conditioning on $x$ proves the same upper bound for randomized policies.
Clairvoyance earns $C$ in the low outcome and $C-1+1/p$ in the high outcome. Therefore
$$
\mathbb E[\mathrm{OPT}]=C+1-p.
$$
Taking dyadic rational probabilities $p\to0$ gives the upper bound $C/(C+1)$.
If $\ell_1\ge1$, put the active resource in $\mathcal K_1$ with $C=1$ and add an unused second-class resource of budget $B$. If $\ell_1=0$, put it in $\mathcal K_2$ with $C=B$ and add an unused first-class resource. Hence
$$
R_{\mathrm{poly}}(\ell_1,\ell_2,B,T)
\le
\begin{cases}
1/2,&\ell_1\ge1,\\
B/(B+1),&\ell_1=0.
\end{cases}
$$
For $T=1$, the lower and upper bounds coincide:
$$
R_{\mathrm{poly}}(\ell_1,\ell_2,B,1)
=
\begin{cases}
1/2,&\ell_1\ge1,\\
B/(B+1),&\ell_1=0.
\end{cases}
$$
The explicit scaling policies attain these ratios.
For $(\ell_1,\ell_2)=(1,0)$, the sparsity attenuation policy can be implemented exactly. Take $c=1/2$. An assignment using resource $k$ has
$$
g_{e,t}=r_{k,t}/b_k.
$$
Inductively, its exact expectation is
$$
q_{e,t}
=
1-\frac{c}{b_k}
\left(
A_k(x^*)+
\sum_{s<t,o}p_{s,o}A_k(y^{s,o,*})
\right).
$$
The LP implies $q_{e,t}\ge1-c=c$. Setting $d_{e,t}=q_{e,t}$ gives
$$
\mathbb E[z_{e,t}\mid O_t=o]=cy_e^{t,o,*},
$$
which closes the induction. Resource-free assignments use $q_{e,t}=1$. These constants and updates have polynomial rational encoding length.
Thus a deterministic polynomial-time policy attains $1/2$, and
$$
R_{\mathrm{poly}}(1,0,B,T)=\frac12
$$
for every positive integer $T$.
The following construction uses a row-selection idea familiar from prophet-inequality lower bounds. The packing representation and the analysis of fractional allocations are proved here; an integral row-selection argument alone would not suffice. [Kleinberg and Weinberg, Section 5](https://arxiv.org/html/1201.4764#S5)
Fix integers $d\ge2$, $N\ge1$, and a rational probability $p\in(0,1)$. Let the active resource capacity be $C\ge1$.
There are $N$ rows, each containing $d$ assignments. Assignment $(r,c)$ has reward one and its own online type. There are no offline assignments.
For every tuple
$$
u=(u_1,\ldots,u_N)\in\{1,\ldots,d\}^N,
$$
create a resource of budget $C$. Assignment $(r,c)$ uses this resource with coefficient one exactly when $u_r=c$.
Thus each assignment uses precisely
$$
d^{N-1}
$$
resources.
Process the $Nd$ assignments in row order. At the stage for $(r,c)$, its type arrives with unit mass with probability $p$; otherwise an unassignable type arrives. All stages are independent. Let $H_{r,c}$ be the corresponding Bernoulli indicator and $Z_{r,c}$ the allocated mass. Then
$$
0\le Z_{r,c}\le H_{r,c}.
$$
Define
$$
M_r=\max_{1\le c\le d}Z_{r,c}.
$$
The resource constraints are equivalent to
$$
\sum_{r=1}^N M_r\le C.
$$
Indeed, every resource constraint has the form
$$
\sum_r Z_{r,u_r}\le C.
$$
If $\sum_rM_r\le C$, all these constraints hold. Conversely, choose $u_r$ attaining the maximum in each row. The corresponding resource constraint gives $\sum_rM_r\le C$.
This equivalence holds for arbitrary fractional allocations.
Let
$$
M_{r,c}=\max_{1\le i\le c}Z_{r,i},
\qquad
M_{r,0}=0,
$$
and
$$
\Delta_{r,c}=M_{r,c}-M_{r,c-1}\ge0.
$$
Pointwise,
$$
Z_{r,c}\le H_{r,c}M_{r,c-1}+\Delta_{r,c}.
$$
When $H_{r,c}=0$, both $Z_{r,c}$ and $\Delta_{r,c}$ are zero. When $H_{r,c}=1$, the right side equals $M_{r,c}$.
The variable $M_{r,c-1}$ depends only on the past and policy randomness, so it is independent of $H_{r,c}$. Hence
$$
\mathbb E[Z_{r,c}]
\le
p\,\mathbb E[M_{r,c-1}]
+
\mathbb E[\Delta_{r,c}].
$$
Summing within a row, using $M_{r,c-1}\le M_r$ and $M_{r,0}=0$, gives
$$
\sum_{c=1}^d\mathbb E[Z_{r,c}]
\le
\bigl(1+(d-1)p\bigr)\mathbb E[M_r].
$$
Finally, fractional feasibility implies
$$
\mathbb E[\mathrm{ALG}]
\le
C\bigl(1+(d-1)p\bigr).
$$
Choose integers $q\ge2$, $r\ge1$, and put
$$
p=1/q,
\qquad
h=\lceil C\rceil,
\qquad
N=hrq^d.
$$
Assume $h2^{-r}<1$.
Partition the rows into $h$ groups of $rq^d$ rows. A row has all $d$ assignments available with probability $q^{-d}$. The probability that one group contains no such row is
$$
(1-q^{-d})^{rq^d}<2^{-r}.
$$
To justify the inequality, for an integer $a\ge2$,
$$
(1-1/a)^{-a}
=
(1+1/(a-1))^a
>
1+\frac{a}{a-1}>2.
$$
Take $a=q^d$ and raise the resulting bound to the $r$th power.
A union bound shows that, with probability at least $1-h2^{-r}$, there are at least $h$ completely available rows. On this event clairvoyance assigns unit mass in $\lfloor C\rfloor$ such rows and mass $C-\lfloor C\rfloor$ in one additional row if needed. This is feasible and earns $Cd$.
Therefore
$$
\mathbb E[\mathrm{OPT}]
\ge
Cd(1-h2^{-r}),
$$
and every policy has ratio at most
$$
\boxed{
\frac{1+(d-1)/q}
{d(1-h2^{-r})}.
}
$$
There are two valid embeddings into the task’s model:
$$
\ell_1\ge d^{rq^d-1},
\qquad
T\ge drq^d.
$$
Add an unused second-class resource of budget $B$.
$$
\ell_2\ge d^{\lceil B\rceil rq^d-1},
\qquad
T\ge d\lceil B\rceil rq^d.
$$
Add an unused first-class resource.
Extra stages contain only unassignable mass. The resource list is explicit, although extremely large. Thus this is a valid family of finite inputs, rather than a succinctly represented resource system.
For example, take $C=1$, $d=3$, $q=8$, and $r=4$. Then
$$
N=2048,
\qquad
Nd=6144,
$$
and the upper bound is
$$
\frac{1+2/8}{3(1-1/16)}=\frac49.
$$
Consequently,
$$
R_{\mathrm{poly}}(\ell_1,\ell_2,B,T)\le\frac49
$$
whenever $\ell_1\ge3^{2047}$ and $T\ge6144$.
More generally, for fixed $C,d$, letting $q,r$ grow makes the displayed upper bound approach $1/d$. Taking $d$ arbitrarily large proves that no positive absolute competitive ratio is valid independently of sparsity and horizon. The construction does not give sharp dependence on sparsity: its required sparsity is very large.
Now suppose $\ell_1=0$, $\ell_2\ge1$, and $B=n$ is an integer at least three. Assume $T\ge2n$.
Use one active second-class resource of budget $n$, and an unused first-class resource. There is one offline assignment with unit cost and unit reward.
At each of the first $2n$ stages, independently, a unit mass of an online type arrives with probability $1/2$. Its only assignment has unit cost and reward two. Otherwise an unassignable type arrives. Remaining stages are unassignable.
Let
$$
N\sim\operatorname{Bin}(2n,1/2)
$$
be the number of assignable stages.
For an offline choice $x\in[0,n]$, set $s=n-x$. The online reward is at most $2\min\{N,s\}$. Thus expected total reward is at most
$$
f(s)=n-s+2\mathbb E[\min\{N,s\}],
\qquad 0\le s\le n.
$$
For $s\in(j-1,j)$, where $1\le j\le n$,
$$
f'(s)=-1+2\Pr(N\ge j).
$$
Symmetry of the binomial distribution gives
$$
\Pr(N\ge j)\ge\Pr(N\ge n)\ge\frac12.
$$
Therefore $f$ is nondecreasing on $[0,n]$ and is maximized at $s=n$. This bounds randomized offline choices as well. Hence
$$
\mathbb E[\mathrm{ALG}]
\le
2\mathbb E[\min\{N,n\}].
$$
The bound is attained by choosing no offline allocation and accepting online mass until capacity is exhausted.
Clairvoyance accepts $\min\{N,n\}$ online units and fills the remaining capacity offline. Its reward is
$$
n+\min\{N,n\}.
$$
Put
$$
a_n=\frac{\binom{2n}{n}}{4^n}.
$$
I claim
$$
\mathbb E[|N-n|]=na_n.
$$
By symmetry,
$$
\mathbb E[|N-n|]
=
\frac2{4^n}
\sum_{j=0}^{n-1}(n-j)\binom{2n}{j}.
$$
Using the convention $\binom{2n-1}{-1}=0$, the identity
$$
(n-j)\binom{2n}{j}
=
n\left(
\binom{2n-1}{j}
-
\binom{2n-1}{j-1}
\right)
$$
makes the sum telescope. Since
$$
\binom{2n-1}{n-1}
=
\frac12\binom{2n}{n},
$$
the claim follows.
Again by symmetry,
$$
\mathbb E[\min\{N,n\}]
=
n-\frac12na_n.
$$
Thus every policy’s ratio on this instance is at most
$$
\boxed{
\frac{4-2a_n}{4-a_n}
=
1-\frac{a_n}{4-a_n}.
}
$$
Finally,
$$
a_n\ge\frac1{2\sqrt n}.
$$
For $n=1$ equality holds. The recurrence
$$
\frac{a_{n+1}}{a_n}
=
\frac{2n+1}{2n+2}
\ge
\sqrt{\frac n{n+1}}
$$
follows by squaring, because $(2n+1)^2\ge4n(n+1)$. Induction proves the bound.
Consequently,
$$
\frac{a_n}{4-a_n}\ge\frac{a_n}{4}
\ge\frac1{8\sqrt n},
$$
and
$$
\boxed{
R_{\mathrm{poly}}(0,\ell_2,n,T)
\le
1-\frac1{8\sqrt n}
\qquad
(\ell_2\ge1,\ T\ge2n).
}
$$
For $n\ge64$, this is strictly stronger than $n/(n+1)$, because $n+1>8\sqrt n$. This obstruction uses only one active resource and two supported online types.
The proofs establish improved general lower bounds, stronger upper bounds in several parameter regimes, and exact finite-parameter answers for $T=1$ and $(\ell_1,\ell_2)=(1,0)$.
They do not determine the optimal general function. In particular, the multi-resource upper construction does not match the sparsity dependence of the lower bounds, and the one-resource budget construction leaves the optimal finite-$B$, horizon-dependent ratio undetermined.
⟨structured verdict parsed — rendered above⟩
The output establishes substantial, sound partial results. I found no false central step or substantive gap in the proofs of its stated bounds and exact cases. It does not determine the best competitive ratio for the full parameter range requested in USER_TASK, and it explicitly acknowledges this limitation.
Interpreting $\ell_1,\ell_2$ as nonnegative integers and $T$ as a positive integer is consistent with the intended task. In particular, $\ell_1=0$ implies $\ell_2\ge1$, so the constructions using a second-class resource are available whenever invoked.
The definition of $R_{\mathrm{poly}}$ uses a supremum over polynomial-time policies. This distinction matters: the simulation arguments establish arbitrarily close attainable guarantees, hence bounds on that supremum. They do not establish exact attainment of $\Psi$ or the general sparsity bound. The write-up respects this distinction; its exact-attainment claims concern separately specified policies.
Major scope limitation: the general optimal function remains undetermined. This is an acknowledged incompleteness relative to USER_TASK, rather than a flaw in the partial results.
The projection of a clairvoyant solution into the LP is valid.
Thus
$$
V\ge\mathbb E[\mathrm{OPT}]
$$
is justified, including when the clairvoyant offline allocation depends on the entire path.
The polynomial-time LP claim also checks out. Offline variables are bounded because every offline assignment has a positive resource coefficient; online variables are bounded by their type supply, hence by one. The LP is feasible, has polynomial size, and has rational coefficients of polynomial encoding length. These are the relevant hypotheses for polynomial-time rational linear programming.
Feasibility holds independently of estimation accuracy.
From $d_{e,t}\ge c/\beta$,
$$
\frac{c}{d_{e,t}}\le\beta<1.
$$
Since $H_{e,t}\in[0,1]$, scaling the LP allocation respects every type-supply constraint.
For a first-class resource, the definition of $F_{e,t}$ gives the stated assignmentwise bound. Summing it and applying the outcome-specific LP constraint bounds stage consumption by the remaining budget.
For a second-class resource, allocations using it vanish when its remaining budget is below $\beta$. Otherwise total stage consumption is at most $\beta$, because the LP allocation contains at most one unit of total mass and all resource coefficients are at most one.
Resource-free online assignments are covered by the empty-minimum conventions. Offline feasibility follows from scaling a feasible LP offline allocation by $c\le1$.
The inductive expected-allocation upper bound implies
$$
\mathbb E[U_{k,t}]\le cb_k.
$$
This correctly includes deterministic offline consumption and the expected consumption of preceding stages.
The scalar clipping inequality is correct on its stated domain. Applying it to the normalized consumed budget of each relevant first-class resource, followed by the bound on the number of such resources, justifies
$$
\mathbb E[1-F_{e,t}]\le\ell_1c.
$$
For second-class resources, the variables $V_s$ are independent because each is a fixed function of the independently sampled stage outcome. Their range is $[0,1]$, and the LP supplies the required bound on their summed expectations.
The pointwise domination of consumed budget, the exponential Markov bound, and the elimination of the term involving $D$ are all valid. Substituting $\theta=\log(1/\beta)$ gives the stated factor $Q_B(\beta)/\beta$. The replacement of $b_k$ by $B$ has the correct direction because
$$
\log(1/\beta)-1+\beta>0.
$$
The union bound and the inequality involving $F_{e,t}G_{e,t}$ therefore establish
$$
q_{e,t}\ge
1-\ell_1c-\frac{\ell_2Q_B(\beta)}{\beta}.
$$
Rearranging the stated condition on $c$ indeed makes this lower bound at least $c/\beta$.
Finally, $H_{e,t}$ depends only on the past once preprocessing constants are fixed. Stage independence therefore justifies the conditional expected-allocation formula and the proposed induction.
The estimation argument is sound.
On an accurate estimate, upward rounding gives
$$
q_{e,t}\le d_{e,t}\le q_{e,t}+3\eta.
$$
The maximum with $c/\beta$ does not invalidate the upper bound, because the availability induction already gives $q_{e,t}\ge c/\beta$.
With $\eta=\delta c/6$, the claimed multiplicative bounds on $q_{e,t}/d_{e,t}$ follow. The upper bound closes the availability induction; the lower bound supplies the reward guarantee.
Approximate prefix sampling introduces at most the stated expectation error because $H_{e,t}$ is bounded in $[0,1]$. Hoeffding’s inequality is applied to independent bounded samples, with the stated exponent. Fresh samples at successive preprocessing stages permit conditional failure bounds, and the union bound covers all estimates.
The conditioning in the final reward argument is legitimate: actual arrivals are independent of preprocessing randomness. For every fixed accurate preprocessing result, the induction holds under the actual arrival law. Inaccurate preprocessing results still produce feasible, nonnegative-reward policies. Consequently,
$$
\mathbb E[\mathrm{ALG}]
\ge(1-\delta/2)^2cV
\ge(1-\delta)c\,\mathbb E[\mathrm{OPT}]
$$
is justified.
The rational-arithmetic argument addresses a genuine implementation concern. With preprocessing constants fixed, updates are piecewise affine with rational coefficients drawn from a polynomial-size collection. The common-denominator argument bounds encoding growth through the horizon. Discontinuous blocking decisions do not undermine this argument: their comparisons involve exactly represented rationals.
The simulation count is polynomial once $1/c$ is polynomially bounded. The baseline uses
$$
c_0=\frac1{\min\{\ell_1+\ell_2,K\}+1},
$$
whose reciprocal is at most $K+1$. Retaining mixed-resource candidates only when they are at least this baseline similarly controls their reciprocal.
The baseline feasibility argument and its expected-availability bound are valid, including for resource-free assignments. Taking arbitrarily small fixed losses establishes the stated supremal sparsity guarantee.
The numerical approximation discussion is sufficient for the claimed supremal bound: it specifies downward approximation, controlled precision, and certified treatment of sufficiently small exponential terms. Continuity and rational density support approaching $\Psi$ with rational choices. This does not claim that one policy exactly attains the supremum.
For fixed $\beta<1$, the exponent defining $Q_B(\beta)$ is strictly negative and grows in magnitude with $B$. The asserted decay and resulting lower limits follow.
Uniformity over $T$ is justified because the lower bound has no horizon dependence and the applicable upper bounds also hold for every positive horizon.
Combining the lower limit with the upper bound from Section 5 correctly yields convergence to $1/2$ when $\ell_1=1$ and $\ell_2$ is fixed. When $\ell_1=0$, the lower limit is one, and pathwise clairvoyant optimality supplies the upper bound of one.
Every component of a feasible clairvoyant allocation is separately feasible under the full budgets. Therefore the decomposition into standalone offline and stage rewards is a valid upper bound.
Scaling the $T+1$ standalone solutions by $1/(T+1)$ ensures feasibility and gives the claimed guarantee.
When $\ell_1=0$, the budget-free stage allocation consumes at most one unit of each resource. The calculation using $b_k\ge B$ correctly establishes feasibility of the scaling factor $B/(B+T)$. The corresponding objective comparison is also valid.
The one-resource construction is valid for every stated embedding. For any offline choice, the expected online contribution is bounded by the remaining capacity capped at one. Hence the expected policy reward is at most $C$, including for randomized offline choices.
The clairvoyant rewards in the two outcomes are correctly computed, giving expected reward $C+1-p$. Taking positive rational probabilities tending to zero establishes the stated supremal upper bounds.
For $T=1$, the explicit lower-bound policies match these upper bounds and attain the claimed ratios.
For $(\ell_1,\ell_2)=(1,0)$, an assignment either uses one first-class resource or is resource-free. Thus its availability expectation is determined by expected consumption of that single resource. The displayed formula for $q_{e,t}$ follows from the allocation induction, and the LP implies $q_{e,t}\ge1/2$. Exact rational attenuation therefore closes the induction and provides the claimed deterministic polynomial-time policy.
The feasibility characterization is correct for fractional allocations. Maximizing separately within each row corresponds to one of the explicitly listed tuple resources, so the resource system is equivalent to
$$
\sum_rM_r\le C.
$$
Because allocations are nonnegative, final feasibility also controls every prefix.
The pointwise inequality involving $Z_{r,c}$, $M_{r,c-1}$, and $\Delta_{r,c}$ is valid in both Bernoulli outcomes. The preceding maximum is independent of the current arrival indicator. Summing the inequalities correctly yields the policy-reward bound.
The probability of a completely available row, the group failure bound, and the union bound all check out. The assumption $h2^{-r}<1$ ensures that the resulting denominator is positive. The clairvoyant allocation described on the success event is feasible for both integer and noninteger $C$.
The sparsity count, horizon requirements, and embeddings satisfy the task’s restrictions. The extremely large resource list is explicit; no unsupported succinct-representation assumption is used.
The numerical example gives $N=2048$, horizon $6144$, and ratio $4/9$ as stated. The limiting conclusion excluding a positive absolute guarantee independent of sparsity and horizon is justified.
The cited [Kleinberg–Weinberg section](https://arxiv.org/html/1201.4764#S5) provides context for the row-selection idea. The prover supplies its own fractional feasibility and policy analysis, so no integral lower-bound theorem is improperly transferred to the fluid model.
The expected-reward upper bound for a fixed offline allocation is valid. The derivative on each open unit interval is correctly computed, and binomial symmetry gives the required monotonicity. Conditioning on a randomized offline choice preserves this upper bound.
The clairvoyant reward is correctly characterized. The binomial identity used in the telescoping sum is correct, including its boundary convention, and yields the stated absolute-deviation expectation.
The resulting ratio
$$
\frac{4-2a_n}{4-a_n}
$$
is correct. The recurrence and induction proving $a_n\ge1/(2\sqrt n)$ also check out, as does the consequent loss bound. For $n\ge64$, the comparison with $n/(n+1)$ has the correct strict direction.
The construction uses admissible rational data, independent stages, one active second-class resource, and two supported online types.
The minimum additional work needed to settle USER_TASK is a matching characterization of the optimal ratio outside the proved exact cases. No clarification of the existing partial proofs alone resolves that outstanding question. Another round is promising because the verified lower bounds and obstructions provide substantive progress.
⟨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.