Answer: For every input, \(W_\infty\) exists and is characterized by the remaining-supply flow. It can be approximated deterministically to additive error \(\varepsilon\) in time polynomial in \(m,\tau,L,1/\varepsilon\), together with exact computation of \(\nu^*\). The universal guarantee \(W_\infty\ge(\nu^*)^2/e\) holds.
Theorem 3 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateRandom Serial Dictatorship always returns an assignment in which the expected social welfare is at least 1 e ν(O)2 n in one-sided matching problems with normalized von Neumann- Morgenstern preferences, where ν (O) is the maximum social welfare.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given rational type masses \(\mu_t\) and category supplies \(\rho_j\), each summing to \(1\), and normalized values \(v_t(j)\in[0,1]\), define a market with \(D\mu_t\) agents of type \(t\) and \(D\rho_j\) items of category \(j\), for common-denominator multiples \(D\). What is the limiting per-capita expected welfare \(W_\infty=\lim_{D\to\infty}\mathbb{E}[\mathrm{SW}(\mathrm{RSD})]/D\), and can it be computed to additive error \(\varepsilon\)? Compute also \(\nu^*=\max_x\sum_{t,j}v_t(j)x_{tj}\), subject to \(\sum_jx_{tj}=\mu_t\) and \(\sum_tx_{tj}=\rho_j\), and determine whether \(W_\infty\ge(\nu^*)^2/e\).
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.
There are \(m\ge1\) item categories with positive binary-rational supplies \(\rho_j\), with \(\sum_t\mu_t=\sum_j\rho_j=1\); type values \(v_t(j)\in[0,1]\) are binary rationals, and equal values are allowed.
For each positive integer \(D\) divisible by a common denominator of the masses and supplies, form \(D\mu_t\) agents of type \(t\) and \(D\rho_j\) distinct items of category \(j\); every such item has value \(v_t(j)\) to type \(t\).
Random Serial Dictatorship (RSD) chooses a uniformly random agent ordering; each agent takes a highest-valued remaining item, uniformly among all tied individual items, including when all remaining values are zero. Every agent receives exactly one item; \(\mathrm{SW}\) is the sum of assigned values.
Write \(W_\infty=\lim_{D\to\infty}\mathbb E[\mathrm{SW}(\mathrm{RSD})]/D\), along these admissible replication sizes, whenever the limit exists.
Define \(\nu^*=\max_{x\ge0}\sum_{t,j}v_t(j)x_{tj}\), subject to \(\sum_jx_{tj}=\mu_t\) and \(\sum_tx_{tj}=\rho_j\). Let \(0<\varepsilon<1\) be binary rational and \(L\) the total input bit length; state running times in \(m,\tau,L,1/\varepsilon\).
Does \(W_\infty\) exist for every such input, and can it be characterized and computed to additive error \(\varepsilon\) in time polynomial in \(m,\tau,L,1/\varepsilon\), together with \(\nu^*\)?
Does the universal approximation guarantee \(W_\infty\ge(\nu^*)^2/e\) hold, or is there a counterexample?
For finite normalized-value assignments, RSD satisfies \(\mathbb E[\mathrm{SW}]\ge\nu(O)^2/(en)\), where \(\nu(O)\) is optimal welfare and \(n\) is the common number of agents and items. [Adamczyk–Sankowski–Zhang](https://arxiv.org/abs/1407.3957)
For strict category rankings and equal category quotas, replica RSD converges to continuum probabilistic serial; this result does not address ties between categories resolved uniformly over remaining individual items. [Che–Kojima](https://cowles.yale.edu/sites/default/files/2022-08/d1677.pdf)
For every input in the question, \(W_\infty\) exists. It is characterized by the remaining-supply flow defined below, and it can be approximated deterministically to additive error \(\varepsilon\) in time polynomial in \(m,\tau,L,1/\varepsilon\). The transportation optimum \(\nu^*\) can be computed exactly in polynomial time.
The universal guarantee also holds:
\( \displaystyle W_\infty\ge \frac{(\nu^*)^2}{e}. \)
The proof includes the specified rule for ties between categories and for zero-valued remaining items.
Throughout, the type masses \(\mu_t\) are fixed and satisfy \(\sum_t\mu_t=1\).
For a nonzero inventory vector \(r\in\mathbb R_{\ge0}^m\), define
\( \displaystyle S(r)=\{j:r_j>0\},\qquad B_t(r)=\operatorname*{arg\,max}_{j\in S(r)}v_t(j). \)
Define the type-specific choice probabilities, aggregate consumption rates, and instantaneous welfare by
\( \displaystyle q_{tj}(r)= \begin{cases} \frac{r_j}{\sum_{k\in B_t(r)}r_k},&j\in B_t(r),\\ 0,&j\notin B_t(r), \end{cases} \qquad f_j(r)=\sum_t\mu_tq_{tj}(r), \)
\( \displaystyle G(r)=\sum_t\mu_t\max_{j\in S(r)}v_t(j). \)
Set \(q_{tj}(0)=f_j(0)=G(0)=0\).
The candidate limiting inventory satisfies
\[ \displaystyle \dot r_j(s)=-f_j(r(s)),\qquad r(0)=\rho. \tag{1} \]
Categories with zero inventory remain unavailable. Notice that the probabilities within a top tie are proportional to remaining supplies. These are precisely the probabilities induced by uniform choice among tied individual items.
For an arbitrary initial inventory \(a\ge0\), write \(\Phi_s(a)\) for its flow, continued as zero after exhaustion, and define
\[ \displaystyle H(a)=\int_0^\infty G(\Phi_s(a))\,ds. \tag{2} \]
We will prove that
\[ \displaystyle W_\infty=H(\rho)=\int_0^1G(r(s))\,ds. \tag{3} \]
On any fixed positive support \(S\), the sets \(B_t\) are fixed. The field \(f\) is then a smooth rational function of the positive coordinates. Moreover,
\[ \displaystyle 0\le f_j(r)\le1,\qquad \sum_jf_j(r)=1 \quad(r\ne0). \tag{4} \]
Consequently, a solution exists uniquely until it approaches the boundary of that support. Its coordinates are nonincreasing and have bounded derivatives, so they have limits at the boundary time.
If the limiting inventory is nonzero, delete all coordinates that have reached zero and restart on the smaller support. If no earlier boundary occurs, conservation of total inventory forces exhaustion at time \(\sum_ja_j\). Each restart deletes at least one category, so there are at most \(m\) extinction times.
This constructs an absolutely continuous solution of (1), with
\[ \displaystyle \sum_j\Phi_s(a)_j=\max\!\left\{\sum_ja_j-s,0\right\}. \tag{5} \]
We next establish uniqueness and the stability needed for computation.
Let \(I\subseteq\{1,\ldots,m\}\), and suppose inventories \(r,z\) satisfy
\( \displaystyle r_j\ge z_j\quad(j\in I),\qquad r_j\le z_j\quad(j\notin I). \)
For every type \(t\),
\[ \displaystyle \sum_{j\in I}q_{tj}(r)\ge\sum_{j\in I}q_{tj}(z). \tag{6} \]
Here is a direct verification. If the probability on the right is zero, there is nothing to prove. Otherwise, let \(a\) be that type’s best available value inside \(I\) under \(z\). Its best value outside \(I\) under \(z\) is at most \(a\).
Under \(r\), the best value inside \(I\) is at least \(a\), and the best value outside \(I\) is at most \(a\). If either comparison becomes strict in favor of \(I\), the choice probability of \(I\) under \(r\) is one. In the remaining case, both sides compete at value \(a\). The mass inside \(I\) at that value has increased, while the competing mass outside \(I\) has decreased. The fraction of tied mass belonging to \(I\) therefore cannot decrease. This proves (6), including empty-inventory cases.
After averaging over types, (6) also holds for \(f\).
For any two flow solutions,
\[ \displaystyle \sum_j\bigl(\Phi_s(a)_j-\Phi_s(b)_j\bigr)_+ \le \sum_j(a_j-b_j)_+. \tag{7} \]
Indeed, at almost every time let \(I\) consist of the coordinates where the first inventory exceeds the second. Differentiating the positive-part sum gives
\( \displaystyle -\sum_{j\in I}f_j(\Phi_s(a)) +\sum_{j\in I}f_j(\Phi_s(b)) \le0 \)
by (6). For absolutely continuous coordinate differences, their derivatives vanish almost everywhere on their zero sets; thus equality coordinates cause no missing terms in this differentiation.
Applying (7) in both directions proves
\[ \displaystyle \|\Phi_s(a)-\Phi_s(b)\|_1\le\|a-b\|_1. \tag{8} \]
In particular, the flow is unique. Also, applying (7) with the inventories reversed shows that
\[ \displaystyle a\ge b\ \Longrightarrow\ \Phi_s(a)\ge\Phi_s(b)\quad\text{for every }s. \tag{9} \]
Although \(G\) is discontinuous when a category disappears, its integrated value is stable:
\[ \displaystyle |H(a)-H(b)|\le m\|a-b\|_1. \tag{10} \]
We prove this first when \(a\ge b\). Put \(\delta=\sum_j(a_j-b_j)\), and let \(r(s)=\Phi_s(a)\), \(z(s)=\Phi_s(b)\).
Order preservation gives \(r(s)\ge z(s)\). Until \(z\) is exhausted, the total inventory difference is exactly \(\delta\); afterwards, the total remaining inventory of \(r\) is at most \(\delta\).
For each category \(j\), let \(\sigma_j\) be its extinction time in \(z\), taking \(\sigma_j=0\) when \(b_j=0\). Then
\[ \displaystyle r_j(\sigma_j)\le\delta. \tag{11} \]
Consider a type whose best available value in \(r(s)\) exceeds its best available value in \(z(s)\). Every category in that type’s top tie under \(r(s)\) must already be exhausted in \(z(s)\). Otherwise, the same best value would still be available in \(z(s)\).
Since values lie in \([0,1]\), that type’s contribution to \(G(r(s))-G(z(s))\) is at most its consumption rate into categories already exhausted in \(z\). This remains true after \(z\) itself is exhausted. Therefore,
\[ \displaystyle 0\le H(a)-H(b) \le\sum_j\int_{\sigma_j}^{\infty}f_j(r(s))\,ds =\sum_jr_j(\sigma_j) \le m\delta. \tag{12} \]
For general \(a,b\), use their coordinatewise minimum and maximum. Their flows bracket both original flows by (9), and \(G\) is nondecreasing with respect to inventory inclusion. The difference between the maximum and minimum inventories has total mass \(\|a-b\|_1\), so (12) proves (10).
We now prove (3), without using a strict-ranking convergence theorem.
For replication size \(D\), let \(R^D(s)\) be the remaining category inventories divided by \(D\), linearly interpolated between successive assignments at times \(k/D\). Every sample path satisfies
\[ \displaystyle R^D(0)=\rho,\qquad \sum_jR_j^D(s)=1-s. \tag{13} \]
Its coordinates are nonincreasing, and the path is \(1\)-Lipschitz in the \(\ell_1\) norm.
Let \(U_t^D(k/D)\) be the number of type-\(t\) agents among the first \(k\) positions, divided by \(D\). Uniform random ordering gives
\[ \displaystyle \sup_{0\le s\le1}|U_t^D(s)-\mu_ts| \xrightarrow{\mathbb P}0. \tag{14} \]
For completeness, at a fixed time the prefix count is hypergeometric, with variance at most \(D/4\). Chebyshev’s inequality gives convergence at every point of a finite time grid. Monotonicity between grid points, followed by refinement of that grid, proves (14).
Conditioned on the first \(k\) assignments, the probability that the next agent has type \(t\) is
\( \displaystyle p_t^D(k)=\frac{\mu_t-U_t^D(k/D)}{1-k/D}. \)
Consequently, for each fixed \(\eta>0\), (14) implies
\[ \displaystyle \sup_{k/D\le1-\eta}|p_t^D(k)-\mu_t| \xrightarrow{\mathbb P}0. \tag{15} \]
Conditional on this next type and on the inventory, its category-choice probabilities are exactly \(q_{tj}\). Thus the conditional expected category-consumption rate is
\( \displaystyle f_j(R^D,p^D)=\sum_tp_t^Dq_{tj}(R^D). \)
Subtracting these conditional expectations from actual normalized category consumptions produces martingales. Each increment has absolute value at most \(1/D\), so its terminal second moment is at most \(1/D\). Doob’s maximal inequality therefore shows that the supremum of each martingale error tends to zero in probability. The same argument applies to normalized welfare.
Consider any sequence of sample paths on which the errors in (14) and the preceding martingale errors tend to zero. Compactness of the uniformly Lipschitz inventory paths gives a uniformly convergent subsequence with limit \(r\).
Fix a closed interval \([a,b]\subset[0,1)\) on which the positive support \(S\) of \(r\) is constant. Its coordinates in \(S\) have a positive lower bound. Coordinates outside \(S\) converge uniformly to zero.
For type \(t\), let \(q_t^S(y_S)\) be its choice distribution restricted to inventory \(y_S\), and let \(c_t(y)\) be its actual probability of choosing outside \(S\). Whenever all categories in \(S\) are available,
\[ \displaystyle q_t(y)|_S=(1-c_t(y))q_t^S(y_S). \tag{16} \]
To verify (16), if an outside category has strictly higher value than every category in \(S\), its left side and the factor \(1-c_t(y)\) are both zero. Otherwise, choices inside \(S\), conditional on making such a choice, are proportional to the inventories in its best tie within \(S\).
Actual consumption outside \(S\) on \([a,b]\) tends to zero, because those inventories converge to zero. The category martingale bounds imply that its conditional expected consumption also tends to zero:
\[ \displaystyle \int_a^b\sum_tp_t^D(s)c_t(R^D(s))\,ds\longrightarrow0. \tag{17} \]
Equation (16) gives
\[ \displaystyle \left\|f(R^D,p^D)|_S-f^S(R_S^D,\mu)\right\|_1 \le \|p^D-\mu\|_1+\sum_tp_t^Dc_t(R^D). \tag{18} \]
On this interval, \(f^S\) is continuous in the positive coordinates. Equations (15), (17), and (18), together with the category martingale identities, therefore imply
\[ \displaystyle r(b)-r(a)=-\int_a^bf(r(s))\,ds. \tag{19} \]
Each coordinate of \(r\) is nonincreasing and can become zero only once. Hence there are at most \(m\) support-change times. Applying (19) within the intervening intervals identifies \(r\) as an absolutely continuous solution of (1) almost everywhere. Uniqueness from Section 2 identifies it with \(\Phi_s(\rho)\).
This proves convergence in probability of the inventory paths. Explicitly, if uniform convergence in probability failed, one could select paths a fixed distance from \(\Phi_s(\rho)\) while all the preceding errors tend to zero; compactness and (19) would contradict uniqueness.
On the same interval \([a,b]\), let \(g_p(y)\) be conditional expected welfare of the next assignment. Then
\[ \displaystyle 0\le g_p(y)-\sum_tp_t\max_{j\in S}v_t(j) \le\sum_tp_tc_t(y). \tag{20} \]
Indeed, any strictly higher best value outside \(S\) forces that type to choose outside \(S\), and the value difference is at most one.
Equations (15), (17), and (20) show convergence of the integrated conditional welfare on every such interval. The welfare martingale error vanishes as well. Small neighborhoods of the finitely many support-change times and of the endpoint contribute arbitrarily little, since welfare per assignment is bounded by one. Therefore,
\[ \displaystyle \frac{\mathrm{SW}(\mathrm{RSD}_D)}{D} \xrightarrow{\mathbb P}\int_0^1G(\Phi_s(\rho))\,ds. \tag{21} \]
The random variables on the left belong to \([0,1]\), so convergence in probability also implies convergence of expectations. This proves existence of \(W_\infty\) and formula (3).
One may additionally characterize the limiting assignment by
\( \displaystyle x_{tj}^{\infty}=\int_0^1\mu_tq_{tj}(r(s))\,ds. \)
Its row sums are \(\mu_t\), its column sums are \(\rho_j\), and its welfare is \(W_\infty\).
Direct numerical integration near a vanishing inventory could have a large derivative bound. We instead discard small inventories and use the welfare stability bound (10) to control the cost.
Choose rational parameters
\[ \displaystyle \alpha=\frac{\varepsilon}{16m^2},\qquad h=\frac{\varepsilon\alpha}{16m} =\frac{\varepsilon^2}{256m^3},\qquad \beta=\frac{\varepsilon h}{32m^2}. \tag{22} \]
A cleanup operation rounds each coordinate down to a multiple of \(\beta\), then deletes every positive coordinate smaller than \(\alpha\).
Start with the cleaned inventory \(y=\rho\) and accumulator \(A=0\). While \(\sum_jy_j\ge h\):
Return \(A\). Any remaining inventory of mass less than \(h\) is ignored.
At the start of each iteration, every positive coordinate is at least \(\alpha\). Since \(h\le\alpha/2\) and \(f_j\le1\), neither the exact flow nor the Euler step loses a category during that step.
For a fixed top tie \(B\), the choice map \(q_j=y_j/\sum_{k\in B}y_k\) has Jacobian with induced \(\ell_1\) norm at most \(2/\sum_{k\in B}y_k\). Averaging over types shows that, where every positive coordinate is at least \(\alpha/2\),
\[ \displaystyle \|Df\|_{1\to1}\le\frac4\alpha. \tag{23} \]
Also, by total consumption,
\( \displaystyle \|\Phi_u(y)-y\|_1=u\qquad(0\le u\le h). \)
Thus
\[ \displaystyle \|\Phi_h(y)-(y-hf(y))\|_1 \le\int_0^h\frac{4u}{\alpha}\,du =\frac{2h^2}{\alpha}. \tag{24} \]
Because the support is unchanged throughout the exact step, its welfare is exactly \(hG(y)\).
Each iteration removes at least mass \(h\), so the number \(N\) of iterations is at most \(1/h\).
Each category is deleted at most once, at inventory less than \(\alpha\); total deletion loss is therefore at most \(m\alpha\). Each cleanup rounds away at most \(m\beta\), including the initial cleanup.
Apply (10) after each local Euler error and each cleanup. The identity
\( \displaystyle H(y)=hG(y)+H(\Phi_h(y)) \)
then telescopes over all iterations. The final omitted welfare is at most \(h\). Consequently,
\[ \displaystyle |H(\rho)-A| \le \frac{2mh}{\alpha} +m^2\alpha +m^2\beta(1/h+1) +h. \tag{25} \]
With (22), the four terms are bounded respectively by \(\varepsilon/8\), \(\varepsilon/16\), \(\varepsilon/16\), and \(\varepsilon/256\). In particular,
\[ \displaystyle |A-W_\infty|<\varepsilon. \tag{26} \]
There are
\( \displaystyle O(m^3/\varepsilon^2) \)
iterations. Each needs \(O(\tau m)\) rational arithmetic operations and value comparisons.
At iteration boundaries every inventory is an integer multiple of \(\beta\) and lies in \([0,1]\). Within a tie, its choice probabilities are therefore ratios of integers of bit length \(O(\log(m/\beta))\). Summing over the explicitly supplied \(\tau\) types gives intermediate rational operands of bit length
\( \displaystyle O\!\left(L+\tau\log(m/\varepsilon)\right). \)
Rounding resets inventories to the grid after every step. Accumulated rewards can use a fixed common denominator formed from the input denominators and the denominator of \(h\), so their bit lengths also remain polynomial.
A resulting bit-time bound is
\[ \displaystyle O\!\left( \frac{\tau m^4}{\varepsilon^2} \operatorname{poly}\!\left(L+\tau\log(m/\varepsilon)\right) \right). \tag{27} \]
The bound uses only the listed support types, and has no reciprocal dependence on the smallest mass or supply.
The defining transportation program has \(m\tau\) variables, \(\tau+m\) marginal equalities, rational coefficients, and a nonempty bounded feasible region. Nonemptiness follows, for example, from \(x_{tj}=\mu_t\rho_j\).
The standard polynomial bit-complexity theorem for rational linear programming states that an exact optimal objective value of a feasible bounded rational linear program can be computed in time polynomial in its encoding length. Its hypotheses hold here, so \(\nu^*\) is computable exactly in time polynomial in \(m,\tau,L\).
Combined with (27), both requested quantities are obtained in polynomial time.
Fix an admissible replication size \(D\), and let \(\nu(O_D)\) be optimal welfare in its finite assignment instance. Then
\[ \displaystyle \nu(O_D)=D\nu^*. \tag{28} \]
To justify equality, the scaled transportation program has integer row margins \(D\mu_t\) and column margins \(D\rho_j\). It has an integral optimum.
Here is a verification of that integrality fact. At a vertex, the bipartite graph of positive entries cannot contain a cycle: alternating sufficiently small increases and decreases around a cycle would express the point as the midpoint of two distinct feasible points. Thus its positive support is a forest. Repeatedly remove a leaf edge. Its value equals the remaining integer margin at its leaf; subtracting it preserves integer margins. Induction proves that every positive entry is integral.
Any such integer matrix can be realized by assigning the corresponding numbers of distinct category items to agents of each type. Conversely, every finite assignment gives such a matrix. Scaling the objective therefore proves (28).
The finite theorem supplied in the question applies: there are exactly \(D\) agents and \(D\) items, all values lie in \([0,1]\), and RSD chooses a best remaining item with uniform random tie-breaking. These are also the model assumptions in [Adamczyk–Sankowski–Zhang](https://arxiv.org/html/1407.3957v2).
It yields
\( \displaystyle \mathbb E[\mathrm{SW}(\mathrm{RSD}_D)] \ge\frac{\nu(O_D)^2}{eD} =\frac{D(\nu^*)^2}{e}. \)
Divide by \(D\) and use the convergence proved in Section 4:
\( \displaystyle \boxed{W_\infty\ge\frac{(\nu^*)^2}{e}}. \)
⟨structured verdict parsed — rendered above⟩
The output resolves the intended task in substance: the limiting flow, deterministic approximation algorithm, exact transportation optimum, and universal welfare guarantee are supported. I found three minor issues, all concerning definitions or routine exposition. I found no major gap or false central step.
The probabilities \(q_{tj}(r)\) correctly implement uniform choice among tied individual items: category probabilities are proportional to their remaining inventories. The definition also covers zero-valued choices.
On each fixed positive support, all relevant denominators are positive and the vector field is smooth. The bounds in (4) imply bounded derivatives and conservation of total inventory until exhaustion. Consequently, the construction by successive boundary limits and support deletion is valid. Simultaneous extinctions are accommodated, and each restart removes at least one category.
Equation (5) is consistent with the extension by zero after exhaustion, including an initially empty inventory.
The argument for (6) handles changes in the available support, rather than merely comparing fractions on a fixed support. Whenever the right-hand probability is positive, increasing inventory inside \(I\) and decreasing inventory outside \(I\) cannot worsen the best available value inside \(I\) relative to the outside options. The remaining tied-value comparison has the asserted direction.
The positive-part differentiation used in (7) is valid for absolutely continuous coordinate differences. The observation about derivatives on zero sets addresses equality coordinates.
Applying (7) in both directions yields (8); applying it with the inventories reversed establishes (9). These arguments justify uniqueness even though the vector field is discontinuous at support changes.
For ordered initial inventories, the total inventory difference is constant while both flows remain nonempty and is at most \(\delta\) afterwards. This justifies (11), including categories initially absent from the smaller inventory.
If a type obtains a strictly larger available value in the larger inventory, all its top choices there are categories already exhausted in the smaller inventory. Because values belong to \([0,1]\), the asserted charge to consumption of those categories is valid.
The integral in (12) equals the inventory remaining at the corresponding extinction time. The coordinatewise minimum/maximum argument then establishes (10). No continuity of \(G\) at extinction is assumed.
The hypergeometric variance bound and finite-grid argument establish (14). Restricting to times bounded away from \(1\) makes the denominator in the remaining-type formula uniformly positive, so (15) follows.
The category and welfare martingale increments are centered and bounded by \(1/D\); their terminal second moments have the claimed bound. The maximal-error conclusion is valid.
Minor issue 1: the cited maximal inequality is not stated precisely. The user’s verification standard expressly requires precise statements of invoked theorems. The output names Doob’s maximal inequality but does not specify its form.
Minimum clarification: State the version used, identify the martingales and filtration, and explicitly check its square-integrability hypotheses. The stated increment bounds already supply the necessary information.
Minor issue 2: interpolated inventories and conditional-rate inventories are conflated. Conditional choice probabilities use the inventory immediately before a discrete assignment. However, \(R^D\) is defined as linearly interpolated, and (17), (18), and the welfare discussion subsequently evaluate rates at \(R^D(s)\) without specifying a discrete-time convention.
These are not literally the same probabilities. For example, take one type, two equally valued categories, supplies \(1/2,1/2\), and \(D=2\). If the first assignment consumes category \(1\), the interpolated inventory at time \(1/4\) is \((1/4,1/2)\), giving \(q_{t1}=1/3\), whereas the conditional probability before the first assignment was \(1/2\).
Minimum clarification: Define the piecewise constant pre-assignment inventory and type probabilities used in the conditional-rate integrals. Specify whether the expressions in (17), (18), and (20) use that process, and explicitly account for its relation to the interpolated inventory. This is a routine discretization clarification; the limiting identification argument does not require a new convergence principle.
Subject to that convention, the identification argument is sound. Equation (16) correctly separates choices outside the limiting support. Vanishing outside inventory, together with the category martingale bounds, controls its integrated conditional consumption. Continuity on the surviving positive coordinates then justifies (19).
There are only finitely many support changes, and the limiting paths are already Lipschitz. Thus identification between support changes suffices for the almost-everywhere flow equation. The uniqueness argument establishes convergence in probability.
The welfare comparison (20) is valid. Bounded welfare controls neighborhoods of support changes and the final endpoint, and boundedness in \([0,1]\) justifies convergence of expectations. The stated limiting assignment has the claimed marginals and welfare.
The parameter choices satisfy \(h\le\alpha/2\). Starting an iteration with every positive coordinate at least \(\alpha\) prevents extinction during that exact step and keeps the Euler inventory nonnegative.
The Jacobian bound (23), local error (24), and exact step reward \(hG(y)\) are correct. Cleanup cannot revive deleted categories. The iteration count, cumulative deletion loss, cumulative rounding loss, and final omitted welfare are all bounded as claimed.
Substitution into (25) gives the stated four bounds. Their sum is strictly less than \(\varepsilon\).
Minor issue 3: the initialization is ambiguous. “Start with the cleaned inventory \(y=\rho\)” simultaneously suggests cleanup and literal equality with the uncleaned input. Arbitrarily small positive supplies are allowed, so the first iteration needs cleanup for the subsequent lower-bound argument.
Minimum clarification: Explicitly initialize \(y\) as the result of applying cleanup to \(\rho\), and retain the initial cleanup in the error accounting. The existing bound already includes that cleanup.
Grid inventories are integer multiples of \(\beta\), and their common factor cancels in within-tie probabilities. The integer ratios have the asserted size. Rational summation over the explicitly listed types has polynomial intermediate bit length, and cleanup resets inventories after each iteration.
The accumulator’s denominator can be bounded using the input denominators and the denominator of \(h\). Consequently, (27) gives a polynomial bit-time bound in the requested parameters. No enumeration of unlisted types or reciprocal dependence on the smallest mass or supply is hidden in this analysis.
The transportation program is feasible, bounded, and rational, with polynomial encoding size. The stated rational linear-programming theorem applies and permits exact computation of the optimal objective value in polynomial time.
The transportation integrality argument is valid: a positive-support cycle contradicts extremality, and leaf elimination in the resulting forest establishes integral entries when margins are integral. Realizability by distinct agents and items then proves (28).
The cited finite theorem applies to equal numbers of agents and items, values in \([0,1]\), and random choice among favorite remaining items. These assumptions match the replication instances, including ties and zero values. I checked the theorem and mechanism definitions in the [Adamczyk–Sankowski–Zhang paper](https://arxiv.org/html/1407.3957v2).
Substitution of (28), normalization by \(D\), and the established expectation limit yield \(W_\infty\ge(\nu^*)^2/e\).
⟨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.