Answer: \(R^*(B,k,T)=1\) for every admissible \(B,k,T\).
Theorem 5 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateFor general $k$ and $T$, no (randomized) mechanism can achieve a competitive ratio better than $\frac{2}{\log 8kT}$ for social welfare.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given an ordered sequence of \(\tau\) cohorts with binary-rational masses \(\mu_i\) summing to \(1\), each cohort consists of individually strategic members sharing a complete reservation type \(\theta_i=(a_i,d_i,t_i,c_i,v_i)\), including its arrival stage; future cohorts are hidden. With normalized capacity \(B\), request densities \(\rho_i=v_i/(c_it_i)\in[1,k]\), and lengths \(t_i\in[1,T]\), each member must receive either a complete reservation or none. What is the supremal worst-case expected social-welfare competitive ratio achievable by a randomized, individually truthful online policy that chooses accepted mass and feasible start times as each cohort arrives, compared with the offline optimum for the same cohort sequence?
A society is given by its support: an ordered list of \(\tau\) types with positive binary-rational masses \(\mu_i\), with \(\sum_i\mu_i=1\); \(\tau\) is the support size, not the number of possible types. There is one reusable resource kind, so \(m=1\); running-time parameters are \(m,\tau\), total input bit length \(L\), and \(B,k,T\).
Each type comprises an exogenous submission time \(s_i\) and reservation data \(\theta_i=(a_i,d_i,t_i,c_i,v_i)\). All numerical data are binary rationals, \(B>0\), \(k,T\geq1\), \(s_i\leq a_i\), \(a_i+t_i\leq d_i\), \(1\leq t_i\leq T\), \(0<c_i\leq B\), and \(1\leq v_i/(c_it_i)\leq k\). Submission times are nondecreasing; equal-time cohorts arrive in the given order.
Each cohort is atomless and its members act individually. Serving a member means committing to an uninterrupted reservation of intensity \(c_i\) for length \(t_i\), starting in \([a_i,d_i-t_i]\); partial service earns no value. Serving mass \(x\) contributes welfare \(xv_i\) and resource load \(xc_i\) while its reservations run.
A realized allocation may distribute accepted members across start times: let \(q_i\) be their start-time mass measure, supported on \([a_i,d_i-t_i]\), with \(x_i=q_i(\mathbb R)\leq\mu_i\). Feasibility requires \(\sum_i c_iq_i((u-t_i,u])\leq B\) at every time \(u\). Welfare is \(\sum_i v_ix_i\); \(\operatorname{OPT}(I)\) is the supremum feasible welfare with the entire sequence known.
An online mechanism knows \(B,k,T\) and total mass \(1\), but learns each cohort only when it arrives. It immediately and irrevocably assigns acceptance, start times, and payments, with feasibility in every realization.
Rejected members pay nothing and have utility zero; accepted members pay \(p\geq0\) and have utility \(v_i-p\). Require individual rationality and universal individual truthfulness: for every fixed random seed and other members’ reports, truthful reporting maximizes each member’s utility. Admissible reports satisfy \(\hat a\geq a\), \(\hat d\leq d\), \(\hat t\geq t\), \(\hat c\geq c\), and otherwise the stated type domain; value may be misreported. Submission time is not strategic. Individual deviations must have defined outcomes even though they have zero mass.
What is the supremal competitive ratio \(R^*(B,k,T)=\sup_M\inf_I \mathbb E[W_M(I)]/\operatorname{OPT}(I)\) over these randomized truthful online mechanisms, where the infimum ranges over all finite admissible sequences fixed independently of the mechanism’s randomness?
For discrete reservations, randomized mechanisms have the published welfare upper bound \(2/\log_2(8kT)\); truthful randomized mechanisms attain \(1/(42\lceil\log_2 k\rceil\lceil\log_2 T\rceil)\) when \(k,T>1\). [Source](https://ojs.aaai.org/index.php/AAAI/article/view/10596/10455).
No result settling exactly the atomless model above was located.
The normalization makes every instance uncongested: total mass is \(1\), and every member’s intensity is at most \(B\). Consequently, \(R^*(B,k,T)=1\) for every admissible \(B,k,T\).
I interpret the target as the explicitly specified atomless model. There is no capacity-constrained case within these premises; such a case would require changing a hypothesis.
For any start-time measures satisfying \(q_i(\mathbb R)\leq\mu_i\), and every time \(u\),
\[
\sum_i c_iq_i((u-t_i,u])
\leq \sum_i c_iq_i(\mathbb R)
\leq \sum_i c_i\mu_i
\leq B\sum_i\mu_i
=B.
\]
Thus the capacity constraint holds regardless of how accepted members are distributed across their admissible start times.
In particular, let \(\delta_{a_i}\) denote unit point mass at \(a_i\), and choose \(q_i=\mu_i\delta_{a_i}\). This serves every member of type \(i\) starting at \(a_i\). The start is admissible because \(a_i+t_i\leq d_i\), and the preceding inequality proves feasibility.
Every allocation has welfare at most \(\sum_i\mu_iv_i\), since \(v_i>0\) and its accepted masses satisfy \(x_i\leq\mu_i\). The full-service allocation attains this bound. Therefore
\[
\operatorname{OPT}(I)=\sum_i\mu_iv_i>0.
\]
Upon receiving any admissible report \((\hat a,\hat d,\hat t,\hat c,\hat v)\), accept the member, assign start time \(\hat a\), reserve intensity \(\hat c\) for duration \(\hat t\), and charge zero.
This decision is immediate and irrevocable. Since submission time is nonstrategic and precedes the reported start, the reservation never starts before submission.
Feasibility holds even when members submit different admissible reports. Indeed, every reported intensity is at most \(B\), so the aggregate load at any time is at most \(B\) times the society’s total mass, namely \(B\).
The rule also defines an outcome for every zero-mass individual deviation: that individual receives the reported reservation for free. Changing one individual’s report does not change any aggregate load.
To verify truthfulness, fix a member’s true type and all other reports. Truthful reporting provides complete service and utility \(v\). An admissible deviation also provides complete service for the true requirements: its assigned start \(\hat a\) satisfies
\[
\hat a\geq a,\qquad
\hat a+t\leq\hat a+\hat t\leq\hat d\leq d,
\]
and its reserved intensity satisfies \(\hat c\geq c\). Its payment remains zero, so its utility remains \(v\). Value misreports likewise change neither allocation nor payment. Hence truthful reporting maximizes utility, and individual rationality holds. The mechanism is deterministic, so this proves universal individual truthfulness.
On every instance, the mechanism obtains welfare \(\sum_i\mu_iv_i=\operatorname{OPT}(I)\), establishing a competitive ratio of \(1\).
Conversely, every realization of any permitted mechanism is feasible and therefore has welfare at most \(\operatorname{OPT}(I)\). Taking expectations proves that no mechanism can have a competitive ratio exceeding \(1\).
The quoted discrete bounds concern a different capacity model, where each accepted request consumes its stated intensity without multiplication by population mass. [The cited paper](https://ojs.aaai.org/index.php/AAAI/article/view/10596/10455) therefore does not contradict this conclusion. Here, the combined assumptions \(\sum_i\mu_i=1\) and \(c_i\leq B\) eliminate resource competition entirely.
⟨structured verdict parsed — rendered above⟩
The prover resolves the stated task correctly: \(R^*(B,k,T)=1\) for every admissible \(B,k,T\). No major or minor issues were found.
The absence of congestion follows from explicit hypotheses of USER_TASK, rather than an unintended interpretation: population mass is \(1\), resource load is multiplied by served mass, and every intensity is at most \(B\).
Each inequality in the displayed capacity bound is valid:
The bound holds for every time \(u\), including reservation endpoints under the specified interval convention. It does not depend on overlaps, reservation lengths, or the ordering of arrivals.
The first sentence of this section appropriately restricts the measures to admissible start times. The capacity calculation alone would not establish start-window admissibility, but the prover checks that separately.
The proposed measure \(q_i=\mu_i\delta_{a_i}\) has total mass \(\mu_i\). Its support is admissible because \(a_i+t_i\leq d_i\), equivalently \(a_i\leq d_i-t_i\). The preceding capacity bound establishes feasibility.
The welfare upper bound also holds. The domain implies \(v_i\geq c_it_i>0\), so \(x_i\leq\mu_i\) gives \(v_ix_i\leq v_i\mu_i\). Consequently, every feasible allocation has welfare at most \(\sum_i\mu_iv_i\), and the proposed allocation attains that value.
Thus the supremum defining \(\operatorname{OPT}(I)\) is attained here, and \(\operatorname{OPT}(I)>0\). Division by the optimum later in the proof is justified.
The mechanism specifies acceptance, start time, reserved intensity, duration, and payment immediately upon receipt of a report. It uses no future information and makes no subsequent revisions.
Starting at \(\hat a\) is valid for the reported reservation because admissible reports satisfy \(\hat a+\hat t\leq\hat d\). It also respects submission time: \(s\leq a\leq\hat a\).
The feasibility argument remains valid when reports differ within a cohort. Every member’s reported intensity is bounded by \(B\); therefore, integrating active reported intensity over a population of mass \(1\) yields load at most \(B\). Splitting cohorts into different reports does not invalidate this bound.
The rule explicitly defines the outcome of a zero-mass individual deviation. Such a deviation changes neither population mass nor aggregate load, while still receiving a specified reservation and payment. This addresses the task’s individual-deviation requirement.
Truthful reporting gives the member an uninterrupted reservation meeting its requirements, at payment zero, and therefore utility \(v\).
For every admissible deviation, the prover correctly verifies
\[ \hat a\geq a,\qquad \hat a+t\leq\hat a+\hat t\leq\hat d\leq d. \]
The reserved intensity satisfies \(\hat c\geq c\), and the duration satisfies \(\hat t\geq t\). Thus the deviating reservation still completes the true requirements within the true time window.
Payment remains zero, so the deviation gives the same utility \(v\). Value reports do not affect allocation or payment. Truthful reporting therefore weakly maximizes utility for every fixed profile of other admissible reports. Strict preference for truthfulness is not required.
Individual rationality follows from \(v>0\). Since the mechanism is deterministic, the same argument establishes universal individual truthfulness.
On every admissible instance, truthful execution serves the entire population and obtains exactly \(\operatorname{OPT}(I)\). Hence its competitive ratio is \(1\).
Conversely, each realization of any permitted mechanism is a feasible allocation, so its welfare is at most \(\operatorname{OPT}(I)\). Taking expectations preserves that bound. This establishes both directions needed for the claimed supremum.
The proof covers \(k=1\), \(T=1\), arbitrary admissible \(B>0\), and every finite support size. It requires no logarithmic bound or limiting construction.
The comparison with the discrete model is accurate: the cited paper models each reservation as a customer request for its stated number of resources, without the normalized population-mass multiplier used here. Its bounds therefore do not contradict this result. [Cited paper](https://ojs.aaai.org/index.php/AAAI/article/view/10596/10455)
No repair or additional clarification is required. The complexity field below is marked unresolved solely because the prover does not explicitly classify computational complexity; its competitive-ratio claim is fully proved.
⟨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.