Answer: —
Theorem 4.4 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateFor all arrival models, given the three objec- tives: operator’s profit, offline side group (individual) fair- ness, and online side group (individual) fairness. No algo- rithm can achieve a competitive ratio of (α, β, γ) over the three objectives simultaneously such that α + β + γ > 1. It is natural to wonder if we can combine individual and group fairness. Though it is possible to extend our algo- rithms to this setting.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finite driver and request type sets, rational offline masses, rational per-period arrival masses, edge data, group memberships, and a finite horizon, characterize the competitive-ratio vectors achievable by causal fluid matching policies. Each policy may split mass among allowed probe sequences, tracking patience states and splitting probed mass into successful and failed fractions according to edge success probabilities; compare its operator-profit and group-fairness values with the separate fluid optima. Determine whether every achievable three-objective vector satisfies \(r_O+r_U+r_V\leq 1\), for group fairness and for the corresponding per-unit and per-arrival-cohort individual-fairness objectives.
Let \(U,V\) be finite driver and request type sets, with allowed edges \(E\), horizon \(T\geq1\), initial driver masses \(a_u>0\), and known arrival masses \(b_{v,t}\geq0\), where \(\sum_v b_{v,t}=1\) and \(n_v=\sum_t b_{v,t}>0\). Stationary arrivals mean \(b_{v,t}=b_v\).
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=|U|+|V|\) is the support size, not the number of possible types. All arrival masses, edge probabilities \(p_e\in[0,1]\), and utilities \(w_e^O,w_e^U,w_e^V\geq0\) are binary rationals; patience limits \(\Delta_u,\Delta_v\geq1\) are integers. State running times in \(m=|E|\), \(\tau\), total input bit length \(L\), \(T\), and the patience limits.
Each side is partitioned into nonempty groups. A causal fluid policy knows the input but uses only currently arrived requests and available drivers; it may reject mass or split it among adaptive probe sequences within its arrival period.
A probe couples equal driver and request masses \(q\) on an allowed edge: \(p_eq\) succeeds, earns the three edge utilities per matched unit, and removes both matched fractions; the remaining \((1-p_e)q\) increments both failure counters. Driver failure counts persist across periods; requests depart at the end of their arrival period. Either unit departs upon success or upon reaching its patience limit. The same driver unit cannot be probed twice by the same request unit; different driver units of one type may occur in a sequence.
Initially identical driver units receive symmetric treatment. Let \(x_{uv,t}\) be the total successful mass on edge \((u,v)\) in period \(t\), and write \(D_u=\sum_{v,t}w^U_{uv}x_{uv,t}\), \(R_v=\sum_{u,t}w^V_{uv}x_{uv,t}\), and \(O=\sum_{u,v,t}w^O_{uv}x_{uv,t}\).
Group fairness values are \(F_U=\min_g\frac{\sum_{u\in U(g)}D_u}{\sum_{u\in U(g)}a_u}\) and \(F_V=\min_g\frac{\sum_{v\in V(g)}R_v}{\sum_{v\in V(g)}n_v}\). Individual fairness instead uses \(F_U=\min_u D_u/a_u\) and arrival-cohort fairness \(F_V=\min_t\sum_{u,v}w^V_{uv}x_{uv,t}\), averaging across request types within each period.
For each instance \(I\), let \(\operatorname{OPT}_j(I)\) be the separate supremum of objective \(j\in\{O,U,V\}\) over feasible fluid schedules obeying these same temporal and probing restrictions. Restrict to instances with all three benchmarks positive. A vector \(r\in[0,1]^3\) is achievable if one causal policy family guarantees \(F_j(I)\geq r_j\operatorname{OPT}_j(I)\) on every instance, with \(F_O=O\).
Which competitive-ratio vectors are achievable for this fluid model, separately for group fairness and individual fairness, with stationary and with time-dependent arrivals? Must every achievable vector satisfy \(r_O+r_U+r_V\leq1\), or can a policy guarantee a vector whose sum exceeds \(1\)?
For discrete stochastic online matching, simultaneous worst-case competitive guarantees for profit and both fairness objectives cannot have sum exceeding \(1\); this is a competitive trade-off bound. [Source](https://arxiv.org/pdf/2201.06021v3).
No result settling these guarantees for the precise fluid model above was identified in the literature search.
I use the nonatomic fluid interpretation implicit in allowing arbitrary mass splitting: units retain identities, but there is no minimum positive mass that a policy must allocate.
For each of the four settings—group or individual fairness, with stationary or time-dependent arrivals—let $\mathcal A$ denote the achievable-ratio region, and define
$$
\mathcal S=\{r\in[0,1]^3:r_O+r_U+r_V\leq1\},
\qquad
\mathcal S_{<}=\{r\in[0,1]^3:r_O+r_U+r_V<1\}.
$$
The following conclusions are proved below:
The unrestricted boundary remains open in this write-up. In particular, computing an exact supremum does not prove that a schedule attains it.
The principal advance beyond the notes is the general benchmark LP and its finite approximation construction.
Fix any horizon $T\geq1$. Take one driver type $u$ with initial mass
$$
a_u=\frac14,
$$
and three request types $v_O,v_U,v_V$, with stationary masses
$$
b_{v_O}=\frac12,
\qquad
b_{v_U}=b_{v_V}=\frac14.
$$
Allow all three edges. Set every success probability and every patience limit to one. Give the edges utility triples
$$
(w^O,w^U,w^V)_{uv_O}=(1,0,0),
$$
$$
(w^O,w^U,w^V)_{uv_U}=(0,1,0),
$$
$$
(w^O,w^U,w^V)_{uv_V}=(0,0,1).
$$
For group fairness, use one group on each side. This is a valid binary-rational instance with support size $\tau=4$.
Write
$$
X_j=\sum_{t=1}^T x_{uv_j,t},
\qquad j\in\{O,U,V\}.
$$
Each successful match consumes driver mass, so every feasible schedule satisfies
$$
X_O+X_U+X_V\leq\frac14.
$$
Profit and driver fairness are
$$
O=X_O,
\qquad
F_U=4X_U.
$$
Matching all driver mass to the corresponding request type in the first period proves
$$
\operatorname{OPT}_O=\frac14,
\qquad
\operatorname{OPT}_U=1.
$$
Under request group fairness,
$$
F_V=\frac{X_V}{T},
\qquad
\operatorname{OPT}_V=\frac{1}{4T}.
$$
The optimum is attained by matching all driver mass to $v_V$ in the first period.
Under arrival-cohort fairness,
$$
F_V=\min_t x_{uv_V,t}.
$$
The driver budget gives
$$
T\min_t x_{uv_V,t}\leq X_V\leq\frac14.
$$
Matching mass $1/(4T)$ to $v_V$ in every period attains this bound: each period has $1/4$ such request mass, and total driver consumption is $1/4$. Thus here also
$$
\operatorname{OPT}_V=\frac{1}{4T}.
$$
All three benchmarks are positive.
For group fairness, therefore,
$$
\frac{O}{\operatorname{OPT}_O}
+\frac{F_U}{\operatorname{OPT}_U}
+\frac{F_V}{\operatorname{OPT}_V}
=4(X_O+X_U+X_V)\leq1.
$$
For individual and cohort fairness,
$$
\frac{O}{\operatorname{OPT}_O}
+\frac{F_U}{\operatorname{OPT}_U}
+\frac{F_V}{\operatorname{OPT}_V}
=4X_O+4X_U+4T\min_t x_{uv_V,t}
\leq1.
$$
Any family guaranteeing $r$ must satisfy its three guarantees on this instance. Adding them proves
$$
r_O+r_U+r_V\leq1.
$$
Because the instance is stationary, this obstruction applies to all four settings.
We next construct a polytope whose projection is the closure of the feasible successful-mass tensors.
A driver state is $(u,k)$ with $0\leq k<\Delta_u$, and a current-period request state is $(v,\ell)$ with $0\leq\ell<\Delta_v$.
Let
$$
q_{u,k,v,\ell,t}\geq0
$$
be the proposed probe mass between those states in period $t$, for $(u,v)\in E$. Put $f_{uv}=1-p_{uv}$, and define
$$
Q^D_{u,k,t}=\sum_{v,\ell}q_{u,k,v,\ell,t},
\qquad
H^D_{u,k,t}=\sum_{v,\ell}f_{uv}q_{u,k,v,\ell,t},
$$
$$
Q^R_{v,\ell,t}=\sum_{u,k}q_{u,k,v,\ell,t},
\qquad
H^R_{v,\ell,t}=\sum_{u,k}f_{uv}q_{u,k,v,\ell,t}.
$$
Let $s_{u,k,t}\geq0$ be driver mass at the beginning of period $t$, and let $h_{v,\ell,t}\geq0$ be request mass left immediately before the period ends. Impose
$$
s_{u,k,1}=a_u\mathbf 1_{\{k=0\}},
$$
$$
s_{u,k,t+1}
=s_{u,k,t}+H^D_{u,k-1,t}-Q^D_{u,k,t},
$$
$$
h_{v,\ell,t}
=b_{v,t}\mathbf 1_{\{\ell=0\}}
+H^R_{v,\ell-1,t}-Q^R_{v,\ell,t},
$$
where the terms indexed by $-1$ are zero.
Failures at the last permitted counter state depart, so they generate no subsequent state. The proposed success tensor is
$$
x_{uv,t}=p_{uv}\sum_{k,\ell}q_{u,k,v,\ell,t}.
$$
We impose zero variables for states that cannot be reached causally.
These states can be computed by a finite closure procedure. In period $t$, begin with the driver states reachable at the end of period $t-1$, and the states $(v,0)$ with $b_{v,t}>0$. Whenever both inputs of a probe are reachable and $f_{uv}>0$, add its surviving output states, if their counters remain below their patience limits. Repeat until no state is added. Carry the resulting driver states to period $t+1$.
The initial reachable driver states are precisely $(u,0)$.
For clarity, reachability here has a particularly simple interpretation. Let $c_u$ be the earliest period in which some incident edge $(u,v)$ has
$$
b_{v,t}>0,\qquad p_{uv}<1,
$$
or let $c_u=\infty$ if no such period exists. Then:
To verify the positive assertions, use sufficiently small probes while retaining positive mass in every previously reached state. Higher driver states can be generated successively using fresh state-zero requests; higher request states can be generated using fresh state-zero drivers. The negative assertions follow because a higher state requires an earlier failure involving that type.
Set $q_{u,k,v,\ell,t}=0$ whenever either input state is unreachable within period $t$. Also set beginning driver states and end request states to zero outside their corresponding reachable sets.
Call the resulting state-balance polytope $\mathcal P$.
Every feasible schedule supplies a point of $\mathcal P$: each probe removes its input mass from its current states, its failed fraction enters the next states, and its successful fraction departs. Requests have no carryover between periods. Voluntarily unused driver mass may be retained idle, without affecting successes.
The polytope is bounded. Indeed, request balances imply
$$
Q^R_{v,0,t}\leq b_{v,t},
$$
and, successively,
$$
Q^R_{v,\ell,t}
\leq H^R_{v,\ell-1,t}
\leq Q^R_{v,\ell-1,t}
\leq b_{v,t}.
$$
Writing $d_V=\max_v\Delta_v$, we obtain
$$
\sum_{u,k,v,\ell}q_{u,k,v,\ell,t}
\leq\sum_v b_{v,t}\Delta_v
\leq d_V.
$$
Summing driver balances over counter states shows that total retained driver mass never increases. Hence every $s_{u,k,t}$ is at most $a_u$. The request remainders are also bounded by their arrival masses.
Thus $\mathcal P$ is a nonempty compact rational polytope. Its projection onto $x$ is compact.
These facts alone do not prove exact executability of a point of $\mathcal P$. We now prove approximate executability.
Suppose two available nonatomic reservoirs, of equal mass $q>0$, are to be coupled. Each unit has previously probed only finitely many partners, because its patience is finite.
Identify each reservoir, up to null sets, with the circle $[0,q)$ equipped with Lebesgue measure. For a shift $c\in[0,q)$, pair coordinate $z$ in the first reservoir with coordinate $z+c$ modulo $q$ in the second.
For each fixed first-side unit, only finitely many shifts pair it with a previous partner. That set has measure zero. By Fubini’s theorem, for almost every shift, the mass of units paired with a previous partner is zero. Choose such a shift and discard any exceptional null set.
Consequently, any prescribed finite sequence of type-and-counter-state probe batches can be implemented without repeating a driver–request pair, provided sufficient masses are available at each batch. A measurable subset of coupled mass $p_{uv}q$ supplies the successful fraction, and the complement supplies the failed fraction.
Initially identical drivers can receive symmetric treatment: uniformly rotate the initial identity coordinates within each driver type before applying the construction. Every driver of that type then has the same treatment distribution. This relabeling preserves all mass totals and pair restrictions.
There exists a finite schedule $S^\circ$ such that, immediately before requests depart in each period, every state reachable within that period contains positive mass.
Construct it period by period. Whenever a probe can create an as-yet-unreached state, fire it on mass
$$
q=\frac12\min\{\text{its two input masses}\}.
$$
Both input states retain positive mass, and every surviving output has positive mass. Repeating this operation realizes the reachability closure. At the end of the period, retain all drivers and let requests depart.
Each such probe creates at least one new state. Define
$$
D_U=\sum_u\Delta_u,\qquad D_V=\sum_v\Delta_v,
\qquad K=T(D_U+D_V).
$$
The seed uses at most $K$ probe batches.
A quantitative buffer bound will be useful. Let
$$
h_*=\min\bigl(\{a_u:u\in U\}\cup
\{b_{v,t}:b_{v,t}>0\}\bigr),
$$
and let $f_*$ be the minimum positive $1-p_e$, setting $f_*=1$ if none exists. Every positive seed buffer is at least
$$
\mu_*=h_*\left(\frac{f_*}{2}\right)^K.
$$
This follows inductively: a seed probe retains at least half of each input mass, while a newly created state receives at least $f_*/2$ times the smaller input mass.
Because positive input rationals and positive $1-p_e$ are at least $2^{-L}$,
$$
\mu_*\geq2^{-(K+1)(L+1)}.
$$
Proposition. Let $(q,s,h)\in\mathcal P$, with success tensor $x$, and let $0<\varepsilon<1$. There is a finite causal schedule whose tensor is
$$
x^\varepsilon=(1-\varepsilon)x+\varepsilon x^\circ,
$$
where $x^\circ$ is the tensor of the seed schedule.
Fix an integer
$$
N\geq\frac{2d_V}{\varepsilon\mu_*}.
$$
We maintain the following driver-state masses at the beginning of each period:
$$
(1-\varepsilon)s_t+\varepsilon s^\circ_t.
$$
This holds initially because both schedules have the same initial masses.
First carve out driver submasses $\varepsilon s^\circ_t$ and request submasses $\varepsilon b_t$. Execute the scaled seed schedule for that period. Keep all other mass idle during this step.
Afterward, the driver and request states together have mass vector
$$
\varepsilon z^\circ_{\mathrm{end}}
+(1-\varepsilon)z_{\mathrm{start}},
$$
where $z_{\mathrm{start}}$ consists of the LP beginning driver states and fresh state-zero requests. The seed vector $z^\circ_{\mathrm{end}}$ has mass at least $\mu_*$ in every permitted probe-input state.
Next perform $N$ cycles. In every cycle, execute every proposed probe batch in any fixed order, on mass
$$
\frac{1-\varepsilon}{N}q_{u,k,v,\ell,t}.
$$
Let $C_tq_t$ denote the net state change of all proposed probes in this period, including departures. After $j$ complete cycles, the state vector is
$$
\varepsilon z^\circ_{\mathrm{end}}
+(1-\varepsilon)
\left(z_{\mathrm{start}}+\frac jN C_tq_t\right).
$$
The expression in parentheses is nonnegative: it is the convex combination
$$
\left(1-\frac jN\right)z_{\mathrm{start}}
+\frac jN z_{\mathrm{end}}
$$
of the LP beginning and ending state vectors.
Thus every permitted input state contains at least $\varepsilon\mu_*$ at the beginning of each cycle. During one cycle, the total mass consumed from any individual state is at most
$$
\frac{1-\varepsilon}{N}\sum_{u,k,v,\ell}q_{u,k,v,\ell,t}
\leq\frac{d_V}{N}
\leq\frac{\varepsilon\mu_*}{2}.
$$
Production during the cycle can only help availability. Every prescribed batch is therefore executable. Apply the pairing lemma to avoid previous partners.
At the end of the $N$ cycles, driver-state masses are exactly
$$
(1-\varepsilon)s_{t+1}+\varepsilon s^\circ_{t+1}.
$$
Carve these into the corresponding two portions for the next period. Requests depart.
The seed contributes $\varepsilon x^\circ$, and the cycles contribute $(1-\varepsilon)x$. This proves the asserted tensor.
Every batch uses currently available drivers and requests from the current period. Each unit obeys its actual counter history, and the pairing lemma prevents repeated pairs. Hence the schedule is causal and feasible. ∎
Every fairness objective in the question is the minimum of finitely many linear functions of $x$, using the original instance’s denominators. Write these functions as $\ell_{j,h}$. Profit is linear.
For nonnegative weights $\alpha_i$,
$$
\min_h\ell_{j,h}\left(\sum_i\alpha_i x^{(i)}\right)
\geq
\sum_i\alpha_i\min_h\ell_{j,h}(x^{(i)}).
$$
In particular, nonnegative utilities and the approximation proposition give
$$
F_j(x^\varepsilon)\geq(1-\varepsilon)F_j(x).
$$
Let $M_j$ be the maximum of objective $j$ over the projected polytope $\mathcal P$. Necessity gives
$$
\operatorname{OPT}_j\leq M_j.
$$
Apply the approximation proposition to an LP maximizer. For every $\varepsilon>0$,
$$
\operatorname{OPT}_j\geq(1-\varepsilon)M_j.
$$
Letting $\varepsilon$ decrease to zero proves
$$
\boxed{\operatorname{OPT}_j=M_j.}
$$
More generally, the proposition and necessity prove
$$
\boxed{
\overline{\{\text{feasible success tensors}\}}
=\operatorname{proj}_x\mathcal P.
}
$$
To optimize fairness, introduce $z\geq0$ and require every relevant linear utility to be at least its denominator times $z$. For example, driver group fairness uses
$$
\sum_{u\in U(g),v,t}w^U_{uv}x_{uv,t}
\geq z\sum_{u\in U(g)}a_u,
$$
request group fairness uses
$$
\sum_{v\in V(g),u,t}w^V_{uv}x_{uv,t}
\geq z\sum_{v\in V(g)}n_v,
$$
individual driver fairness uses
$$
\sum_{v,t}w^U_{uv}x_{uv,t}\geq za_u,
$$
and arrival-cohort fairness uses
$$
\sum_{u,v}w^V_{uv}x_{uv,t}\geq z
\qquad\text{for every }t.
$$
Maximize $z$ for the relevant benchmark.
The LP maxima exist by compactness and continuity. This proves attainment in the LP, not necessarily by a fluid schedule.
Set
$$
P=1+T\left(
\sum_{(u,v)\in E}\Delta_u\Delta_v+D_U+D_V
\right).
$$
Writing $d_U=\max_u\Delta_u$, we have
$$
P\leq1+T\bigl(md_Ud_V+\tau(d_U+d_V)\bigr).
$$
The LP has $O(P)$ variables and constraints. Its rational coefficient encoding length is polynomial in $P$ and $L+\log T$: coefficients consist of input masses, probabilities, products of probabilities and utilities, and fairness-denominator sums.
I use the following standard rational LP theorem: a rational linear program can be solved exactly in time polynomial in its binary encoding length; when an optimum exists, a rational optimal solution of polynomial encoding length can be returned. This is the exact polynomial-time LP result established by [Khachiyan](https://www.mathnet.ru/eng/zvmmf5239).
The hypotheses hold here: the data are rational, the feasible region is nonempty, and the relevant objectives have finite attained LP maxima. Therefore all three benchmark values and corresponding LP allocations are computable in
$$
\operatorname{poly}(P,L+\log T)
$$
bit operations.
For rational $\varepsilon$, choose
$$
N=
\left\lceil
\frac{2d_V\,2^{(K+1)(L+1)}}{\varepsilon}
\right\rceil.
$$
The construction uses at most $K+NP$ probe batches.
For completeness, the pairing step can also be implemented with finite rational data. Represent reservoirs as finite unions of identity intervals and use their ordered mass coordinates. Previous pairings are finite unions of graphs of translations. A new rotation can agree with an old pairing on positive mass only at one of finitely many rational shifts, obtained by comparing the interval pieces. Choose a rational shift outside that list.
Each probe introduces only a bounded number of new endpoints in the current state partitions: endpoints for the selected mass and its success fractions. With $B$ batches, these partitions have $O(B+\tau)$ intervals, and the recorded pairing graphs have polynomially many pieces. Candidate forbidden shifts can consequently be enumerated in polynomial time in $B$ and the rational encoding lengths. Choosing shifts as midpoints of rational gaps keeps those lengths polynomial in the number of batches and the original plan’s encoding length.
Thus a conservative bound for constructing and executing the finite approximation is
$$
\operatorname{poly}\bigl(P,N,L+\log T+\ell_\varepsilon\bigr),
$$
where $\ell_\varepsilon$ is the encoding length of $\varepsilon$.
This is an explicit, potentially exponential bound. The benchmark LP is polynomial in the numerical patience limits; no claim is made that it is polynomial in their binary encoding lengths alone.
Let $S_i$ be feasible schedules for the same instance, and let $\lambda_i\geq0$ satisfy $\sum_i\lambda_i\leq1$.
Split every initial driver-type mass and every arriving request-type mass into those proportions. Execute a scaled copy of $S_i$ within component $i$ and leave the remainder unused. Scaling preserves successes, failures, counter histories, and temporal restrictions. Components use disjoint units, so pair restrictions are preserved. Symmetric initial component assignment preserves the required driver symmetry.
The combined tensor is
$$
x=\sum_i\lambda_i x^{(i)}.
$$
Using the original denominators, linearity of profit and the minimum-of-linear-functions inequality give
$$
F_j(x)\geq\sum_i\lambda_i F_j(x^{(i)}).
$$
Fix a rational vector $r$ with
$$
s=r_O+r_U+r_V<1.
$$
Set
$$
\varepsilon=\frac{1-s}{2},
\qquad
\lambda_j=\frac{r_j}{1-\varepsilon}.
$$
Then
$$
\sum_j\lambda_j=\frac{2s}{1+s}<1.
$$
For each objective $j$, compute its LP maximizer and use Sections 5–7 to construct a feasible schedule $S_j$ satisfying
$$
F_j(S_j)\geq(1-\varepsilon)\operatorname{OPT}_j.
$$
Mix the three schedules with weights $\lambda_j$. Nonnegativity allows us to retain just the contribution from $S_j$, obtaining
$$
F_j\geq\lambda_jF_j(S_j)
\geq r_j\operatorname{OPT}_j.
$$
This is one causal policy family for the prescribed vector. It plans from the known input and executes only on current resources.
If $\ell_r$ is the ratio vector’s encoding length, a running-time bound is
$$
\operatorname{poly}\left(
P,\ L+\log T+\ell_r,\
\left\lceil
\frac{2d_V\,2^{(K+1)(L+1)}}{(1-s)/2}
\right\rceil
\right).
$$
Every real strict-interior vector is also achievable: choose a rational vector coordinatewise above it whose sum remains below one, and apply that rational vector’s policy.
Together with Section 2,
$$
\mathcal S_{<}\subseteq\mathcal A\subseteq\mathcal S,
\qquad
\overline{\mathcal A}=\mathcal S
$$
in all four settings.
Whenever all three separate benchmarks are attained by feasible schedules, mixing their optimizers with weights $r_O,r_U,r_V$ proves every vector in $\mathcal S$ achievable. The following classes have that property.
Suppose $p_e\in\{0,1\}$ for every edge.
A probability-zero probe never earns utility or removes a successful fraction. Omitting it leaves both units with no larger failure counts. Replaying all other probes on the same units therefore remains feasible: patience can only improve, and removing probes cannot introduce a repeated pair.
Thus probability-zero edges can be ignored. All remaining probes succeed immediately, and feasible success tensors are exactly those satisfying
$$
x_{uv,t}\geq0,
\qquad
\sum_{v,t}x_{uv,t}\leq a_u,
\qquad
\sum_u x_{uv,t}\leq b_{v,t},
$$
on probability-one edges.
Sufficiency follows by executing these allocations period by period. The total driver inequality leaves enough mass for each current allocation, and the request inequality leaves enough current request mass. Every allocated unit departs upon success.
This compact rational polytope has attained benchmark maxima. The three optimizations and their mixed schedule take
$$
\operatorname{poly}(T(m+\tau),L+\log T+\ell_r)
$$
time for rational $r$. Patience limits do not affect this bound.
Assume $\Delta_v=1$ for every request type. Use variables $q_{uv,k,t}$ and driver states $s_{u,k,t}$. The exact constraints are
$$
s_{u,k,t+1}
=s_{u,k,t}
+\sum_v(1-p_{uv})q_{uv,k-1,t}
-\sum_vq_{uv,k,t},
$$
with the initial states as before, together with
$$
\sum_{u,k}q_{uv,k,t}\leq b_{v,t}.
$$
Successes are
$$
x_{uv,t}=p_{uv}\sum_kq_{uv,k,t}.
$$
To execute any feasible point, reserve disjoint request submasses for all prescribed probes in a period. Process driver states in increasing $k$. Upon reaching state $k$, available mass is its beginning mass plus the failed mass just generated at $k-1$. The nonnegative end-state balance guarantees enough mass for all its prescribed probes.
Each request is probed once, so pair repetition is impossible. This proves exact executability and benchmark attainment.
The resulting running time is
$$
\operatorname{poly}(T(m+\tau)d_U,L+\log T+\ell_r).
$$
Assume $\Delta_u=1$ for every driver type. Every probed driver departs, whether the probe succeeds or fails.
Let $q_{uv,\ell,t}$ denote probes from request state $\ell$, and impose
$$
\sum_{v,\ell,t}q_{uv,\ell,t}\leq a_u,
$$
$$
h_{v,\ell,t}
=b_{v,t}\mathbf1_{\{\ell=0\}}
+\sum_u(1-p_{uv})q_{uv,\ell-1,t}
-\sum_uq_{uv,\ell,t}\geq0.
$$
Successes are
$$
x_{uv,t}=p_{uv}\sum_\ell q_{uv,\ell,t}.
$$
Reserve disjoint driver submasses for every prescribed probe over the entire horizon; the driver inequalities permit this. Within each period, process request counters in increasing order. The request balances guarantee sufficient mass at every state. Drivers are used once, so no pair can repeat.
Again every feasible LP point is executable, and benchmarks are attained. The running time is
$$
\operatorname{poly}(T(m+\tau)d_V,L+\log T+\ell_r).
$$
Each of these classes contains the obstruction of Section 2. Consequently, its achievable region is exactly $\mathcal S$, for both fairness definitions and both arrival models.
The general approximation construction needs a positive seed component. Setting $\varepsilon=0$ removes the buffer that justifies sequential execution. Neither the LP theorem nor the closure identity repairs that issue.
A small diagnostic illustrates the distinction. Take one driver and one request type, both with mass one and patience two, with one probability-zero edge. In one period, the state balances permit
$$
q_{0,1}=q_{1,0}=1,
\qquad
q_{0,0}=q_{1,1}=0.
$$
All final state masses are zero. Yet this exact probe allocation cannot start: initially neither counter-one state exists, and the allocation permits no counter-zero-to-counter-zero probe.
This diagnostic has zero benchmarks and is not an instance for the competitive obstruction. It also does not show nonattainment of a success optimum: its success tensor is zero and is trivially attainable. It shows only why exact execution of arbitrary balanced probe allocations cannot be assumed.
Thus the following distinction is essential:
⟨structured verdict parsed — rendered above⟩
Verdict: partial, with substantial valid progress. The output establishes the sum bound, strict-interior guarantees, and the closed simplex for the three restricted classes it identifies. Its general benchmark LP and approximation argument are sound in substance under the stated nonatomic interpretation, subject to minor formal and implementation clarifications.
It does not determine the entire achievable region for arbitrary probabilities and patience limits. The prover acknowledges this limitation. No central mathematical assertion has been refuted.
The task asks for the achievable vectors in all four settings:
The output establishes, in each setting,
$$
\mathcal S_{<}\subseteq\mathcal A\subseteq\mathcal S,
\qquad
\overline{\mathcal A}=\mathcal S.
$$
This answers the question about guarantees whose coordinates sum to more than $1$: they are impossible.
It leaves unresolved which vectors satisfying
$$
r_O+r_U+r_V=1
$$
are achievable in the unrestricted model. Knowing the closure of the achievable region does not determine membership on that face.
Issue — major, incomplete resolution of the assignment. The full characterization remains unfinished. This is an acknowledged limitation, not a concealed logical error.
Minimum additional work required: determine membership on the sum-one face in each unrestricted setting. Exact computation of benchmark suprema alone does not supply that determination.
The instance in Section 2 satisfies the input requirements:
Every successful match consumes driver mass, so
$$
X_O+X_U+X_V\leq\frac14
$$
is valid.
The profit and driver-fairness calculations are correct:
$$
O=X_O,\qquad F_U=4X_U,
$$
and the proposed first-period schedules attain
$$
\operatorname{OPT}_O=\frac14,\qquad
\operatorname{OPT}_U=1.
$$
For request group fairness, the single group has total arrival mass $T$. Thus
$$
F_V=\frac{X_V}{T},
\qquad
\operatorname{OPT}_V=\frac{1}{4T}.
$$
For arrival-cohort fairness, only the edge to $v_V$ contributes request utility, giving
$$
F_V=\min_t x_{uv_V,t}.
$$
The budget bound and the schedule allocating $1/(4T)$ in each period correctly establish the same benchmark.
The normalized-objective inequalities therefore hold as written. Adding the guarantees on this instance proves
$$
r_O+r_U+r_V\leq1.
$$
Since stationary instances are also time-dependent instances, and the single driver type makes the driver fairness definitions coincide here, the obstruction applies to all four settings.
Assessment: correct and complete.
The probe variables distinguish both failure counters. The balances correctly account for:
The success projection
$$
x_{uv,t}=p_{uv}\sum_{k,\ell}q_{u,k,v,\ell,t}
$$
is correct.
Retaining voluntarily unused driver mass idle preserves the success tensor, so voluntary rejection does not invalidate the necessary-condition argument.
The stated reachability description is valid under the nonatomic interpretation.
In particular, reaching a higher driver counter within a period does not require repeated use of the same request unit: the construction explicitly uses fresh state-zero requests. Likewise, higher request counters can use different driver units of the same type. Both are permitted by the task.
The distinction between reachability within period $t$ and at its beginning is correctly expressed by
$$
c_u\leq t
\quad\text{and}\quad
c_u<t,
$$
respectively.
The request balances imply
$$
Q^R_{v,\ell,t}\leq b_{v,t}
$$
for every permitted counter. Consequently,
$$
\sum_{u,k,v,\ell}q_{u,k,v,\ell,t}\leq d_V.
$$
The driver balances bound every state mass by its type’s initial mass. The request remainder bounds also follow from the displayed balances. Nonnegativity and linear equalities make the feasible set closed, and the idle allocation establishes nonemptiness.
Thus the state-balance feasible region is a compact rational polytope.
Assessment: correct. The output appropriately avoids claiming that conservation and reachability alone imply exact executability.
For a fixed first-side unit, each previous partner rules out at most one rotation shift. Finite patience therefore gives a finite forbidden set of shifts for that unit.
Provided the forbidden-pair relation is measurable, the stated Fubini argument correctly implies that almost every shift repeats partners only on a null set. Discarding that null set preserves the allocated mass.
Issue — minor, Section 4.1: the hypotheses needed for the measure-theoretic argument are not fully stated. Arbitrary nonatomic measure spaces need not admit the asserted identification with a Lebesgue circle, and finite forbidden fibers alone do not establish joint measurability.
This does not undermine the finite interval construction described later, where these properties are available.
Minimum clarification: state that reservoirs use standard Lebesgue identity spaces and that previous pairing maps are measurable. Explicitly identify the measurable forbidden relation to which Fubini is applied.
Uniform rotation of initial identity coordinates gives each initially identical driver the same treatment distribution. The relabeling preserves masses, counters, utilities, and pair restrictions.
Issue — minor, Sections 4.1, 7, and 8.1: the proof uses distributional symmetry through continuous random relabeling, whereas the computational discussion emphasizes finite rational data. The relationship between these two descriptions is not specified.
Minimum clarification: state the adopted meaning of symmetric treatment and explain whether the bit-operation bound constructs the rational mass plan together with a symbolic random relabeling rule. The mass guarantees survive every such relabeling; they need not be weakened to expected guarantees.
Each seed probe uses half the smaller input mass. Therefore both input reservoirs retain positive mass, and every surviving output receives positive mass when the failure probability is positive.
Each probe adds at least one previously absent state, so
$$
K=T(D_U+D_V)
$$
is a valid upper bound on the number of batches.
The buffer estimate
$$
\mu_*=h_*\left(\frac{f_*}{2}\right)^K
$$
is valid. The binary-length estimate is also conservative and correct:
$$
\mu_*\geq2^{-(K+1)(L+1)}.
$$
The convention $f_*=1$ when no positive failure probability exists causes no problem: no failure-generated state then requires seeding.
Assessment: correct, subject to the pairing clarification above.
The induction starts correctly because the LP allocation and seed schedule have the same initial driver masses.
After executing the scaled seed, every permitted probe-input state has a buffer of at least
$$
\varepsilon\mu_*.
$$
At complete-cycle boundaries, the non-seed portion is the displayed convex combination of the LP beginning and ending state vectors. Both are nonnegative, so the cycle-boundary calculation is valid even when the LP allocation contains cyclic dependencies.
The within-cycle consumption bound is correct:
$$
\frac{1-\varepsilon}{N}\sum q_{u,k,v,\ell,t}
\leq\frac{d_V}{N}
\leq\frac{\varepsilon\mu_*}{2}.
$$
It bounds all consumption from any one state during that cycle. Thus no prescribed batch exhausts its available input reservoir.
The final driver-state identity is correct and supports the next-period induction. The seed and cycle contributions give exactly
$$
x^\varepsilon=(1-\varepsilon)x+\varepsilon x^\circ.
$$
All probes occur within the appropriate arrival period, counters track actual failures, and the pairing lemma supplies the no-repeat restriction.
Assessment: sound. This is a substantive approximation result, not an assumption of exact LP executability.
Each fairness objective is a minimum of finitely many linear functions of the success tensor. All denominators are positive under the task’s assumptions.
The inequality
$$
\min_h\ell_{j,h}\left(\sum_i\alpha_i x^{(i)}\right)
\geq
\sum_i\alpha_i\min_h\ell_{j,h}(x^{(i)})
$$
is valid for nonnegative coefficients.
Nonnegative utilities therefore imply
$$
F_j(x^\varepsilon)\geq(1-\varepsilon)F_j(x).
$$
Necessity gives the upper bound by the LP maximum. Approximating an LP maximizer gives the matching supremum lower bound. Hence
$$
\operatorname{OPT}_j=M_j
$$
follows correctly.
The closure identity also follows: necessity puts feasible tensors inside the compact projection, while the approximation proposition approaches every point in that projection.
The fairness LP inequalities use the correct group, individual, and cohort denominators.
Assessment: correct, subject to the minor feasibility formalization above. The output correctly distinguishes an attained LP optimum from an attained schedule optimum.
The parameter
$$
P=1+T\left(
\sum_{(u,v)\in E}\Delta_u\Delta_v+D_U+D_V
\right)
$$
correctly bounds the numbers of state and probe variables and constraints. The stated bound in terms of $m$, $\tau$, and maximum patience limits is valid.
The LP data are rational and have polynomial encoding length in the stated parameters. The exact rational LP theorem is accurately stated, and its required hypotheses are satisfied here: feasibility, rational data, and finite attained LP optima. The cited [Khachiyan paper](https://www.mathnet.ru/eng/zvmmf5239) supports polynomial-time linear programming in binary input length.
The explicit choice of $N$ is sufficient because it uses an upper bound on $1/\mu_*$. The batch-count estimate is conservative. The output correctly qualifies polynomial dependence on the numerical patience limits.
Issue — minor, Section 7: the finite rational pairing implementation is compressed. In particular, the asserted endpoint and encoding-length bounds are not accompanied by an explicit update invariant. Choosing rational midpoints, by itself, does not explain the cumulative denominator bound.
Minimum clarification: specify how probe inputs and successful fractions are selected in ordered reservoir coordinates, and state the maintained bounds on interval endpoints, pairing pieces, and rational encoding lengths. These are implementation details of the existing construction; no change to the approximation argument is indicated.
Subject to that clarification, the claimed potentially exponential construction bound is credible. The benchmark LP bound itself does not depend on this implementation detail.
Splitting both initial driver masses and every arrival mass into common proportions permits disjoint scaled copies of feasible schedules. The temporal restrictions and counter histories remain valid within each copy.
Using the original fairness denominators is essential, and the output does so correctly.
For
$$
s=r_O+r_U+r_V<1,
$$
the choices
$$
\varepsilon=\frac{1-s}{2},
\qquad
\lambda_j=\frac{r_j}{1-\varepsilon}
$$
satisfy
$$
\sum_j\lambda_j=\frac{2s}{1+s}<1.
$$
Combining the three approximations then gives every required guarantee. Nonnegative cross-objective contributions justify keeping only the designated component’s contribution.
The extension to real strict-interior vectors by rational coordinatewise domination is valid. It is an existence argument and does not assert finite input encoding for arbitrary real vectors.
Assessment: correct, subject to the minor construction clarifications.
Omitting probability-zero probes cannot increase failure counts or create repeated pairs. The remaining probability-one probes succeed immediately.
The displayed transportation constraints are necessary and sufficient, and their feasible region is compact. Benchmark attainment and simplex achievability follow.
Disjoint request reservations ensure that each request is probed at most once. Processing driver counters in increasing order respects the failure transitions. The nonnegative balances guarantee sufficient driver mass at each counter.
Disjoint driver reservations over the entire horizon are justified by the total driver inequalities. Processing request counters in increasing order respects the request transitions. Every driver is used at most once.
The stated runtime bounds correctly reflect the remaining counter dimension.
Assessment: all three restricted-class conclusions are valid. Each class contains the obstruction, so its achievable region is exactly $\mathcal S$.
The diagnostic allocation satisfies the state balances: each counter-one input is supplied algebraically by the other proposed probe. It cannot be executed exactly from the initial state because neither proposed batch has both inputs available.
The output correctly limits the example’s significance. Its success tensor is zero and attainable, so it does not establish nonattainment of a benchmark or exclude any competitive vector.
The final distinction between exact supremum values and actual benchmark attainment is therefore appropriate.
The genuine established content is the sum bound, the general closure and approximation characterization, strict-interior achievability, and the three restricted boundary results. The unresolved sum-one face prevents a complete answer to the original task.
⟨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.