Answer: —
Theorem 3.3 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateIn OM-RR-PA with non-identical resources, OAA- NID(𝜙) achieves a competitive ratio of 1 2 −𝜖 for any 𝜖> 0.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite horizon \(H\), resource classes \(R\) with per-capita supplies \(\rho_r\), agent types \(A\) with utilities \(w_{ar}\), bounded patience and occupation-time laws, and a known finite-support rational law over arriving cohort-mass vectors \(\xi_t\), does there exist a causal policy, computable in time polynomial in the encoded instance size, such that for every \(\varepsilon>0\), \(\mathbb{E}[\mathrm{ALG}] \geq (1/2-\varepsilon)\mathbb{E}[\mathrm{OPT}]\)? The policy allocates waiting type mass to resource classes over time; \(\mathrm{OPT}\) is the feasible fluid allocation that knows the cohort trajectory in advance.
Time consists of \(H\geq1\) rounds. There are \(m\geq1\) resource classes, initially entirely free, with positive binary-rational capacities \(\rho_r\), and an explicitly specified eligibility relation \(E\subseteq A\times R\); eligible matches have nonnegative binary-rational utilities \(w_{ar}\).
A society is given by its support: the list of the \(\tau\) types with positive mass, each with its mass as a binary rational. Here \(A\) is the union of cohort supports and \(\tau=|A|\), not the number of possible types. Masses and capacities use a fixed population reference unit; cohort masses need not sum to one.
For each round \(t\), an explicitly listed finite-support rational distribution specifies the nonnegative rational cohort vector \(\xi_t\). These vectors are independent across rounds, their laws are known in advance, and \(\xi_t\) is revealed at the start of round \(t\).
Each type has a rational patience law \(p_a(d)\), supported on \(\{0,\ldots,D\}\): exactly \(p_a(d)\xi_{t,a}\) of its arriving mass has deadline \(t+d\), revealed upon arrival. This mass can be matched through that round, or leaves unmatched afterward.
Each eligible pair has a rational occupation law \(q_{ar}(k)\), supported on \(\{1,\ldots,K\}\). Allocating mass \(x\) to that pair in round \(s\) earns \(w_{ar}x\) immediately; exactly \(q_{ar}(k)x\) occupies capacity during rounds \(s,\ldots,s+k-1\), returning before round \(s+k\). These proportions apply to every allocation, independently of its patience subdivision.
A policy may split waiting mass among eligible classes and rounds, but each mass unit is matched at most once; matches cannot be revoked, and occupied mass never exceeds capacity. Returns precede arrivals and allocation in each round. Allocations cease after round \(H\). A causal policy observes only arrivals through the current round and may randomize.
Let \(\mathrm{ALG}\) be its total utility and \(\mathrm{OPT}\) the maximum feasible fluid utility knowing the entire arrival trajectory. Let \(L\) be the total binary input length; \(H,D,K\) are also encoded in unary.
Does there exist an algorithm that, for every instance and rational \(0<\varepsilon<1/2\), constructs and executes a causal policy in time polynomial in \(m,\tau,H,D,K,L,1/\varepsilon\), satisfying \(\mathbb{E}[\mathrm{ALG}]\geq(1/2-\varepsilon)\mathbb{E}[\mathrm{OPT}]\)?
For discrete online matching with non-identical reusable resources and patient agents under known stochastic arrivals, an online algorithm achieves competitive ratio \(1/2-\varepsilon\). [Dong et al.](https://chienjuho.com/pub/AAMAS21_ScarceMatching.pdf)
Related work uses fluid approximations to obtain a \(1-1/e\) guarantee in a large-inventory reusable-resource allocation model; this does not establish the guarantee for the patient fluid model defined here. [Goyal et al.](https://arxiv.org/abs/2010.03983)
I do not resolve the question for arbitrary occupation laws. I prove a reservation theorem that gives new guarantees with arbitrary patience, including overlapping cohorts:
$$
\mathbb E[\mathrm{ALG}]
\geq
\frac{1}{2\min\{K,H\}}\mathbb E[\mathrm{OPT}].
$$
A more precise bound below depends on the occupation tails.
These results use rational fluid allocations directly. They do not expand masses into individual agents.
First consider an auxiliary allocation problem.
There is a finite set $\mathcal V$ of bins, with positive rational capacities $C_v$. A reservation consumes bin capacity permanently. In round $t$, an independent outcome $i\in I_t$ is revealed, with probability $\pi_{t,i}>0$. It specifies the masses $M_{t,i,g}$ of a finite collection of groups $g\in G_t$.
Group $g$ may be assigned to bins in a specified set $S_{t,g}$. Assigning mass $x$ to bin $v$ earns $c_{t,g,v}x$, where $c_{t,g,v}\geq0$ is fixed. Mass may be split, but its total assignment cannot exceed its supply.
Let $\mathrm{OPT}_{\mathrm{res}}$ denote the maximum assignment utility knowing every outcome.
Lemma. There is a deterministic causal reservation policy, constructible and executable in polynomial time in the explicit rational input length, such that
$$
\mathbb E[\mathrm{ALG}_{\mathrm{res}}]
\geq
\frac12\mathbb E[\mathrm{OPT}_{\mathrm{res}}].
$$
Use nonnegative variables $b_{t,i,g,v}$ for allowed assignments, and set all other variables to zero. Write
$$
\bar b_{t,g,v}
=
\sum_{i\in I_t}\pi_{t,i}b_{t,i,g,v}.
$$
Maximize
$$
V=\sum_{t,g,v}c_{t,g,v}\bar b_{t,g,v}
$$
subject to
$$
\sum_v b_{t,i,g,v}\leq M_{t,i,g}
\qquad\text{for every }t,i,g,
$$
$$
\sum_g b_{t,i,g,v}\leq C_v
\qquad\text{for every }t,i,v,
$$
and
$$
\sum_{t,g}\bar b_{t,g,v}\leq C_v
\qquad\text{for every }v.
$$
Its optimal value $V^\star$ satisfies
$$
V^\star\geq\mathbb E[\mathrm{OPT}_{\mathrm{res}}].
$$
To prove this, select an offline optimal assignment $Y_{t,g,v}$ for every outcome trajectory and define
$$
b_{t,i,g,v}
=
\mathbb E[Y_{t,g,v}\mid I_t=i].
$$
The supply constraints follow by conditioning the offline supply constraints. An offline assignment reserves at most $C_v$ in bin $v$ altogether, so its assignments from any one round also total at most $C_v$; conditioning gives the second constraint family. Taking expectations of the total bin-capacity constraints gives the third family. The objective equals $\mathbb E[\mathrm{OPT}_{\mathrm{res}}]$.
There are finitely many trajectories, and each trajectory’s feasible assignment set is a nonempty compact polytope. Thus the selected optima exist, and conditional expectations pose no measurability problem.
Fix an optimal LP solution. Precompute
$$
\alpha_{v,t}
=
1-\frac{1}{2C_v}
\sum_{u<t,g}\bar b_{u,g,v}.
$$
The LP constraints imply
$$
\frac12\leq\alpha_{v,t}\leq1.
$$
Let $F_{v,t}$ be the unreserved capacity of bin $v$ before round $t$. Upon observing outcome $i$, reserve
$$
X_{t,g,v}
=
\frac{F_{v,t}}{2C_v\alpha_{v,t}}b_{t,i,g,v}.
$$
Inductively, $0\leq F_{v,t}\leq C_v$. Consequently,
$$
0\leq
\frac{F_{v,t}}{2C_v\alpha_{v,t}}
\leq1.
$$
For every group,
$$
\sum_vX_{t,g,v}
\leq
\sum_vb_{t,i,g,v}
\leq M_{t,i,g}.
$$
For every bin,
$$
\sum_gX_{t,g,v}
\leq
\frac{F_{v,t}}{2C_v\alpha_{v,t}}C_v
=
\frac{F_{v,t}}{2\alpha_{v,t}}
\leq F_{v,t}.
$$
Thus every reservation is feasible.
I prove inductively that
$$
\mathbb E[X_{t,g,v}\mid I_t=i]
=
\frac12b_{t,i,g,v}.
$$
The induction hypothesis for earlier rounds yields
$$
\begin{aligned}
\mathbb E[F_{v,t}]
&=
C_v-\sum_{u<t,g}\mathbb E[X_{u,g,v}]\\
&=
C_v-\frac12\sum_{u<t,g}\bar b_{u,g,v}\\
&=
C_v\alpha_{v,t}.
\end{aligned}
$$
The unreserved capacity $F_{v,t}$ depends only on earlier outcomes. Independence across rounds therefore implies that it is independent of $I_t$. Hence
$$
\begin{aligned}
\mathbb E[X_{t,g,v}\mid I_t=i]
&=
\frac{b_{t,i,g,v}}{2C_v\alpha_{v,t}}
\mathbb E[F_{v,t}\mid I_t=i]\\
&=\frac12b_{t,i,g,v}.
\end{aligned}
$$
The base case uses $F_{v,1}=C_v$ and $\alpha_{v,1}=1$.
Summing utilities proves
$$
\mathbb E[\mathrm{ALG}_{\mathrm{res}}]
=
\frac12V^\star
\geq
\frac12\mathbb E[\mathrm{OPT}_{\mathrm{res}}].
$$
The equality is with half the LP value; equality with half the expected offline optimum is not asserted.
Discard resource classes with no eligible type. If none remain, both utilities are zero.
For every eligible pair, define the occupation tail
$$
Q_{ar}(h)=\sum_{k=h+1}^{K}q_{ar}(k),
\qquad h\geq0.
$$
An allocation of mass $x$ in round $s$ occupies exactly $Q_{ar}(u-s)x$ in round $u\geq s$. In particular, $Q_{ar}(0)=1$, the tails are nonincreasing, and $Q_{ar}(h)=0$ for $h\geq K$.
For an active resource class $r$, define
$$
U_r(h)=\max_{a:(a,r)\in E}Q_{ar}(h).
$$
Choose an integer block length $\ell_r\in\{1,\ldots,H\}$ for which
$$
\beta_r
=
\min_{a:(a,r)\in E}Q_{ar}(\ell_r-1)
>0.
$$
Such a choice always exists: $\ell_r=1$ gives $\beta_r=1$.
Partition rounds into consecutive blocks
$$
B_{r,j}
=
\{(j-1)\ell_r+1,\ldots,\min(j\ell_r,H)\},
\qquad
j=1,\ldots,n_r,
$$
where
$$
n_r=\left\lceil\frac{H}{\ell_r}\right\rceil.
$$
Set
$$
G_r
=
1+\sum_{j=0}^{n_r-2}U_r(1+j\ell_r),
\qquad
\lambda_r=\frac{\beta_r}{G_r},
$$
with an empty sum interpreted as zero.
Theorem. There is a deterministic polynomial-time causal policy satisfying
$$
\mathbb E[\mathrm{ALG}]
\geq
\frac12\left(\min_r\lambda_r\right)
\mathbb E[\mathrm{OPT}].
$$
Fix a trajectory and a feasible allocation.
Consider block $B_{r,j}$, and let $e_{r,j}$ be its last round. Every allocation to class $r$ started in that block has age at most $\ell_r-1$ at round $e_{r,j}$. Therefore its occupation fraction in that round is at least $\beta_r$.
If $T_{r,j}$ is the total mass allocated to class $r$ during the block, capacity feasibility at its last round gives
$$
\beta_rT_{r,j}\leq\rho_r.
$$
All occupation from earlier blocks is nonnegative, so omitting it preserves this inequality. Consequently,
$$
T_{r,j}\leq\frac{\rho_r}{\beta_r}.
$$
This also holds for the final, possibly shorter block.
Create one bin $(r,j)$ for every resource block, with capacity
$$
C_{r,j}=\frac{\rho_r}{\beta_r}.
$$
The groups arriving in round $t$ are the patience subdivisions $(a,d)$, with masses
$$
M_{t,i,(a,d)}=p_a(d)z_{t,i,a},
$$
where $z_{t,i}$ is the revealed cohort outcome.
Group $(a,d)$ may reserve bin $(r,j)$ precisely when $(a,r)\in E$ and
$$
B_{r,j}\cap\{t,\ldots,\min(H,t+d)\}\neq\varnothing.
$$
Its utility per reserved mass is $w_{ar}$.
Every original feasible allocation induces a feasible offline reservation assignment: assign each match to the bin containing its matching round. Supply constraints are unchanged, and Section 2.1 proves the bin-capacity constraints. Thus, pathwise,
$$
\mathrm{OPT}_{\mathrm{res}}\geq\mathrm{OPT}.
$$
For completeness, an original offline optimum exists: its allocation amounts can be indexed by arrival round, type, patience subdivision, resource class, and matching round. Supply and occupation constraints are finitely many closed linear inequalities, and each variable is bounded by its subdivision’s finite supply. The feasible set is nonempty and compact.
Apply the reservation lemma to obtain reservations $X_{t,a,d,r,j}$.
For every allowed reservation, define the service round
$$
s(t,d,r,j)=\max\{t,(j-1)\ell_r+1\}.
$$
The eligibility of the bin guarantees that this round belongs to the block and does not exceed either $H$ or $t+d$.
A reservation of amount $X_{t,a,d,r,j}$ produces an actual allocation of amount
$$
\lambda_rX_{t,a,d,r,j}
$$
in that service round.
This is causal. At arrival, the policy fixes the future service round and amount using only the current cohort and earlier reservations. Since $0<\lambda_r\leq1$, the actual scheduled amounts from a patience subdivision total at most its reservation total, which is at most its arriving mass. Divisibility permits assigning disjoint pieces to these scheduled matches.
Every piece is served by its deadline, and no piece is served twice.
Pathwise, the total actual allocation mass started in block $B_{r,j}$ is at most
$$
\lambda_rC_{r,j}
=
\frac{\rho_r}{G_r}.
$$
Fix round $u$ in block $B_{r,c}$. Allocations started in the current block occupy at most their total mass, hence at most $\rho_r/G_r$.
For an earlier block $B_{r,b}$, its last round is $b\ell_r$. Every allocation from that block has age at least $u-b\ell_r$, so its occupation fraction is at most
$$
U_r(u-b\ell_r).
$$
Because $u\geq(c-1)\ell_r+1$ and $U_r$ is nonincreasing,
$$
U_r(u-b\ell_r)
\leq
U_r(1+(c-1-b)\ell_r).
$$
Therefore total occupation in class $r$ at round $u$ is at most
$$
\begin{aligned}
\frac{\rho_r}{G_r}
\left(
1+\sum_{b=1}^{c-1}
U_r(1+(c-1-b)\ell_r)
\right)
&=
\frac{\rho_r}{G_r}
\left(
1+\sum_{j=0}^{c-2}U_r(1+j\ell_r)
\right)\\
&\leq\rho_r.
\end{aligned}
$$
The last inequality follows from $c\leq n_r$ and the definition of $G_r$.
This bounds occupation including all allocations made in round $u$. Thus it also ensures that their total mass fits the capacity free immediately before allocation. After round $H$, occupation only decreases.
The calculation uses the stipulated fact that occupation proportions apply to every allocation, independently of its patience subdivision.
Every reserved piece is served within the horizon. Since utilities are nonnegative,
$$
\begin{aligned}
\mathbb E[\mathrm{ALG}]
&=
\sum_{t,a,d,r,j}
w_{ar}\lambda_r
\mathbb E[X_{t,a,d,r,j}]\\
&\geq
\left(\min_r\lambda_r\right)
\mathbb E[\mathrm{ALG}_{\mathrm{res}}]\\
&\geq
\frac12\left(\min_r\lambda_r\right)
\mathbb E[\mathrm{OPT}_{\mathrm{res}}]\\
&\geq
\frac12\left(\min_r\lambda_r\right)
\mathbb E[\mathrm{OPT}].
\end{aligned}
$$
This completes the theorem.
Suppose $q_{ar}(1)=1$ for every eligible pair.
Choose $\ell_r=1$. Then $\beta_r=1$ and $U_r(h)=0$ for every $h\geq1$, so
$$
G_r=1,
\qquad
\lambda_r=1.
$$
The theorem gives
$$
\mathbb E[\mathrm{ALG}]
\geq\frac12\mathbb E[\mathrm{OPT}].
$$
This proves the requested guarantee for arbitrary patience when all allocations return before the next round, including the case $K=1$.
Here the bins are simply resource class–round pairs. Reserving a future bin upon arrival avoids any need to assume independence between a waiting cohort and physical free capacity.
Suppose every active resource class satisfies one of these conditions:
For an immediate-return class, choose $\ell_r=1$, as above.
For a permanent class, choose $\ell_r=H$. Then $n_r=1$, $G_r=1$, and
$$
\beta_r=\min_aQ_{ar}(H-1)=1.
$$
Thus every class has $\lambda_r=1$, and again
$$
\mathbb E[\mathrm{ALG}]
\geq\frac12\mathbb E[\mathrm{OPT}].
$$
The two kinds of class may coexist, with arbitrary eligibility and utilities.
Suppose each class $r$ has an integer $k_r$ such that
$$
q_{ar}(k_r)=1
\qquad
\text{for every eligible }a.
$$
If $k_r=1$, the preceding calculation gives $\lambda_r=1$. If $k_r\geq H$, choose $\ell_r=H$, again giving $\lambda_r=1$.
Otherwise, $2\leq k_r<H$. Choose $\ell_r=k_r$. Then $\beta_r=1$ and
$$
U_r(h)=
\begin{cases}
1,&h<k_r,\\
0,&h\geq k_r.
\end{cases}
$$
There are at least two blocks. In the sum defining $G_r$, the term with $j=0$ equals $U_r(1)=1$, and all terms with $j\geq1$ vanish. Hence
$$
G_r=2,
\qquad
\lambda_r=\frac12.
$$
Therefore, with arbitrary patience and possibly different deterministic lengths across classes,
$$
\mathbb E[\mathrm{ALG}]
\geq\frac14\mathbb E[\mathrm{OPT}].
$$
This bound does not deteriorate with $D$, $H$, or the deterministic occupation lengths.
For unrestricted occupation laws, choose $\ell_r=1$ for every class. Then
$$
\beta_r=1,
\qquad
G_r=1+\sum_{h=1}^{H-1}U_r(h).
$$
Each summand is at most $1$, and all summands with $h\geq K$ vanish. Consequently,
$$
G_r\leq\min\{K,H\}.
$$
The theorem gives
$$
\mathbb E[\mathrm{ALG}]
\geq
\frac{1}{2\min\{K,H\}}\mathbb E[\mathrm{OPT}].
$$
This supplies a guarantee controlled by occupation length rather than patience.
One can obtain the stronger instance-dependent guarantee
$$
\mathbb E[\mathrm{ALG}]
\geq
\frac12
\left[
\min_r
\max_{\substack{1\leq\ell\leq H\\
\min_aQ_{ar}(\ell-1)>0}}
\frac{
\min_{a:(a,r)\in E}Q_{ar}(\ell-1)
}{
1+\displaystyle\sum_{j=0}^{\lceil H/\ell\rceil-2}
U_r(1+j\ell)
}
\right]
\mathbb E[\mathrm{OPT}],
$$
by optimizing each class’s block length before solving the reservation LP.
Suppose, for some $\delta\in[0,1]$,
$$
q_{ar}(1)\geq1-\delta
\qquad
\text{for every eligible pair}.
$$
For every $h\geq1$,
$$
Q_{ar}(h)\leq1-q_{ar}(1)\leq\delta.
$$
Using $\ell_r=1$ therefore gives
$$
G_r\leq1+(\min\{K,H\}-1)\delta,
$$
and hence
$$
\mathbb E[\mathrm{ALG}]
\geq
\frac{1}{
2\bigl(1+(\min\{K,H\}-1)\delta\bigr)
}
\mathbb E[\mathrm{OPT}].
$$
In particular, the requested factor holds whenever
$$
(\min\{K,H\}-1)\delta
\leq
\frac{2\varepsilon}{1-2\varepsilon}.
$$
This follows by rearranging
$$
\frac{1}{2(1+x)}\geq\frac12-\varepsilon.
$$
Let
$$
M=\sum_{t=1}^{H}|I_t|
$$
be the total number of explicitly listed arrival outcomes. Zero-probability outcomes can be deleted, and identical cohort vectors can be merged, so the observed vector identifies its outcome.
There are at most $mH$ bins and $\tau(D+1)$ groups per cohort. The reservation LP therefore has at most
$$
M\tau(D+1)mH
$$
variables, with polynomially many constraints.
Occupation tails, their maxima and minima, and all admissible block-length ratios can be computed with polynomially many rational operations. Their bit lengths are polynomial: each is formed from polynomially many input rationals by sums, comparisons, products, or a quotient with a nonzero denominator.
The LP is rational, zero is feasible, and supply constraints bound every variable. The standard polynomial-time theorem for rational linear programming therefore supplies an optimal rational solution of polynomial encoding length. The relevant input-size and solution-size facts are summarized in [MIT’s linear programming notes](https://ocw.mit.edu/courses/6-854j-advanced-algorithms-fall-2005/d974aef980258f2a796171e96717d646_n11_lp.pdf).
Execution also has polynomial bit complexity. For each bin and possible current outcome, precompute
$$
\kappa_{v,t,i}
=
\frac{\sum_gb_{t,i,g,v}}{2C_v\alpha_{v,t}}.
$$
These are polynomial-length rationals in $[0,1]$. The remaining virtual capacity obeys
$$
F_{v,t+1}=F_{v,t}(1-\kappa_{v,t,I_t}),
$$
so it is a product of at most $H$ precomputed rational factors and its initial capacity. Its numerator and denominator consequently have polynomial bit length. Individual reservations, their scaled service amounts, and the polynomially many scheduled sums also have polynomial bit length.
All schedules use explicitly represented type–deadline groups. Neither construction nor execution enumerates arrival trajectories or individual mass units.
The resulting running time is polynomial in $m,\tau,H,D,K,L$. The policies do not use $\varepsilon$, so their running time also meets the requested polynomial dependence on $1/\varepsilon$.
The block theorem does not establish the requested guarantee for every instance. For example, with one class, deterministic occupation length $2$, and $H\geq3$, its best admissible block-length ratio is $\lambda_r=\frac12$. It therefore proves only a $\frac14$ guarantee, below $\frac12-\varepsilon$ when $\varepsilon<\frac14$.
This is a limitation of the proved construction, not an impossibility result.
The reservation method resolves the dependence issue by making virtual capacity depend only on earlier cohorts. Its remaining loss arises when reservations from different service blocks overlap in physical occupation. The proof bounds that overlap by $G_r$; it does not show that this loss is necessary.
The cited [Dong et al. theorem](https://chienjuho.com/pub/AAMAS21_ScarceMatching.pdf) uses a discrete model with one sampled agent per round. Its application to the present correlated, divisible cohorts would require an additional reduction or argument, which is not supplied here.
For context, a universal factor strictly exceeding $\frac12$ is impossible. The following proof restates the barrier independently of the notes.
Take one resource of capacity $1$, $H=K=2$, and $D=0$. Both types have occupation length $2$. Round one brings mass $1$ with utility $1$. Independently, round two brings mass $1$ with utility $1/p$ with probability $p$, and otherwise no mass, where $p=2^{-b}$ and $b\geq1$.
For any causal policy, let $X\in[0,1]$ be its first-round allocation. No part returns before round two. Independence gives
$$
\mathbb E[\mathrm{ALG}]
\leq
\mathbb E[X]
+
p\frac1p\mathbb E[1-X]
=1.
$$
The offline optimum serves the second cohort whenever it arrives, and otherwise serves the first. Thus
$$
\mathbb E[\mathrm{OPT}]=2-p,
$$
and every causal policy has ratio at most
$$
\frac{1}{2-p}.
$$
As $b$ increases, this approaches $\frac12$. This rules out every universal constant above $\frac12$, while leaving the requested $\frac12-\varepsilon$ guarantee unresolved.
⟨structured verdict parsed — rendered above⟩
The output establishes valid partial results, but does not resolve USER_TASK for arbitrary occupation laws. The reservation lemma, block theorem, stated approximation guarantees, and upper barrier are sound. I found no substantive mathematical error in those arguments.
The unresolved universal guarantee is a major scope gap, explicitly acknowledged by the prover. There is also a minor ambiguity in the indexing of several minima.
1. Reservation lemma
The conditional-outcome LP is a valid upper bound on expected offline reservation utility.
The existence argument is sufficient: finitely many trajectories and nonempty compact feasible polytopes permit selecting an optimum for each trajectory.
The policy is well defined. Positive capacities and
$$
\frac12\leq\alpha_{v,t}\leq1
$$
ensure that its denominator is positive. Given
$$
0\leq F_{v,t}\leq C_v,
$$
the scaling multiplier lies in $[0,1]$. Consequently, summing scaled assignments across bins preserves each group’s supply constraint. The per-outcome bin constraint gives
$$
\sum_gX_{t,g,v}
\leq\frac{F_{v,t}}{2\alpha_{v,t}}
\leq F_{v,t},
$$
which proves capacity feasibility and maintains the induction on remaining capacity.
The expectation induction is correct. The essential independence statement is justified: $F_{v,t}$ depends only on outcomes before round $t$, so it is independent of the current outcome. The induction therefore establishes
$$
\mathbb E[X_{t,g,v}\mid I_t=i]
=\frac12b_{t,i,g,v}.
$$
The base case is explicitly supplied. Summing the utilities proves exactly half the LP value, and hence at least half the expected offline reservation optimum.
Finding: The reservation lemma is proved.
2. Occupation tails and offline block bound
The tail
$$
Q_{ar}(h)=\sum_{k=h+1}^{K}q_{ar}(k)
$$
uses the correct occupation convention. An allocation of age $h$ still occupies capacity precisely for occupation lengths exceeding $h$. In particular, $Q_{ar}(0)=1$, and returns before the next allocation round are handled correctly.
The block supply bound is valid. At the last round of a block, every allocation started within that block has age at most $\ell_r-1$. Monotonicity gives occupation fraction at least $\beta_r$, so
$$
\beta_rT_{r,j}\leq\rho_r.
$$
Discarding occupation from earlier blocks only weakens the capacity constraint. The argument also covers a shorter final block.
The choice $\ell_r=1$ always supplies an admissible positive $\beta_r$. Thus the construction does not encounter an undefined division when longer blocks have zero minimum tail.
Finding: The block bound is proved, including its boundary cases.
3. Reservation reduction and causal scheduling
The offline reduction preserves utilities and supplies: each original match is assigned to the bin containing its actual service round. Its bin is eligible because that service round lies within the arriving subdivision’s permitted service interval. The block supply bound establishes bin feasibility. Therefore,
$$
\mathrm{OPT}_{\mathrm{res}}\geq\mathrm{OPT}
$$
holds pathwise.
The original offline optimum existence argument is also adequate. The explicitly indexed allocation variables have closed linear constraints and finite supply bounds.
For an allowed reservation, the proposed service round
$$
s(t,d,r,j)=\max\{t,(j-1)\ell_r+1\}
$$
is the first round in the intersection of the block and the permitted service interval. Nonempty intersection therefore guarantees that this round is within the horizon and no later than the deadline.
The scaling satisfies
$$
0<\lambda_r\leq1,
$$
because $0<\beta_r\leq1$ and $G_r\geq1$. Consequently, total scheduled mass from each subdivision does not exceed its supply. The explanation using disjoint divisible pieces is sufficient to ensure that no mass is matched twice.
The schedule is causal: reservations and future service commitments use only arrivals already observed. No future arrival information enters the service decisions.
Finding: The reduction and scheduling argument are correct.
4. Physical capacity feasibility
The total actual mass assigned to each block is bounded by
$$
\lambda_rC_{r,j}=\frac{\rho_r}{G_r}.
$$
For a current round $u$ in block $c$, current-block allocations occupy at most this amount. For an earlier block $b$, its latest possible starting round is $b\ell_r$, so every allocation from it has age at least $u-b\ell_r$. The bound using $U_r$ is therefore valid even when occupation laws depend on type.
The monotonicity comparison
$$
U_r(u-b\ell_r)
\leq U_r(1+(c-1-b)\ell_r)
$$
has the correct direction. Reindexing the sum gives precisely the prefix of the sum defining $G_r$. Since $c\leq n_r$ and all terms are nonnegative, total occupation is at most $\rho_r$.
The calculation includes allocations made in round $u$. Because new allocations initially occupy their entire mass, this also proves that those allocations fit the capacity available after returns. After the horizon, no new allocations occur and occupation decreases.
Finding: Physical feasibility is proved. The argument correctly uses deterministic occupation proportions rather than sampled occupation durations.
5. Utility guarantee
Every scaled reservation is served within the horizon. Nonnegative utilities justify extracting $\min_r\lambda_r$ from the utility sum. Both subsequent comparisons have the correct direction:
$$
\mathbb E[\mathrm{ALG}_{\mathrm{res}}]
\geq\frac12\mathbb E[\mathrm{OPT}_{\mathrm{res}}],
\qquad
\mathbb E[\mathrm{OPT}_{\mathrm{res}}]
\geq\mathbb E[\mathrm{OPT}].
$$
Finding: The block theorem establishes its stated factor.
6. Consequences and constants
All stated specializations check out.
$$
\frac{1}{2(1+x)}\geq\frac12-\varepsilon
\quad\Longleftrightarrow\quad
x\leq\frac{2\varepsilon}{1-2\varepsilon},
$$
where the denominator is positive under the required range of $\varepsilon$.
The cases $H=1$ and $K=1$ are covered by empty tail sums. Removing classes without eligible types also avoids minima over empty eligibility sets.
Minor issue: In Sections 3.2 and 3.4, some expressions use $\min_a$ without explicitly restricting the index to eligible types. Occupation tails are defined only for eligible pairs.
Minimum clarification: Specify that every such minimum ranges over $a$ satisfying $(a,r)\in E$.
7. Polynomial construction and execution
The LP size bound is polynomial because the arrival distributions are explicitly listed. There are at most $mH$ bins, $\tau(D+1)$ groups per cohort, and the claimed polynomial number of variables and constraints.
The rational LP theorem is applied under suitable hypotheses: the coefficients are rational, zero is feasible, and finite supply constraints bound every variable. The cited notes support polynomial-time rational LP optimization and polynomial encoding length of suitable optimal solutions. [MIT linear programming notes](https://ocw.mit.edu/courses/6-854j-advanced-algorithms-fall-2005/d974aef980258f2a796171e96717d646_n11_lp.pdf)
The execution argument addresses the important precision issue. Each remaining capacity is a product of at most $H$ precomputed rational factors. Its encoding length therefore grows polynomially, rather than requiring an exponentially large trajectory representation. Individual reservations and scheduled sums likewise have polynomial encoding length and polynomial count.
Merging identical outcomes is legitimate because their cohort vectors specify identical current supplies. It preserves independence between rounds and allows the observed vector to identify the merged outcome.
Finding: Polynomial construction and execution are justified for the guarantees actually proved.
8. Limitations and upper barrier
The deterministic occupation-length example correctly demonstrates a limitation of the block guarantee. For length $2$ and $H\geq3$, only block lengths $1$ and $2$ have positive $\beta_r$. Length $1$ gives $G_r=2$, and length $2$ also gives $G_r=2$. Thus the best admissible ratio is $\lambda_r=\frac12$, yielding only $\frac14$.
This does not establish failure of the requested guarantee for another policy. The prover correctly distinguishes that limitation from impossibility.
The description of the Dong et al. model is supported by its formulation, which samples an individual arriving agent at each time step. The output does not claim an unsupported transfer to fluid cohorts. [Dong et al., setting and preliminaries](https://chienjuho.com/pub/AAMAS21_ScarceMatching.pdf)
The upper barrier is valid. Its inputs satisfy the task’s rationality, support, and independence requirements. For a randomized causal policy, the first-round allocation remains independent of the second-round arrival. Since first-round occupation lasts through round two,
$$
\mathbb E[\mathrm{ALG}]\leq1.
$$
The offline expectation is correctly computed as
$$
(1-p)\cdot1+p\cdot\frac1p=2-p.
$$
Hence every policy has ratio at most $\frac1{2-p}$. These bounds approach $\frac12$ from above and rule out a universal constant strictly exceeding $\frac12$. They do not rule out the requested factor.
9. Required feedback
Major scope gap: The output leaves unanswered whether a polynomial-time causal policy achieves $(\frac12-\varepsilon)\mathbb E[\mathrm{OPT}]$ on every instance. The weaker general guarantee and the upper barrier do not settle that question.
Completing the assignment requires an argument establishing the requested universal guarantee, or an impossibility result that actually excludes it. No correction to the existing calculations alone supplies that missing result. The proved reservation and block results can be retained as valid partial 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.