Answer: A universal deterministic family, truthful on every finite individual-edge report profile, achieves $\alpha=e/(e-1)<2$ with a template-dependent constant additive loss at all sufficiently large admissible scales. Hence $\alpha_*\leq e/(e-1)<2$, settling the stated dichotomy.
Theorem 3 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateThere does not exist a truthful and deterministic mech- anism for the MVbM problem that achieves an approximation ratio better than 2.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finite task classes \(J\), worker types \(\Theta\) with eligible sets \(N_\theta\subseteq J\) and capacities \(b_\theta\), rational masses \(\mu_\theta\), per-capita task supplies \(s_j\), and task values \(q_j\), let \(I_n\) be the integral realization with \(n\mu_\theta\) workers of type \(\theta\) and \(ns_j\) tasks of class \(j\). Determine the least \(\alpha\) for which a deterministic mechanism family \(M_n\), individually truthful against edge hiding at every scale, guarantees \(W(M_n(I_n))\geq \mathrm{OPT}(I_n)/\alpha-o(n)\) across fixed-support templates; does the paper's \(2\)-barrier persist?
A society is specified by its support: \(\tau\) distinct worker types \(\theta=(N_\theta,b_\theta)\) with positive binary-rational masses \(\mu_\theta\), where \(\sum_\theta\mu_\theta=1\). Here \(\tau\) is the support size, not the number of possible types. There are \(m=|J|\geq1\) task classes, with \(\varnothing\neq N_\theta\subseteq J\), public capacities \(b_\theta\in\mathbb Z_{>0}\), and public binary-rational supplies \(s_j>0\) and common values \(q_j>0\). Let \(L\) be the template's total encoding length; express running times in \(m,\tau,L,n\) and the expanded input/output size.
For every positive integer \(n\) making all \(n\mu_\theta\) and \(ns_j\) integral, \(I_n\) has \(n\mu_\theta\) labeled workers of type \(\theta\) and \(ns_j\) distinct tasks of class \(j\). Each such worker is eligible for every copy of every class in \(N_\theta\). An allocation assigns each task at most once and at most \(b_\theta\) tasks to each worker. Worker utility is the sum of assigned task values; welfare \(W\) is total utility, and \(\mathrm{OPT}(I_n)\) is maximum feasible welfare.
A single deterministic mechanism family \((M_n)\), without payments or computational restrictions, operates on individual edge reports and public data, without access to true eligibility sets or their masses. Reports may be any nonempty subset of a worker's eligible task copies, including subsets that split a class. Each \(M_n\) must be truthful on every finite report profile: hiding edges cannot increase that worker's utility, whatever the other reports. Outputs must respect reported edges and public capacities; deterministic choices may use labels, and guarantees must hold for every labeling.
Let \(\alpha_*\) be the infimum of constants \(\alpha\geq1\) for which such a family satisfies, on truthful reports, \(W(M_n(I_n))\geq\mathrm{OPT}(I_n)/\alpha-r_H(n)\) for every fixed template \(H\), with \(r_H(n)\geq0\) and \(r_H(n)/n\to0\) along its admissible scales. The family and constant are universal; the remainder may depend on the template.
What is \(\alpha_*\): does \(\alpha_*=2\), or can a deterministic family truthful at every scale achieve a constant \(\alpha<2\) with this vanishing per-capita loss?
For arbitrary finite instances, deterministic truthful mechanisms cannot achieve an approximation factor below \(2\), and a deterministic truthful mechanism achieves \(2\); the [extended treatment](https://arxiv.org/html/2310.11908v1) retains both results. No result settling this exact fixed-support asymptotic formulation was located.
The second alternative holds. There is a universal deterministic mechanism family, truthful on every finite report profile, that achieves
$$
\alpha=\frac{e}{e-1}<2
$$
with a template-dependent constant additive loss at all sufficiently large admissible scales. Consequently,
$$
\boxed{\alpha_*\leq\frac{e}{e-1}<2.}
$$
This settles the proposed dichotomy. The exact value of $\alpha_*$ remains undetermined.
The construction has very large running time. Its key feature is that each worker receives a menu determined entirely by the other workers’ reports. We select these menus jointly so that their outputs are feasible on every report profile.
Fix public data consisting of $n$ labeled workers, capacities $b_i$, and task classes $J$, with $T_j$ task copies of class $j$ and value $q_j>0$.
Fix a public task order that sorts tasks by decreasing value and resolves ties deterministically. For a worker permutation $\pi$, let $\mathrm{SD}_\pi$ process workers in that order, giving each worker its highest-valued available reported tasks, up to its capacity.
We use the following established theorem.
Ranking theorem. In online bipartite matching with arbitrary positive integer capacities on the offline vertices, choose a uniformly random permutation of those vertices. Match each arriving online vertex to its first eligible vertex in that permutation with remaining capacity. For every fixed graph and arrival order, the expected matching cardinality is at least $1-1/e$ times the maximum feasible cardinality. This is [Theorem 3 of Albers and Schubert, *Optimal Algorithms for Online b-Matching with Variable Vertex Capacities*](https://link.springer.com/article/10.1007/s00453-024-01282-9).
Here the offline vertices are workers and the arriving vertices are tasks. Thus all hypotheses, including variable worker capacities, hold.
Write
$$
c=1-\frac1e.
$$
Lemma 1. For every finite report profile $P$,
$$
\mathbb E_\pi W(\mathrm{SD}_\pi(P))\geq c\,\mathrm{OPT}(P).
$$
Proof. Processing tasks in the fixed task order and assigning each to its first available eligible worker in $\pi$ produces the same allocation as $\mathrm{SD}_\pi$.
To verify this, the first worker in $\pi$ receives exactly its first $b_i$ eligible tasks in the task order, or all its eligible tasks if fewer exist. These are precisely its serial-dictatorship choices. Remove that worker and those tasks; induction proves the assertion for the remaining workers.
Let the distinct task values be
$$
v_1>\cdots>v_d>0,
\qquad v_{d+1}=0.
$$
For an allocation $A$, let $C_h(A)$ count its assigned tasks having value at least $v_h$. Then
$$
W(A)=\sum_{h=1}^d(v_h-v_{h+1})C_h(A).
$$
Let $M_h$ be the maximum feasible cardinality using only tasks of value at least $v_h$. The task-order algorithm’s decisions on this prefix do not depend on later tasks. Applying the Ranking theorem to each prefix gives
$$
\mathbb E_\pi C_h(\mathrm{SD}_\pi(P))\geq cM_h.
$$
If $O$ is a welfare-optimal allocation, then $C_h(O)\leq M_h$. Therefore
$$
\begin{aligned}
\mathbb E_\pi W(\mathrm{SD}_\pi(P))
&\geq c\sum_{h=1}^d(v_h-v_{h+1})M_h\\
&\geq c\sum_{h=1}^d(v_h-v_{h+1})C_h(O)\\
&=c\,\mathrm{OPT}(P).
\end{aligned}
$$
This proves the lemma. $\square$
The randomized benchmark is used only to construct a rational fractional solution. The eventual mechanism makes no random choices.
We need to round choices while controlling many constraints simultaneously.
Lemma 2. Partition finitely many variables into groups. Suppose $x_k\in[0,1]$ and
$$
\sum_{k\in G}x_k=1
$$
for every group $G$. Let $A=(a_{\ell k})$ be a finite rational matrix satisfying
$$
\sum_\ell |a_{\ell k}|\leq\Delta
$$
for every column $k$, where $\Delta>0$.
There is a deterministically computable vector $y_k\in\{0,1\}$ satisfying
$$
\sum_{k\in G}y_k=1
$$
for every group and
$$
\left|\sum_k a_{\ell k}(y_k-x_k)\right|\leq2\Delta
$$
for every row $\ell$.
Proof. Keep variables already equal to $0$ or $1$ fixed. Let $F$ be the remaining fractional variables.
Preserve every group-sum equation. Retain a numerical row equation only while
$$
\sum_{k\in F}|a_{\ell k}|>2\Delta;
$$
otherwise discard that row equation permanently.
Every group containing fractional variables contains at least two of them: its fractional variables sum to $1$, because any fixed variables in that group are $0$. Hence there are at most $|F|/2$ relevant group equations.
The number of retained numerical equations is strictly less than $|F|/2$, since
$$
\sum_{\ell\text{ retained}}\sum_{k\in F}|a_{\ell k}|
\leq |F|\Delta.
$$
Thus fewer than $|F|$ equations constrain the $|F|$ fractional variables. A nonzero nullspace direction exists. Move along a deterministically selected rational direction until a variable reaches $0$ or $1$.
Repeat. At least one variable becomes integral per iteration, so the process terminates. Group sums remain exactly $1$.
A retained row has zero error. When a row is discarded, its current value still equals its initial value, and its remaining coefficient sum is at most $2\Delta$. Subsequent changes in each remaining variable have absolute value at most $1$. Its final error is therefore at most $2\Delta$. $\square$
This proof also gives a finite rational algorithm.
First work on the finite domain
$$
\mathcal X=(2^J)^n.
$$
A coordinate $P_i\subseteq J$ means that worker $i$ reports every copy of exactly those classes. We allow $P_i=\varnothing$ internally.
Public capacities remain fixed throughout this domain.
For $n\geq16$, put
$$
h(n)=\lfloor n^{1/4}\rfloor.
$$
For $P\in\mathcal X$, define its report-type counts
$$
a_{B,b}(P)
=
|\{i:P_i=B,\ b_i=b\}|.
$$
Define their common reduced denominator by
$$
d(P)=
\frac{n}{\gcd\{a_{B,b}(P):(B,b)\}},
$$
where zero counts can be omitted from the gcd.
Call $P$ a centre if
$$
d(P)\leq h(n).
$$
For $n<16$, take the centre set to be empty.
This definition uses only hypothetical report profiles and public capacities. It does not use true eligibility sets or masses.
Lemma 3. For a fixed worker $i$ and fixed reports $R$ of all other workers, at most one report $B$ completes $(B,R)$ to a centre.
Proof. Each coordinate of a centre’s normalized count vector is a rational number whose denominator is at most $h(n)$. Two distinct such rationals differ by at least $1/h(n)^2$.
Consequently, distinct centre count vectors differ in some unnormalized coordinate by at least
$$
\frac{n}{h(n)^2}\geq\sqrt n\geq4.
$$
Changing one worker’s report changes every count coordinate by at most $1$. Thus two centres agreeing on all other workers must have the same count vector. That vector, together with the other workers’ reports and worker $i$’s public capacity, determines $i$’s report uniquely. $\square$
A context is a pair
$$
a=(i,R)
$$
for which some centre $P$ satisfies $P_{-i}=R$. By Lemma 3, that centre is unique; denote it by $P^a$.
Crucially, whether worker $i$ has a context depends only on the other workers’ reports.
For each context $a=(i,R)$ and worker permutation $\pi$, construct a menu
$$
F_a^\pi:2^J\longrightarrow\mathbb Z_{\geq0}^{J}.
$$
Run serial dictatorship on the workers preceding $i$ in $\pi$, using their reports from $R$. Let $t_j$ be the number of class-$j$ copies remaining before $i$ is processed.
For a report $B\subseteq J$, the vector $F_a^\pi(B)$ specifies the highest-valued bundle available from these remaining copies in classes $B$, up to capacity $b_i$, using the fixed task order.
Also include the zero menu
$$
F_a^0(B)=0.
$$
Every menu respects the reporting worker’s classes and capacity. Its utility is monotone under inclusion:
$$
B'\subseteq B
\quad\Longrightarrow\quad
\sum_jq_jF_a^\pi(B')_j
\leq
\sum_jq_jF_a^\pi(B)_j.
$$
Indeed, the remaining supply vector is fixed independently of $B$, and passing from $B$ to $B'$ restricts the available bundles.
The following identity provides the joint feasibility needed below.
Lemma 4. If $Q_{-i}=R$, then
$$
F_a^\pi(Q_i)
=
\text{the class-count vector assigned to }i
\text{ by }\mathrm{SD}_\pi(Q).
$$
Proof. Every worker preceding $i$ has the same report in the menu calculation and in $Q$. Their decisions are independent of $i$’s report. Thus the remaining supply before $i$ is identical, and the two calculations make the same choice for $i$. $\square$
Let
$$
T=\sum_jT_j,
\qquad
B_{\max}=\max_i\min\{b_i,T\},
\qquad
q_{\max}=\max_jq_j.
$$
Set
$$
\Delta=(2^m+1)B_{\max},
\qquad
T_{\min}=\min_jT_j,
\qquad
\varepsilon=\min\left\{1,\frac{2\Delta}{T_{\min}}\right\}.
$$
If there are no centres, or if $\varepsilon=1$, select the zero menu in every context. Otherwise proceed as follows.
For every context $a$, create one group of choice variables indexed by the zero menu and all $n!$ permutations. Initially set
$$
x_{a,0}=\varepsilon,
\qquad
x_{a,\pi}=\frac{1-\varepsilon}{n!}.
$$
Define a rational matrix with the following rows.
For every $Q\in\mathcal X$ and $j\in J$, include the expression
$$
D_{Q,j}(x)
=
\sum_{\substack{a=(i,R)\\R=Q_{-i}}}
\sum_\pi x_{a,\pi}F_a^\pi(Q_i)_j.
$$
Zero-menu contributions vanish. By Lemma 3, at most one context contributes for each worker.
For a fixed $\pi$, Lemma 4 identifies these menu outputs with a subset of the workers’ outputs in $\mathrm{SD}_\pi(Q)$. Hence
$$
D_{Q,j}(x)\leq(1-\varepsilon)T_j.
$$
For every centre $P$, include
$$
U_P(x)
=
\sum_i\sum_\pi
x_{(i,P_{-i}),\pi}
\frac{\sum_jq_jF_{(i,P_{-i})}^\pi(P_i)_j}{q_{\max}}.
$$
Every worker has a context at a centre. Lemma 4 therefore gives
$$
U_P(x)
=
\frac{1-\varepsilon}{q_{\max}}
\mathbb E_\pi W(\mathrm{SD}_\pi(P)).
$$
Fix a column corresponding to one menu in context $a=(i,R)$.
It contributes to task-supply rows only for profiles with $Q_{-i}=R$. There are exactly $2^m$ such profiles. At each, its total contribution over all classes is at most $B_{\max}$.
It contributes to exactly one welfare row, that of $P^a$, with coefficient at most $B_{\max}$.
Thus its total absolute coefficient sum is at most
$$
2^mB_{\max}+B_{\max}=\Delta.
$$
Apply Lemma 2, fixing all choices deterministically using public label orders. This selects one menu $F_a$ per context.
For every profile $Q$ and class $j$, the selected menus demand at most
$$
(1-\varepsilon)T_j+2\Delta\leq T_j,
$$
because $\varepsilon T_j\geq2\Delta$.
For every centre $P$, their welfare satisfies
$$
W(P)\geq
(1-\varepsilon)\mathbb E_\pi W(\mathrm{SD}_\pi(P))
-2\Delta q_{\max}.
$$
When $\varepsilon=1$, selecting all zero menus satisfies this last inequality as well. We have therefore proved:
Lemma 5. The selected menus are jointly feasible on every profile in $\mathcal X$, and every centre satisfies
$$
W(P)\geq(1-\varepsilon)c\,\mathrm{OPT}(P)-2\Delta q_{\max}.
$$
All menu selections depend only on public data. They are computed before evaluating the actual reports.
We now define the mechanism on arbitrary individual-edge reports.
For a worker report $S_i$ of task copies, let
$$
B_i(S_i)
=
\{j:\text{every copy of class }j\text{ belongs to }S_i\}.
$$
This projection may be empty even when $S_i$ is nonempty. It satisfies
$$
S_i'\subseteq S_i
\quad\Longrightarrow\quad
B_i(S_i')\subseteq B_i(S_i).
$$
Given actual reports, form their projected profile $Q\in\mathcal X$.
For each worker $i$:
Lemma 5 ensures that the total requested number of class-$j$ copies is at most $T_j$. Assign distinct copies to fulfill all requested counts, using fixed public worker and task orders.
Every assigned copy belongs to a class whose entire set of copies was reported by its recipient. Thus assignments respect reported edges. Menus respect individual capacities.
Proposition 6. This mechanism is truthful on every finite report profile, including reports that split classes.
Proof. Fix worker $i$ and all other individual-edge reports. Their projected reports, and therefore $Q_{-i}$, are fixed.
If $(i,Q_{-i})$ is not a context, worker $i$ receives zero utility under every report.
If it is a context, worker $i$ faces one fixed selected menu $F_{(i,Q_{-i})}$. Hiding edges can only shrink its projected class set. Every selected menu has utility monotone under this inclusion.
Assigning particular copies does not change utility, because values are common within each class. Hence hiding edges cannot increase worker $i$’s utility. $\square$
The zero mechanisms used at small scales are also truthful. This defines a single universal deterministic family.
Fix any template $H$ from the question. Write
$$
b_H=\max_\theta b_\theta,
\qquad
s_{\min}=\min_js_j,
\qquad
S_q=\sum_js_jq_j,
\qquad
\Delta_H=(2^m+1)b_H.
$$
Choose a positive integer $D$ such that every $D\mu_\theta$ is integral.
At any admissible scale, the truthful normalized report-type count vector is exactly the template mass vector, regardless of labeling. Its reduced denominator is at most $D$. Therefore every truthful labeling is a centre once
$$
n\geq N_H:=\max\{16,D^4\}.
$$
At such a scale,
$$
T_{\min}=ns_{\min},
\qquad
\Delta\leq\Delta_H,
\qquad
\varepsilon\leq\frac{2\Delta_H}{ns_{\min}}.
$$
Also,
$$
\mathrm{OPT}(I_n)\leq nS_q,
$$
because $nS_q$ is the total value of all supplied tasks.
Lemma 5 gives, for every labeling,
$$
\begin{aligned}
W(M_n(I_n))
&\geq c\,\mathrm{OPT}(I_n)
-\varepsilon c\,\mathrm{OPT}(I_n)
-2\Delta q_{\max}\\
&\geq c\,\mathrm{OPT}(I_n)-C_H,
\end{aligned}
$$
where the finite template-dependent constant is
$$
C_H=
\frac{2c\Delta_HS_q}{s_{\min}}
+2\Delta_Hq_{\max}.
$$
For example, define the remainder on admissible scales by
$$
r_H(n)
=
C_H+c\,nS_q\,\mathbf 1_{\{n<N_H\}}.
$$
For small scales, nonnegative welfare and $\mathrm{OPT}(I_n)\leq nS_q$ establish the required guarantee. For all larger scales, the preceding constant-loss bound establishes it.
Finally,
$$
\frac{r_H(n)}n\longrightarrow0,
$$
and $c=1/\alpha$ for $\alpha=e/(e-1)$.
This proves the claimed universal asymptotic factor below $2$.
Let $\mathcal B_{\mathrm{exp}}$ be the expanded input/output bit size. The mechanism has no computational restriction, but the construction is a finite algorithm.
There are at most
$$
2^{mn}
$$
projected profiles and at most
$$
n2^{mn}
$$
contexts. Each context has at most $n!+1$ menu alternatives. The rounding system has at most
$$
V=n2^{mn}(n!+1)
$$
variables, together with at most $(m+1)2^{mn}$ numerical rows and one group equation per context.
Each menu can be evaluated on all $2^m$ class reports using class supply counts. Exact averages use rational probabilities with denominator $n!$. The rounding algorithm uses at most $V$ iterations of rational linear algebra; its coefficient encodings and intermediate rational encodings have polynomial size in the explicitly constructed system.
A coarse bit-running-time bound on template-derived public data is consequently
$$
2^{O(mn+n\log(n+1))}
\operatorname{poly}(L+\mathcal B_{\mathrm{exp}}).
$$
The mechanism does not receive $\tau$ or the masses. Thus this bound has no additional dependence on $\tau$ beyond the template encoding and expanded instance.
On truthful reports,
$$
T=n\sum_js_j,
$$
$$
E=
n^2\sum_\theta\mu_\theta
\sum_{j\in N_\theta}s_j,
$$
and the output contains at most
$$
K\leq
\min\left\{
T,\ n\sum_\theta\mu_\theta b_\theta
\right\}
$$
assignments. Reading reports and producing labeled assignments additionally takes polynomial time in the expanded input/output size.
The proof establishes the complete existence claim requested in the second alternative. Determining the exact infimum requires further work.
⟨structured verdict parsed — rendered above⟩
The argument establishes the claimed asymptotic factor
$$
\alpha=\frac{e}{e-1}<2,
$$
subject to two minor computational specification gaps. I found no false central step or missing mathematical lemma affecting the existence, feasibility, truthfulness, or asymptotic welfare guarantee.
The exact value of $\alpha_*$ remains undetermined, as the prover acknowledges. The output nevertheless resolves the task’s stated dichotomy by establishing a qualifying constant below $2$.
The cited theorem is applicable. Theorem 3 of Albers and Schubert states that Ranking achieves expected cardinality at least $1-1/e$ times optimum for online bipartite matching with variable server capacities. Its algorithm ranks servers uniformly at random and assigns each arriving request to its highest-ranked eligible server with remaining capacity. This matches the stated worker–task interpretation. [Published theorem](https://link.springer.com/article/10.1007/s00453-024-01282-9)
The hypotheses hold:
The equivalence with serial dictatorship is correct. The first worker in the permutation receives precisely its first eligible tasks in the fixed task order, up to capacity. Removing that worker and those tasks leaves the same procedure for the remaining workers. The induction establishes equality of allocations, including deterministic tie choices.
The weighted extension in Lemma 1 is correct. The identity
$$
W(A)=\sum_{h=1}^{d}(v_h-v_{h+1})C_h(A)
$$
counts each assigned task’s value exactly. Decisions on a task-order prefix are unaffected by later tasks, so the cardinality theorem applies separately to every prefix. The comparison
$$
C_h(O)\leq M_h
$$
holds because restricting an optimal allocation to that prefix yields a feasible allocation there. All differences $v_h-v_{h+1}$ are positive, so the inequalities can be summed as written.
Conclusion: Lemma 1 is verified.
The dimension argument is correct.
A group containing fractional variables cannot contain a variable fixed at $1$, and its fractional entries sum to $1$. Consequently, it contains at least two fractional variables, giving at most $|F|/2$ relevant group equations.
Every retained numerical row has remaining absolute coefficient sum strictly greater than $2\Delta$. The column bound therefore implies that there are strictly fewer than $|F|/2$ retained numerical equations. Together, the constraints number strictly fewer than $|F|$, so a nonzero nullspace direction exists.
Moving to a boundary preserves the retained equations and group sums while making at least one additional variable integral. The process terminates.
The discrepancy calculation is also correct: until a row is discarded, its value equals its initial value; afterward, only variables fractional at discard can change, and their total absolute coefficient sum is at most $2\Delta$.
Minor issue: The lemma permits arbitrary real $x_k$ but claims a finite rational algorithm. Its application uses rational $x_k$, so the mechanism’s construction is unaffected.
Minimum clarification: Restrict the algorithmic statement to rationally encoded $x_k$ and $\Delta$, or specify the computational representation intended for real inputs.
The denominator definition is well-defined because the nonnegative counts sum to the positive integer $n$.
For a centre, every normalized count has reduced denominator at most $h(n)$. Distinct rationals with such denominators differ by at least $1/h(n)^2$. Hence distinct centre count vectors differ in some unnormalized coordinate by at least
$$
\frac{n}{h(n)^2}\geq\sqrt n\geq4
$$
for the stipulated range $n\geq16$.
Changing only one worker’s report changes each count coordinate by at most $1$. Thus two centres with the same other-worker reports cannot have distinct count vectors. Given those other reports and the worker’s public capacity, the remaining count vector determines the worker’s class report uniquely.
This verifies both Lemma 3 and the uniqueness of $P^a$.
Conclusion: Context existence depends only on other-worker reports, as required.
For a fixed context and permutation, preceding workers’ choices depend only on their reports and public data. The remaining supplies are therefore independent of the reporting worker’s own class report.
Restricting that report restricts the available bundles. Since the menu chooses a highest-valued bundle subject to the same capacity, its utility is monotone under inclusion. The zero menu also has this property.
Lemma 4 follows directly from the identical preceding-worker computation in the menu construction and serial dictatorship.
Conclusion: The menu construction and its monotonicity are verified.
Initial supply feasibility is correct. For a fixed permutation, all contexts contributing at a profile correspond to outputs of that same serial dictatorship allocation. They form a subset of its worker outputs. Averaging with weight $1-\varepsilon$ gives
$$
D_{Q,j}(x)\leq(1-\varepsilon)T_j.
$$
The welfare identity is correct. Every worker has a context at a centre, so summing its menu outputs recovers the complete serial dictatorship welfare before averaging.
The column bound is correct. A context column occurs in supply rows for exactly $2^m$ profiles, and its total contribution across classes at each such profile is at most $B_{\max}$. Context uniqueness permits its occurrence in only one welfare row. Normalization by $q_{\max}$ bounds that welfare coefficient by $B_{\max}$.
Thus the stated bound
$$
\Delta=(2^m+1)B_{\max}
$$
holds.
Rounding preserves supply feasibility. In the nonzero branch, $\varepsilon<1$, so
$$
\varepsilon=\frac{2\Delta}{T_{\min}}
$$
and consequently $\varepsilon T_j\geq2\Delta$ for every class. The rounding error is covered by the reserved supply.
The welfare discrepancy is at most $2\Delta q_{\max}$ after undoing normalization. Combining this with Lemma 1 proves Lemma 5.
The exceptional branches are handled correctly:
Conclusion: Lemma 5 is verified.
The projection to fully reported classes is monotone under edge deletion, including deletion that leaves only a proper subset of a class.
For fixed other-worker reports, their projections remain fixed. Thus the reporting worker either always receives zero or always faces one fixed selected menu. Its utility cannot increase when its projected class set shrinks.
The final assignment of labeled copies fulfills all requested counts because the supply constraints hold at every projected profile. Every recipient reported every copy of each requested class, so these assignments respect reported edges. Copy selection does not affect utility because class values are common.
This argument covers arbitrary other-worker reports and reports that split classes. It does not rely on a truthful profile or on access to true eligibility.
Conclusion: Proposition 6 establishes the required finite-profile truthfulness.
The truthful count coordinates are indexed by the same pairs $(N_\theta,b_\theta)$ that define the distinct template types. Their normalized counts are the fixed masses $\mu_\theta$, independently of labeling.
Choosing $D$ with integral $D\mu_\theta$ bounds the common reduced denominator by $D$. Therefore
$$
n\geq\max\{16,D^4\}
$$
ensures that every truthful labeling is a centre.
The remaining estimates are valid:
$$
\Delta\leq\Delta_H,\qquad
T_{\min}=ns_{\min},\qquad
\varepsilon\leq\frac{2\Delta_H}{ns_{\min}},
\qquad
\mathrm{OPT}(I_n)\leq nS_q.
$$
They yield exactly the stated constant $C_H$. These estimates remain valid when $\varepsilon=1$.
The proposed remainder is nonnegative, covers the finitely many admissible scales below $N_H$, and satisfies
$$
\frac{r_H(n)}n\longrightarrow0.
$$
Neither the mechanism nor its constant depends on the true masses. Only the analysis and allowed remainder do. The guarantee holds for every labeling because all truthful labelings are centres and all centre welfare constraints are included simultaneously.
Conclusion: The claimed universal asymptotic guarantee is verified.
The profile, context, variable, and numerical-row counts are valid upper bounds. The formulas for truthful task count, edge count, and maximum output assignments are also correct.
The exponential running-time form is consistent with explicitly constructing the stated system and performing polynomially many rational operations in its size.
Minor issue: The polynomial bound on intermediate rational encoding lengths is asserted without specifying the nullspace selection and arithmetic implementation. Finiteness of the rational algorithm alone does not establish that bit bound.
Minimum clarification: Specify the exact rational linear-algebra implementation and provide a short bound on intermediate encoding lengths across at most $V$ rounding iterations. This concerns the stated running time, not the mathematical existence or approximation guarantee.
The substantive construction is sound. The required repairs are limited to specifying rational inputs for the rounding algorithm and documenting its bit complexity. No blocking issue remains for the asymptotic existence claim.
The established result is an approximation guarantee with an exponential-time construction. It does not establish polynomial-time solvability or computational hardness.
⟨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.