Answer: —
Theorem 2.4 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateWhen κ = 1, no deterministic IC mechanism can obtain a competitive ratio less than 5. To prove the theorem, in addition to using an adversary argument similar to that in the work of Woeginger (1994), we need to further perturb the job sequence and leverage the shadow job argument. Intuitively, we construct a special job set, in which tight-deadline jobs are released one by one, and any two jobs collide with each other (that is, the deadline of one job is later than the release time of the other, and under any mechanism, it is impossible for these two jobs to be both completed).
statement extracted from the paper’s text layer; consult the paper for the exact wording
Fix a per-capita processing capacity \(b>0\). Given a finite-support rational population over job types \(\theta=(r,d,\ell,v)\), with \(\ell\in[1,\kappa]\), whose cohort masses are revealed only when they arrive, what is the optimal worst-case competitive ratio of deterministic, individually truthful and individually rational online mechanisms against a clairvoyant fluid schedule at capacity \(b\)? In particular, do the lower bounds \(5\) at \(\kappa=1\) and \(\kappa/\ln\kappa+1-o(1)\) for large \(\kappa\) persist?
A society is given by its support: the list of the \(\tau\) types with positive mass, each mass a binary rational; \(\tau\) is the support size, not the number of possible types. Masses sum to \(1\). Types are rational \(\theta=(r,d,\ell,v)\), with \(0\le r<d\), \(v>0\), and \(1\le\ell\le\kappa\); \(b>0\) and \(\kappa\ge1\) are known rational parameters. Running-time bounds use \(m=4\) type coordinates, \(\tau\), total input bit length \(L\), and \(b,\kappa\).
Each cohort is a nonatomic continuum of jobs with fixed, publicly distinguishable identities. Its type and mass are revealed at arrival; the mechanism has no advance knowledge of future support or arrivals, apart from the normalization and public parameters.
A fluid schedule measurably selects jobs to process at unit speed, with active mass at most \(b\) at every time. Cohorts may be split into arbitrary measurable subcohorts. Each job earns its full value only upon completion by its deadline; unfinished work earns nothing.
Consider separately preemption-resume, requiring \(\ell\) total processing time within \([r,d]\), and preemption-restart, requiring \(\ell\) consecutive processing time within that window. The clairvoyant benchmark has the same capacity and processing restrictions.
A deterministic direct mechanism schedules jobs and charges each individual a nonnegative payment \(p\). Reports satisfy \(\hat r\ge r\), \(\hat d\le d\), \(\hat\ell\ge\ell\), \(\hat v>0\), and \(\hat\ell\in[1,\kappa]\); a report is submitted at \(\hat r\). Jobs are returned at their reported deadlines, and processing stops upon reported completion or at the reported deadline.
Utility is \(vq-p\), where \(q\) indicates true completion by the true deadline. Individual dominant-strategy truthfulness and individual rationality apply to each identity, including a single individual's deviation of zero population mass; mechanisms must specify such counterfactual outcomes. Deterministic tie-breaking may use public identities.
Welfare is \(W_M=\int vq\,d\mu\). Define \(C_s(b,\kappa)=\inf_M\sup_{I:W_{\mathrm{OPT},s}(I)>0}W_{\mathrm{OPT},s}(I)/W_M(I)\), over deterministic truthful, individually rational online mechanisms and finite-support rational inputs, for \(s\in\{\mathrm{restart},\mathrm{resume}\}\); a positive numerator divided by zero is \(+\infty\).
What is the optimal worst-case competitive ratio \(C_s(b,\kappa)\) in each model? In particular, do \(C_s(b,1)\ge5\) and \(C_s(b,\kappa)\ge\kappa/\ln\kappa+1-o(1)\) as \(\kappa\to\infty\), with \(b\) fixed, hold, or can either bound be improved upon by a mechanism?
For finite jobs on one unit-speed machine, deterministic truthful mechanisms have competitive ratio at least \(5\) for equal lengths, attained in both models, and at least \(\kappa/\ln\kappa+1-o(1)\) for large \(\kappa\). [Chen et al.](https://www.ijcai.org/proceedings/2017/0707.pdf)
No result settling exactly the nonatomic model specified here was located in the literature search.
For both $s\in\{\mathrm{restart},\mathrm{resume}\}$ and every $\kappa\ge1$, I prove
$$
C_s(b,\kappa)\le \frac{1}{\min\{b,1\}}.
$$
Consequently,
$$
C_s(b,\kappa)=1
\qquad\text{when }b\ge1.
$$
For $0<b<1$, I also prove
$$
1+\min\left\{\frac14,\frac{1-b}{8b}\right\}
\le C_s(b,\kappa)\le\frac1b.
$$
Thus the proposed equal-length lower bound $C_s(b,1)\ge5$ is false whenever $b>1/5$. The proposed growing lower bound
$$
C_s(b,\kappa)\ge \frac{\kappa}{\ln\kappa}+1-o(1)
$$
is false for every fixed $b>0$.
These are partial results: the exact ratios for $0<b<1$, including whether $C_s(b,1)\ge5$ holds for $0<b\le1/5$, remain undetermined.
The finite-job results quoted in the question concern a machine processing at most one finite job at a time. They are not used in the proofs below. [Chen et al.](https://www.ijcai.org/proceedings/2017/0707.pdf)
The upper-bound proof repairs the reporting-domain issue identified in the verifier’s report. It permits infinitely many positive-mass arrival events, uses an infimum for payments, and specifies every singleton’s allocation even when its qualifying admission times have no earliest element.
Write the population as a nonatomic measure space $(X,\mu)$ with $\mu(X)=1$. As required for a measurable scheduling model, report profiles are measurable. Fix deterministic measurable tie-breaking that permits exact splitting of equal-value sets. For example, order reported structural types first, then use public identities within each type.
Put
$$
\beta=\min\{b,1\}.
$$
For a fixed report profile, let
$$
h_t=\mu\{i:\hat r_i=t\},
\qquad
\mathcal E=\{t:h_t>0\},
\qquad
q_t=\beta h_t.
$$
The set $\mathcal E$ is at most countable: for each positive integer $n$, at most $n$ distinct arrival times can have mass at least $1/n$. Moreover,
$$
\sum_{t\in\mathcal E}q_t
=\beta\sum_{t\in\mathcal E}h_t
\le\beta.
$$
The admission opportunities occur at the times in $\mathcal E$. At such a time $t$, the immediately feasible set is
$$
E_t=\{i:\hat r_i\le t,\ t+\hat\ell_i\le\hat d_i\}.
$$
The intended rule is:
For finite $\mathcal E$, this is an ordinary chronological greedy algorithm. For infinite $\mathcal E$, chronological recursion alone is insufficient: $\mathcal E$ need not have a first event, and events can accumulate. The following lemma supplies a well-defined extension.
Let $E$ be a measurable eligible set with a fixed priority order. Let $A$ be the set already admitted. Denote by $H_q(E\setminus A)$ the highest-priority portion of $E\setminus A$ of mass
$$
\min\{q,\mu(E\setminus A)\}.
$$
Define
$$
G_{E,q}(A)=A\cup H_q(E\setminus A).
$$
For measurable sets, use the distance
$$
d_\mu(A,B)=\mu(A\mathbin{\triangle}B).
$$
Lemma. For fixed $E$, priority order, and quota $q$,
$$
d_\mu\bigl(G_{E,q}(A),G_{E,q}(B)\bigr)
\le d_\mu(A,B).
$$
For fixed $E,A$ and two quotas,
$$
d_\mu\bigl(G_{E,q}(A),G_{E,q'}(A)\bigr)
\le |q-q'|.
$$
Proof. Partition the jobs available in at least one of the two states into
$$
U=E\setminus(A\cup B),\qquad
X=E\cap(A\setminus B),\qquad
Y=E\cap(B\setminus A).
$$
Starting from $A$, the available jobs are $U\cup Y$; starting from $B$, they are $U\cup X$.
Let $U_A,Y_A$ be the portions selected from $U,Y$ in the first update, and let $U_B,X_B$ be the portions selected from $U,X$ in the second. The subsets $U_A,U_B$ are initial portions of the same priority order on $U$, so they are nested, modulo null sets. Consequently,
$$
\begin{aligned}
d_\mu\bigl(G_{E,q}(A),G_{E,q}(B)\bigr)
={}&d_\mu(A,B)-\mu(X_B)-\mu(Y_A)\\
&+\left|\mu(U_A)-\mu(U_B)\right|.
\end{aligned}
$$
If both updates select mass $q$, then
$$
\mu(U_A)+\mu(Y_A)=q=\mu(U_B)+\mu(X_B),
$$
and hence
$$
\left|\mu(U_A)-\mu(U_B)\right|
=\left|\mu(X_B)-\mu(Y_A)\right|
\le\mu(X_B)+\mu(Y_A).
$$
If, instead, the first update selects all its available jobs and selects less than $q$, then $U_A=U$ and $Y_A=Y$. If the second update also selects all its available jobs, then $U_B=U$, and the difference term is zero. Otherwise,
$$
\mu(U_B)+\mu(X_B)=q,
$$
so
$$
\mu(U_A)-\mu(U_B)
=\mu(U)-q+\mu(X_B)
\le\mu(X_B),
$$
because $\mu(U)\le q$. The case in which only the second update selects less than $q$ is symmetric. This proves the first inequality.
For the second inequality, the selected sets for quotas $q,q'$ are nested. Their mass difference is
$$
\left|
\min\{q,\mu(E\setminus A)\}
-\min\{q',\mu(E\setminus A)\}
\right|
\le |q-q'|.
$$
This proves the lemma. $\square$
For a finite subset $F\subseteq\mathcal E$, run the greedy algorithm using admission opportunities only at times in $F$. All reports are still received at their actual reported arrivals; only opportunities outside $F$ are suppressed.
Let $A_F(u)$ be the cumulative admitted set after the events in $F$ at times at most $u$. Comparing two finite truncations chronologically and applying the lemma gives
$$
d_\mu\bigl(A_F(u),A_G(u)\bigr)
\le
\sum_{t\in F\mathbin{\triangle}G}q_t
$$
for every time $u$.
Choose increasing finite sets $F_n$ exhausting $\mathcal E$. Since $\sum_tq_t<\infty$, the sets $A_{F_n}(u)$ form a Cauchy sequence in $d_\mu$, uniformly in $u$. Measurable sets modulo null sets are complete for this metric: this follows by viewing their indicators in $L^1$, and taking an almost-everywhere convergent subsequence of an $L^1$-convergent sequence.
Thus there is a limit $A(u)$, independent of the exhaustion. The same argument, using events strictly before $t$, gives a pre-event set $A^-(t)$.
The contraction lemma also implies continuity of the event update. Therefore, for every $t\in\mathcal E$,
$$
A(t)=G_{E_t,q_t}\bigl(A^-(t)\bigr)
$$
modulo null sets. Define the newly admitted set
$$
D_t=A(t)\setminus A^-(t).
$$
Then $\mu(D_t)\le q_t$, and the sets $D_t$ are pairwise disjoint modulo null sets.
We must also check that the limit has no additional admissions arising only from accumulation. For a fixed finite $S\subseteq\mathcal E$, a finite truncation containing $S$ satisfies
$$
\mu(A_F(u))
\le
\sum_{\substack{t\in S\\t\le u}}\mu(D_{t,F})
+
\sum_{t\in\mathcal E\setminus S}q_t,
$$
where $D_{t,F}$ is its admission set at $t$. Passing to the limit gives
$$
\mu(A(u))
\le
\sum_{\substack{t\in S\\t\le u}}\mu(D_t)
+
\sum_{t\in\mathcal E\setminus S}q_t.
$$
Exhausting $\mathcal E$ by finite $S$ shows
$$
A(u)=\bigcup_{\substack{t\in\mathcal E\\t\le u}}D_t
$$
modulo null sets. The corresponding equality with $t<u$ holds for $A^-(u)$.
This construction is online. The pre-event state at $t$ is determined entirely by reports and opportunities strictly before $t$. Its limit can be constructed by exhausting that past history alone. The update at $t$ uses only reports submitted by $t$, the newly observed mass $h_t$, and the pre-event state.
No assumption of finite aggregate report support has been made.
The measure-level construction must now be supplemented with pointwise outcomes, including outcomes for singleton deviations.
At an event $t$, consider the positive-mass eligible pending pool
$$
E_t\setminus A^-(t).
$$
If its mass is at most $q_t$, set the value cutoff $a_t=0$ and offer admission to every eligible pending identity.
Otherwise, let $a_t$ be a quantile satisfying
$$
\mu\{i\in E_t\setminus A^-(t):\hat v_i>a_t\}
\le q_t
\le
\mu\{i\in E_t\setminus A^-(t):\hat v_i\ge a_t\}.
$$
Admit all strictly higher bids and split the cutoff-value set according to the fixed tie-breaking rule.
Such a finite cutoff exists. Indeed, the mass of bids above $z$ tends to zero as $z$ tends to infinity, since every reported bid is finite and the population has finite mass. The quantile inequalities follow from continuity of measure for monotone sequences of sets.
These cutoffs and cutoff tie decisions specify an offer to any eligible identity, including a singleton:
Changing one identity’s report leaves all mass-level states, quotas, and cutoff rules unchanged. Its report changes only its own eligibility, bid, and possible position within a cutoff tie.
For an identity with report $(\hat r,\hat d,\hat\ell,w)$, let $Q$ be its set of qualifying offer times, including eligibility:
$$
Q=\{t\in\mathcal E:\hat r\le t\le\hat d-\hat\ell,\
\text{the identity qualifies at }t\}.
$$
If $Q$ is empty, give it no processing.
If $Q$ is nonempty, define
$$
\sigma=\inf Q.
$$
Process it consecutively for $\hat\ell$ time units from $\sigma$, with the usual immaterial choice of interval endpoints. This finishes by its reported deadline because
$$
\hat r\le\sigma\le\hat d-\hat\ell.
$$
This allocation is causal even if $\sigma\notin Q$. At a current time $u$, the mechanism knows
$$
Q_u=Q\cap(-\infty,u].
$$
If $Q_u$ is nonempty, then
$$
\inf Q_u=\inf Q=\sigma:
$$
all future offer times are greater than $u$, whereas $\inf Q_u\le u$. If $Q$ has no minimum, $Q_u$ is nonempty for every $u>\sigma$. Thus the mechanism can process throughout the interval from $\sigma$ to $\sigma+\hat\ell$, apart from an irrelevant initial endpoint, using only observed offers.
This pointwise allocation agrees almost everywhere with the measure-level admission schedule. To see this, take the union of the null exceptional sets in the selection rule over the countably many events. Outside this union:
Hence almost every admitted identity has a first qualifying event equal to its actual admission event. Identities whose qualifying sets have no minimum lie in a null set. Their specified processing consumes zero population mass.
The qualifying sets and their infima are measurable because $\mathcal E$ is countable. Thus this is a measurable schedule.
Finally, at every time, the active mass is at most the total admitted mass:
$$
\mu(\text{active jobs})
\le\sum_{t\in\mathcal E}\mu(D_t)
\le\sum_{t\in\mathcal E}q_t
\le\beta\le b.
$$
The exceptional singleton conventions do not alter this inequality.
For fixed structural coordinates, define the feasible offer-event set
$$
T(\hat r,\hat d,\hat\ell)
=\{t\in\mathcal E:\hat r\le t\le\hat d-\hat\ell\}.
$$
Define its critical payment by
$$
P(\hat r,\hat d,\hat\ell)
=
\inf_{t\in T(\hat r,\hat d,\hat\ell)}a_t,
$$
with $P=+\infty$ when $T$ is empty.
Charge an admitted identity $P(\hat r,\hat d,\hat\ell)$ and charge an unadmitted identity zero.
An admitted identity has a nonempty feasible event set, so its payment is finite. The payment can be determined by its reported deadline: every event in $T$ occurs by $\hat d-\hat\ell<\hat d$.
For every fixed identity and fixed reports of all other identities:
No attainment assumption is needed. In particular, for the verifier’s sequence $a_{t_n}=1+1/n$, the critical payment is the well-defined number $1$.
Fix an identity of true type $(r,d,\ell,v)$ and fix every other identity’s reports. Since this identity has zero population mass, the events and their aggregate cutoffs are independent of its own report.
Every permitted structural report satisfies
$$
[\hat r,\hat d-\hat\ell]\subseteq[r,d-\ell].
$$
Indeed, $\hat r\ge r$ and
$$
\hat d-\hat\ell\le d-\ell.
$$
Consequently,
$$
T(\hat r,\hat d,\hat\ell)\subseteq T(r,d,\ell),
$$
and therefore
$$
P(\hat r,\hat d,\hat\ell)\ge P(r,d,\ell).
$$
Write $P_{\mathrm{true}}=P(r,d,\ell)$.
Under any permitted report, admission gives true completion. The mechanism supplies the entire reported length consecutively within the reported window, and
$$
\hat\ell\ge\ell,\qquad
\hat r\ge r,\qquad
\hat d\le d.
$$
Rejection gives no processing. Thus there is no possibility of obtaining true completion from an unfinished inflated-length report while paying zero.
If truthful reporting wins, its payment satisfies $P_{\mathrm{true}}\le v$. Any winning deviation pays at least $P_{\mathrm{true}}$ and earns the same value $v$. Any losing deviation earns zero utility, whereas truthful utility is nonnegative.
If truthful reporting loses, the critical-value property implies
$$
v\le P_{\mathrm{true}}.
$$
Any winning deviation then has utility
$$
v-P(\hat r,\hat d,\hat\ell)\le0.
$$
A losing deviation has utility zero.
Truthful reporting is therefore dominant for every identity, including singleton counterfactuals. Payments are nonnegative, and truthful utility is nonnegative, establishing individual rationality.
Call a job individually feasible if
$$
d-r\ge\ell.
$$
An individually infeasible job cannot contribute to either benchmark.
At a truthful arrival time $t$, let $V_t$ be the total value of individually feasible newly arriving jobs. Their mass is at most $h_t$.
By nonatomic splitting, select a $\beta$ fraction of each newly arriving feasible type. This comparison selection has mass at most
$$
\beta h_t=q_t
$$
and value exactly $\beta V_t$. Every job in it is immediately feasible.
The greedy rule selects the highest-value eligible pending mass subject to this same quota, from a pool containing the comparison selection. Hence its newly admitted value at $t$ is at least $\beta V_t$.
Admissions at different events are disjoint, and every admitted job completes. Therefore,
$$
W_M\ge\beta\sum_t V_t.
$$
The benchmark can complete only individually feasible jobs, so
$$
W_{\mathrm{OPT},s}\le\sum_tV_t.
$$
Combining these inequalities yields
$$
W_M\ge\beta W_{\mathrm{OPT},s},
$$
and thus
$$
C_s(b,\kappa)\le\frac1\beta
=\frac1{\min\{b,1\}}.
$$
This proof applies to both models because the mechanism always supplies consecutive processing.
On finite-support report profiles, there are at most $\tau$ admission events. The construction reduces to sorting residual cohort types and updating rational admitted masses. Payments are minima over finitely many recorded cutoffs. With cohort splitting represented by admitted mass per type, this uses polynomially many bit operations in $\tau$ and $L$; it does not enumerate possible types.
The preceding bound gives $C_s(b,\kappa)\le1$. Every feasible mechanism’s schedule is also feasible for its corresponding clairvoyant benchmark, so its welfare cannot exceed benchmark welfare. Hence $C_s(b,\kappa)\ge1$, proving
$$
C_s(b,\kappa)=1
\qquad(b\ge1).
$$
There is also a simpler mechanism in this range: process every individually feasible report continuously from its reported arrival, and charge zero. Active mass never exceeds the total population mass $1$. Truthful feasible jobs receive their full value, so no permitted deviation can improve their utility.
The following construction applies to every deterministic online scheduler, without any truthfulness assumption.
Choose positive masses $a,c$ satisfying
$$
a\le b,\qquad c\le b,\qquad c\ge b-a,\qquad c+2a\le1.
$$
Consider two inputs with the following cohorts:
| Cohort | Mass | Release | Deadline | Length | Value |
|---|---:|---:|---:|---:|---:|
| $A$ | $a$ | $0$ | $1$ | $1$ | $1$ |
| $B$ | $c$ | $1/2$ | $3/2$ | $1$ | $2$ |
| $C$, input $0$ | $a$ | $1$ | $3/2$ | $1$ | $2$ |
| $C$, input $1$ | $a$ | $1$ | $2$ | $1$ | $2$ |
Use the same identities and reports before time $1$ in both inputs. Any remaining mass $1-c-2a$ arrives later with an infeasible window, for example with release $3$, deadline $7/2$, length $1$, and value $1$.
All feasible windows above are tight. In the resume model, completing a length-$1$ job in a window of length $1$ requires processing it at unit speed almost everywhere in that window: the integral of a processing rate bounded by $1$ can equal $1$ only this way. The same necessity holds in the restart model.
Let $y$ be the mass of $A$ completed by the scheduler. Its processing before time $1$ determines $y$, and the two inputs have identical histories before then. Their common value of $y$ therefore satisfies
$$
0\le y\le a\le b.
$$
Cohort $C$ is infeasible. If the scheduler completes mass $x_0$ of $B$, the completed portions of $A$ and $B$ both require processing throughout $(1/2,1)$.
Integrating their required processing over that overlap and applying capacity gives
$$
y+x_0\le b.
$$
Thus
$$
W_M^{(0)}=y+2x_0\le2b-y.
$$
The benchmark can complete all $c$ mass of $B$, so
$$
W_{\mathrm{OPT},s}^{(0)}\ge2c.
$$
If the scheduler completes masses $x_1,z_1$ of $B,C$, respectively, their required processing overlaps throughout $(1,3/2)$. Hence
$$
x_1+z_1\le b
$$
and
$$
W_M^{(1)}
=y+2x_1+2z_1
\le y+2b.
$$
The benchmark can complete all of $A$ and $C$, together with mass $b-a$ of $B$. This selection exists because
$$
0\le b-a\le c.
$$
On each overlap interval, its active mass is
$$
a+(b-a)=b.
$$
Outside the overlaps its active mass is at most $b$. Its value is
$$
a+2a+2(b-a)=2b+a.
$$
Therefore,
$$
W_{\mathrm{OPT},s}^{(1)}\ge2b+a.
$$
The denominators below are positive because $0\le y\le b$. At least one input has competitive ratio at least
$$
\max\left\{
\frac{2c}{2b-y},
\frac{2b+a}{2b+y}
\right\}.
$$
If the scheduler has zero welfare on either input, the corresponding ratio is infinite and the bound already holds.
The maximum of two fractions with positive denominators is at least their denominator-weighted average. Consequently,
$$
\max\left\{
\frac{2c}{2b-y},
\frac{2b+a}{2b+y}
\right\}
\ge
\frac{2c+2b+a}{4b}.
$$
Set
$$
a_*=\min\left\{b,\frac{1-b}{2}\right\}.
$$
Choose dyadic positive $a,c$ approaching $a_*,b$ from below, with $b-c<a$. These choices satisfy all the required inequalities: in particular,
$$
c+2a<b+2a_*\le1,
\qquad
c>b-a.
$$
The residual mass is also dyadic and nonnegative. Thus the inputs are valid even under the more restrictive interpretation of binary rational masses as dyadic masses.
For every deterministic scheduler, the supremum over these rational inputs is therefore at least the limiting bound
$$
\frac{4b+a_*}{4b}
=
1+\min\left\{\frac14,\frac{1-b}{8b}\right\}.
$$
Taking the infimum over truthful mechanisms proves
$$
C_s(b,\kappa)
\ge
1+\min\left\{\frac14,\frac{1-b}{8b}\right\}.
$$
All lengths are $1$, and each input has at most four support types. The bound therefore applies to both models for every $\kappa\ge1$.
The proved upper bound gives
$$
C_s(b,1)<5
\qquad\text{for every }b>1/5.
$$
For example, when $b=1/2$, the admission mechanism is truthful and has ratio at most $2$ for every $\kappa$.
For every fixed $b>0$, the same bound is independent of $\kappa$, whereas
$$
\frac{\kappa}{\ln\kappa}+1-o(1)\longrightarrow+\infty.
$$
Thus the proposed asymptotic lower bound cannot hold in the specified nonatomic model.
What remains open is the exact optimum for $0<b<1$. The results here also do not decide whether the equal-length lower bound $5$ survives for $0<b\le1/5$, or whether the two processing models have different optimal ratios.
⟨structured verdict parsed — rendered above⟩
The output establishes substantial partial results. I find no substantive error in the stated upper bound, the exact result for $b\ge1$, or the stated lower bound for $0<b<1$. It does not determine the optimal ratios throughout the parameter range requested in USER_TASK, and it correctly acknowledges that limitation.
The established claims are
$$
C_s(b,\kappa)\le\frac{1}{\min\{b,1\}},
$$
$$
C_s(b,\kappa)=1\qquad(b\ge1),
$$
and
$$
1+\min\left\{\frac14,\frac{1-b}{8b}\right\}
\le C_s(b,\kappa)\le\frac1b
\qquad(0<b<1).
$$
These apply to both processing models and every $\kappa\ge1$.
They imply the claimed failures of the proposed lower bounds in the specified ranges. However, the exact optimum for $0<b<1$ remains unresolved.
Major issue — incomplete resolution of the task. The task asks for the optimal worst-case competitive ratio in each model. The bounds supplied generally do not coincide for $0<b<1$.
Required follow-up: Determine the exact ratios in that range, or retain the explicit designation of these results as partial. This is missing mathematical content, not an expositional defect.
The definition
$$
\beta=\min\{b,1\},\qquad q_t=\beta h_t
$$
is valid. Positive-mass arrival times are countable: the stated bound on the number of times with $h_t\ge1/n$, followed by a countable union, establishes this.
The inequality
$$
\sum_{t\in\mathcal E}q_t\le\beta
$$
also holds when the arrival-time distribution has a nonatomic component. Such a component contributes no admission opportunities under this rule; that does not invalidate the construction or its guarantee on finite-support truthful inputs.
The decomposition into $U,X,Y$ correctly describes the available pools in the two states.
Because selection uses one fixed priority order, the selected portions $U_A,U_B$ are nested modulo null sets. The symmetric-difference identity therefore correctly accounts for:
When both updates fill quota $q$, the displayed mass equations imply the required bound.
When the first update exhausts its available pool below quota, the proof correctly uses
$$
\mu(U)\le q
$$
to bound the difference in selected $U$ mass. The symmetric case covers the remaining possibility.
Thus
$$
d_\mu(G_{E,q}(A),G_{E,q}(B))\le d_\mu(A,B)
$$
is established.
For a fixed available pool, selections at two quotas are nested. Their mass difference is the difference of the two truncated quotas. Hence
$$
d_\mu(G_{E,q}(A),G_{E,q'}(A))\le|q-q'|
$$
is correct.
No error was found in either inequality.
The finite-truncation comparison is justified by the contraction lemma. A common event cannot increase the discrepancy; an event present in only one truncation can increase it by at most its quota.
Consequently, the summable quota tails give a uniformly Cauchy family of cumulative admitted sets. The asserted completeness of measurable sets modulo null sets under $d_\mu$ is valid: an $L^1$ limit of indicators has an indicator representative, as justified by the almost-everywhere subsequence argument.
The pre-event construction and continuity of the update justify
$$
A(t)=G_{E_t,q_t}(A^-(t))
$$
modulo null sets. Taking set differences is also continuous in this metric, so the finite-truncation admission sets converge to $D_t$.
The argument excluding admissions created solely by accumulation is sound. The displayed finite-subset estimate bounds any admission mass not attributable to the selected finite collection of events by the remaining quota tail. Exhausting the events makes that tail vanish.
Minor issue — omitted set-inclusion explanation. The displayed estimate directly establishes the mass bound needed for the union identity, but the write-up does not explicitly state the complementary inclusion
$$
\bigcup_{\substack{t\in\mathcal E\\t\le u}}D_t\subseteq A(u)
$$
modulo null sets.
Minimum clarification: State that chronological monotonicity of the finite histories passes to their limits, giving this inclusion and pairwise disjointness of the event increments. This is a routine clarification and requires no new mathematics.
The online claim is otherwise justified: the construction of a state at time $t$ uses only the history through $t$, even when that history has infinitely many events.
For a pool of mass greater than $q_t$, a finite quantile cutoff exists under the stated assumptions. In particular, $q_t>0$, all individual bids are finite, and the upper-tail mass tends to zero. The quantile inequalities and the prescribed splitting of a cutoff tie support the stated admission rule.
A singleton report change leaves aggregate masses and the measure-level histories unchanged. Structural changes can alter the singleton’s tie position, as the output expressly allows; they do not change aggregate cutoffs.
For nonempty $Q$, eligibility gives
$$
\hat r\le\inf Q\le\hat d-\hat\ell.
$$
Thus the specified consecutive processing fits within the reported window.
The causality argument is valid. Whenever $Q_u$ is nonempty, every excluded future offer lies after $u$, whereas
$$
\inf Q_u\le u.
$$
Therefore future offers cannot lower that infimum. If $Q$ has no minimum, every $u>\inf Q$ has a qualifying offer in its observed past. The unobservable initial endpoint contributes no processing time.
The countable-event exceptional-set argument correctly confines disagreement with the measure-level admission history to a null set. Together with countability of $\mathcal E$, it supports measurability of the pointwise allocation.
The resulting capacity estimate is valid at every time:
$$
\mu(\text{active jobs})\le\sum_t\mu(D_t)\le\beta\le b.
$$
The infimum payment correctly handles nonattainment. For finite $P$:
An admitted identity has a nonempty feasible event set and therefore a finite, nonnegative payment. Every relevant event occurs before the reported deadline, so the payment can be determined by that deadline.
No attainment assumption is improperly used.
The structural-report inclusion
$$
[\hat r,\hat d-\hat\ell]\subseteq[r,d-\ell]
$$
is correct whenever the reported interval is nonempty; an empty reported interval contributes no feasible events. Consequently,
$$
T(\hat r,\hat d,\hat\ell)\subseteq T(r,d,\ell),
\qquad
P(\hat r,\hat d,\hat\ell)\ge P(r,d,\ell).
$$
Every admitted permitted report receives enough consecutive processing to complete the true job within its true window. Every rejected report receives no processing. Thus the proof correctly avoids a discrepancy between reported admission and true completion.
The utility comparisons cover truthful winners, truthful losers, and equality at the critical payment. In particular, if truthful reporting loses at $v=P_{\mathrm{true}}$, a winning deviation can yield at most zero utility.
The argument establishes individual dominant-strategy truthfulness and individual rationality, including singleton deviations.
At a truthful arrival event, newly arriving feasible jobs have not been admitted earlier and are immediately feasible. The comparison selection has mass at most $q_t$ and value exactly $\beta V_t$.
Highest-value selection from a pool containing that comparison selection therefore yields admitted value at least $\beta V_t$. Finite-support truthful inputs make this a finite-valued, finite-event comparison.
Summing disjoint admissions gives
$$
W_M\ge\beta\sum_tV_t.
$$
Every benchmark completion must be individually feasible, so
$$
W_{\mathrm{OPT},s}\le\sum_tV_t.
$$
The claimed upper bound follows.
The mechanism uses consecutive processing, so the argument applies to both models.
For $b\ge1$, the upper bound is $1$, and benchmark dominance supplies the matching lower bound. The simpler zero-payment mechanism described in the output is also valid, including for individually infeasible true jobs, whose permitted reports cannot make them feasible.
The finite-support implementation claim is consistent with the described operations: there are at most $\tau$ events, rational mass updates, and finitely many cutoff comparisons. It does not enumerate the universe of possible types.
The mass constraints ensure valid inputs and sufficient capacity for the benchmark selections. All lengths equal $1$, so the instances are permitted for every $\kappa\ge1$.
The inputs agree before time $1$. Completion of an $A$ job requires processing throughout its tight window almost everywhere, so its completion is determined by that common history. Endpoint decisions cannot change its completed processing amount.
The tight-window necessity is correctly established in both processing models.
Completed $A$ and $B$ portions require simultaneous processing over their overlap. The capacity argument correctly gives
$$
y+x_0\le b.
$$
Therefore
$$
W_M^{(0)}\le2b-y.
$$
Completing all mass $c$ of $B$ establishes the stated benchmark lower bound $2c$.
The corresponding overlap constraint is
$$
x_1+z_1\le b,
$$
which yields
$$
W_M^{(1)}\le y+2b.
$$
The proposed benchmark selection is feasible because
$$
0\le b-a\le c.
$$
Its overlap load is $b$, and its welfare calculation
$$
a+2a+2(b-a)=2b+a
$$
is correct.
Both bounding denominators are positive since $0\le y\le b$ and $b>0$. The denominator-weighted average correctly gives
$$
\max\left\{\frac{2c}{2b-y},\frac{2b+a}{2b+y}\right\}
\ge\frac{2c+2b+a}{4b}.
$$
The dyadic approximation respects all mass constraints and normalization. Its limit is
$$
1+\frac{a_*}{4b}
=
1+\min\left\{\frac14,\frac{1-b}{8b}\right\}.
$$
The bound holds uniformly for each scheduler before taking the infimum over truthful mechanisms. No quantifier error was found.
The upper bound strictly improves on $5$ whenever $b>1/5$. It also remains bounded independently of $\kappa$ for each fixed $b>0$, contradicting the proposed diverging asymptotic lower bound.
These consequences are established. Whether the equal-length bound $5$ holds for $0<b\le1/5$, the exact ratios for $0<b<1$, and possible differences between the two models remain unresolved.
⟨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.