d4-conf-sagt-2024-0015 (d4-conf-sagt-2024-0015)

Given finite agent-type and item-type sets \(T\) and \(G\), rational agent masses \(\mu_t\) and item supplies \(q_g\) summing to \(1\), strict rankings of item types, and either rational values \(v_t(g)\) or metric costs \(c_t(g)\), form each admissible \(N\)-agent instance with \(N\mu_t\) agents of type \(t\) and \(Nq_g\) items of type \(g\). Run the paper's uniform-random-order RSD on each finite instance. Establish and compute the limiting expected assignment masses \(x_{tg}=\lim_{N\to\infty}N^{-1}\mathbb{E}[\#\text{ type-}t\text{ agents assigned to type }g]\) and the corresponding per-capita expected welfare \(\sum_{t,g}x_{tg}v_t(g)\), or cost \(\sum_{t,g}x_{tg}c_t(g)\).

Let \(T\) be the agent-type support and \(G\) the item-type support, with \(\tau=|T|\) and \(m=|G|\). A society is given by its support: the list of its \(\tau\) positive-mass types, each mass a binary rational; \(\tau\) is the support size, not the number of possible types. Supplies are also positive binary rationals, with \(\sum_t\mu_t=\sum_g q_g=1\); let \(L\) be the total input bit length.
Each type has a strict ranking of all item types and either nonnegative rational values \(v_t(g)\), ranked in nonincreasing order, or nonnegative rational costs \(c_t(g)\), ranked in nondecreasing order. In the cost setting, the input is promised to admit points \(a_t,b_g\) in a common metric space with \(c_t(g)=d(a_t,b_g)\); points may coincide. The supplied ranking resolves equal values or costs.
For every positive integer \(N\) making all \(N\mu_t\) and \(Nq_g\) integral, create those numbers of agents and item copies. RSD uses a uniformly random permutation of all agents; each agent takes one copy of its highest-ranked type still available. Copies within a type are interchangeable.
Define \(A^{(N)}_{tg}\) as the number of type-\(t\) agents receiving type-\(g\) items, and \(x_{tg}=\lim_{N\to\infty}\mathbb E[A^{(N)}_{tg}]/N\), along admissible integers. The associated per-capita welfare and cost are \(W=\sum_{t,g}x_{tg}v_t(g)\) and \(C=\sum_{t,g}x_{tg}c_t(g)\).

Do these limits exist for every input, and is exact computation of \(x\) and the applicable aggregate \(W\) or \(C\) possible in time polynomial in \(m,\tau,L\), or is the computation NP-hard?

Exact finite-instance RSD expected welfare and metric cost are \(\#\mathrm P\)-hard. [Caragiannis–Homrighausen](https://arxiv.org/abs/2405.14316)
Che–Kojima establish convergence of replica RSD assignments to continuum probabilistic serial, including proportionally growing unequal supplies; this covers the limit specified here, so it cannot honestly be presented as an unresolved limit problem. [Primary source](https://www.columbia.edu/~yc2271/files/papers/psrp28.pdf)

Result

All the limits exist. The limiting allocation \(x\), and hence the applicable aggregate \(W\) or \(C\), can be computed exactly in time polynomial in \(m,\tau,L\).

The limit is the mass-weighted probabilistic serial allocation. This agrees with the convergence result of [Che–Kojima](https://www.columbia.edu/~yc2271/files/papers/psrp33-EMA.pdf). Below is a self-contained proof for the specified inputs, followed by an exact algorithm and its bit-complexity analysis.

1. The continuum allocation

Let \(s\) denote time, starting at zero. Each type \(t\) consumes its highest-ranked available item type at rate \(\mu_t\). Write \(z_{tg}(s)\) for its cumulative consumption and
\[ r_g(s)=q_g-\sum_t z_{tg}(s) \]
for the remaining supply.

This process has a precise finite-stage construction. At the beginning of a stage, let
\[ S=\{g:r_g>0\}, \qquad h_t(S)=\text{the highest-ranked item in }S, \]
and define
\[ a_g=\sum_{t:h_t(S)=g}\mu_t. \]
The duration of the stage is
\[ \Delta=\min_{g\in S:a_g>0}\frac{r_g}{a_g}. \]
During the stage, update
\[ z_{t,h_t(S)}\leftarrow z_{t,h_t(S)}+\mu_t\Delta, \qquad r_g\leftarrow r_g-a_g\Delta. \]
Remove every item whose remaining supply becomes zero, including all simultaneous exhaustions.

Whenever \(S\) is nonempty, every type chooses an item in \(S\), so \(\sum_g a_g=1\). Thus the minimum exists and is positive. Each stage exhausts at least one item, so there are at most \(m\) stages.

At elapsed time \(s\), total remaining supply is \(1-s\). Moreover,
\[ \Delta \leq \sum_{g:a_g>0}a_g\frac{r_g}{a_g} = \sum_{g:a_g>0}r_g \leq 1-s. \]
Consequently the construction never passes time one. Upon termination all supply is exhausted, so termination occurs exactly at time one. Define
\[ x^*_{tg}=z_{tg}(1). \]
Then
\[ \sum_g x^*_{tg}=\mu_t, \qquad \sum_t x^*_{tg}=q_g. \]

2. Convergence of finite RSD to this allocation

Fix an admissible \(N\). After the first \(k\) agents in the random permutation have acted, let \(B_t^{(N)}(k)\) be the number of those agents of type \(t\).

Define \(F_t^{(N)}(s)\) by linearly interpolating \(B_t^{(N)}(k)/N\) at times \(s=k/N\). Likewise, let \(Y_{tg}^{(N)}(s)\) interpolate the normalized cumulative assignments. In particular,
\[ Y_{tg}^{(N)}(1)=\frac{A_{tg}^{(N)}}N. \]
Every coordinate of these processes is nondecreasing and \(1\)-Lipschitz, and
\[ \sum_gY_{tg}^{(N)}(s)=F_t^{(N)}(s), \qquad \sum_{t,g}Y_{tg}^{(N)}(s)=s. \]

Uniform convergence of type arrivals

For a fixed prefix length \(k\), the variable \(B_t^{(N)}(k)\) is hypergeometric. Hence
\[ \mathbb E[B_t^{(N)}(k)]=k\mu_t, \qquad \operatorname{Var}(B_t^{(N)}(k))\leq N. \]
Chebyshev’s inequality therefore gives convergence in probability of normalized counts to their means at each fixed time; interpolation contributes at most \(1/N\).

To obtain uniform convergence, fix a finite grid of mesh at most \(\delta\). A union bound gives convergence simultaneously at its grid points. Between grid points, both \(F_t^{(N)}\) and \(s\mapsto\mu_ts\) are \(1\)-Lipschitz, so the error increases by at most \(2\delta\). First letting \(N\) tend to infinity and then letting \(\delta\) tend to zero proves
\[ \max_t\sup_{0\leq s\leq1} \left|F_t^{(N)}(s)-\mu_ts\right| \xrightarrow{\mathbb P}0. \]

Identification of every possible assignment limit

Consider any deterministic sequence of permutation realizations along which the preceding arrival error tends to zero. The assignment paths are uniformly bounded and uniformly Lipschitz. By the Arzelà–Ascoli theorem, every subsequence has a further subsequence converging uniformly to a path \(y\).

Its coordinates are nondecreasing and Lipschitz, and
\[ \sum_g y_{tg}(s)=\mu_ts, \qquad r_g(s):=q_g-\sum_t y_{tg}(s)\geq0, \qquad \sum_g r_g(s)=1-s. \]

We now determine its derivatives, which exist almost everywhere.

If \(r_g(s)=0\), monotonicity and feasibility imply that every coordinate \(y_{tg}\) remains constant thereafter. Thus exhausted items receive no further allocation, apart from irrelevant individual exhaustion times.

Next suppose \(t\) ranks \(g\) above \(h\). On any closed interval contained in the open set where \(r_g>0\), uniform convergence ensures that item \(g\) remains available throughout the corresponding finite processes, for all sufficiently large \(N\). RSD therefore makes no assignments of \(h\) to type \(t\) on that interval. Consequently \(y_{th}\) is locally constant wherever a better-ranked item has positive remaining supply.

For \(s<1\), at least one item has positive remaining supply because their total remaining supply is \(1-s\). Let \(h_t(s)\) be type \(t\)’s highest-ranked such item. The preceding observations eliminate every other item from its allocation derivative. Differentiating the row identity therefore yields, almost everywhere,
\[ y'_{tg}(s)= \begin{cases} \mu_t,&g=h_t(s),\\ 0,&g\neq h_t(s). \end{cases} \]

These equations uniquely determine the path. Indeed, between consecutive exhaustion times the available set is fixed, so all rates are fixed. The next exhaustion occurs after exactly the minimum residual-supply-to-rate ratio from Section 1. Removing all items exhausted at that time and repeating determines the entire path in at most \(m\) stages. Thus \(y=z\).

It follows that whenever type-arrival errors tend to zero, the assignment paths converge uniformly to \(z\): otherwise a subsequence staying a positive distance away would have a uniformly convergent further subsequence, whose limit was just proved to equal \(z\).

Combining this deterministic implication with arrival convergence gives
\[ Y_{tg}^{(N)}(1)\xrightarrow{\mathbb P}x^*_{tg}. \]
For completeness, failure of this implication in probability would allow us to select realizations with arbitrarily small arrival error but assignment error bounded away from zero, contradicting the preceding compactness argument.

Finally, these normalized assignment variables lie in \([0,1]\). For every \(\varepsilon>0\),
\[ \mathbb E\left|Y_{tg}^{(N)}(1)-x^*_{tg}\right| \leq \varepsilon+ \Pr\left(\left|Y_{tg}^{(N)}(1)-x^*_{tg}\right|>\varepsilon\right). \]
Therefore
\[ \lim_{\substack{N\to\infty\\N\text{ admissible}}} \frac{\mathbb E[A_{tg}^{(N)}]}N =x^*_{tg}. \]
This proves existence and identifies the requested limits.

3. Exact computation and polynomial bit complexity

The stage construction already gives an exact rational algorithm. The remaining issue is whether its intermediate numbers have polynomial bit length.

Let \(D\) be the product of the input denominators of the masses, and \(E\) the product of the input denominators of the supplies. Write
\[ \mu_t=\frac{M_t}{D}, \qquad q_g=\frac{Q_g}{E}. \]
Then
\[ \sum_t M_t=D, \qquad \sum_g Q_g=E, \qquad \log_2D+\log_2E=O(L). \]
The products themselves may be large, but their binary encodings have polynomial length.

Maintain a common denominator \(H\) for every residual supply, allocation entry, and elapsed time:
\[ r_g=\frac{R_g}{H}, \qquad z_{tg}=\frac{Z_{tg}}H, \qquad s=\frac UH. \]
Initially take \(H=ED\), \(R_g=DQ_g\), and all allocation and time numerators zero.

At a stage, put
\[ K_g=\sum_{t:h_t(S)=g}M_t, \qquad a_g=\frac{K_g}{D}. \]
Choose an item \(e\) minimizing \(R_g/K_g\) among those with \(K_g>0\). Then
\[ \Delta=\frac{DR_e}{HK_e}. \]
Using the new denominator \(H'=HK_e\), the exact updates are
\[ R'_g=K_eR_g-K_gR_e, \]
\[ Z'_{tg}= \begin{cases} K_eZ_{tg}+M_tR_e,&g=h_t(S),\\ K_eZ_{tg},&g\neq h_t(S), \end{cases} \]
and
\[ U'=K_eU+DR_e. \]
All comparisons use integer cross multiplication. No rounding is required.

Since \(1\leq K_e\leq D\), after at most \(m\) stages,
\[ H\leq ED^{m+1}. \]
Every represented residual, allocation, and elapsed time belongs to \([0,1]\), so its nonnegative numerator is at most \(H\). Thus all stored integers have
\[ O\bigl(1+\log E+(m+1)\log D\bigr) = O\bigl(1+(m+1)L\bigr) \]
bits. Products used in comparisons and updates also have polynomial bit length.

A straightforward implementation scans the listed rankings and updates the allocation matrix at each stage, using \(O(\tau m^2)\) arithmetic operations overall. Standard exact integer arithmetic therefore gives polynomial bit complexity in \(m,\tau,L\).

The algorithm uses only the \(\tau\) listed positive-mass types. It neither enumerates unlisted rankings nor constructs any replicated finite society.

4. Welfare, cost, and the metric promise

Having computed \(x=x^*\), calculate the applicable aggregate by exact rational arithmetic:
\[ W=\sum_{t,g}x_{tg}v_t(g), \qquad C=\sum_{t,g}x_{tg}c_t(g). \]
There are \(\tau m\) terms. A common denominator can be obtained by multiplying the final allocation denominator by the input denominators of the applicable cardinal data. Its bit length is polynomial, because those input denominators have total bit length at most \(L\). Numerators likewise have polynomial length. Hence the aggregate is exactly computable in polynomial time.

The cost algorithm needs only the supplied costs and rankings. It therefore applies to every input satisfying the metric promise without reconstructing the metric space. Equal values or costs cause no ambiguity because the supplied strict rankings determine every choice.

The cited finite-instance hardness concerns exact expectations before replication and passage to the limit. It does not prevent the limiting quantities proved here from having polynomial-time exact algorithms. See [Caragiannis–Homrighausen](https://arxiv.org/abs/2405.14316).

⟨structured verdict parsed — rendered above⟩

The output resolves the requested limit and exact-computation questions in substance. The limiting allocation is identified correctly, and the exact algorithm has polynomial bit complexity. I found no false central step, incorrect update, or missing substantive lemma. Two minor theorem-statement omissions remain under the requested verification standard.

1. Scope and assumptions

The proof addresses the specified support representation: it works with the \(\tau\) listed types and their masses, without enumerating possible rankings.

Positive masses and supplies, their normalization, and complete strict rankings supply all assumptions needed by the construction. Cardinal values and costs are used only after computing the allocation. Consequently, equal cardinal quantities and coincident metric points do not invalidate any step.

Rationality also ensures there are arbitrarily large admissible integers \(N\). Thus the limiting sequence in the task is well defined.

2. Continuum construction

All substantive steps in Section 1 are correct.

• When the available set is nonempty, every type selects exactly one available item. Hence the total consumption rate is \(1\).
• At least one item has positive consumption rate, and each residual supply in the available set is positive. The minimum defining the stage duration therefore exists and is strictly positive.
• The update preserves nonnegative residual supplies because the stage duration is the minimum exhaustion ratio.
• Removing every simultaneous exhaustion ensures that each stage removes at least one item. There are at most \(m\) stages.
• The displayed bound on the stage duration is valid: the minimum is bounded by the weighted average because the positive rates sum to \(1\).
• Total residual supply is \(1-s\). The construction cannot pass time \(1\), and exhausting every supply forces its terminal time to be exactly \(1\).

The resulting row and column sums are correct. Each type consumes at rate \(\mu_t\) throughout the unit time interval, and each item’s initial supply is exhausted.

3. Arrival convergence

The probabilistic argument is correct.

For each prefix, the type count is hypergeometric with the stated mean. The variance bound by \(N\) is valid, including degenerate cases where the count is deterministic. After normalization, Chebyshev’s inequality gives convergence at each fixed time.

The interpolation error is at most \(1/N\). A finite-grid union bound is applicable because, for a fixed input, both the grid and the type set are finite. The Lipschitz estimate between grid points is correct. The resulting uniform convergence in probability does not require independence between prefix counts.

No convergence rate uniform over different inputs is needed: this part proves existence separately for every fixed input.

4. Identification of subsequential assignment limits

The compactness and preference arguments are sound, with one minor presentation issue.

Minor issue 1 — Section 2, invocation of Arzelà–Ascoli.
The output names the theorem but does not state its precise form, as required by the verification instructions. The needed compactness conclusion is applicable: the domain is compact, the codomain has fixed finite dimension, and the assignment paths are uniformly bounded and equicontinuous.

Minimum clarification: State the version of Arzelà–Ascoli being used and explicitly identify these hypotheses. No additional mathematical argument is required.

The remaining limit-identification steps check out:

• Uniform convergence preserves monotonicity, Lipschitz bounds, feasibility, and the row and total-allocation identities.
• If an item’s limiting residual supply reaches zero, monotonicity and feasibility force all its allocation coordinates to remain constant afterward.
• On a closed interval where a better-ranked item has positive limiting residual supply, continuity provides a positive minimum residual. Uniform convergence therefore makes that item available in the finite processes for sufficiently large \(N\). The prohibition on choosing a worse item follows.
• Linear interpolation does not undermine this argument: an allocation segment overlapping the interval corresponds to a choice made at its preceding grid point, where the better item is also available.
• At every time strictly before \(1\), positive total residual supply guarantees a highest-ranked available item for every type.
• There are finitely many allocation coordinates and exhaustion times. The derivative exclusions and differentiated row identities can therefore be combined outside a single measure-zero exceptional set.

The stated derivative equations follow.

5. Uniqueness and convergence of expectations

The uniqueness argument is correct in substance, but it implicitly uses another standard theorem.

Minor issue 2 — Section 2, “These equations uniquely determine the path.”
The transition from almost-everywhere derivative equations to fixed-rate evolution on each stage requires absolute continuity and the integral representation of the path. Lipschitz continuity supplies these properties, but the output does not state or explicitly invoke them.

Minimum clarification: State that Lipschitz coordinates are absolutely continuous and that their increments equal the integrals of their derivatives. Explicitly invoke this fact when passing from the derivative equations to the stage evolution.

With that standard justification, the described uniqueness argument is valid. Availability changes only when an item becomes exhausted; exhausted items never return. The next exhaustion is determined by the minimum residual-to-rate ratio, and simultaneous exhaustions are removed together.

The subsequent compactness contradiction correctly promotes uniqueness of subsequential limits to convergence of the assignment paths whenever arrival errors vanish.

The passage to convergence in probability is also valid. If assignment convergence failed, arrival convergence would permit selecting realizations with vanishing arrival error and assignment error bounded away from zero, contradicting the deterministic conclusion.

Finally, the bounded-variable estimate is correct. It establishes convergence in mean and hence convergence of the normalized expectations along all admissible integers.

6. Exact arithmetic and bit complexity

The denominator construction and every displayed integer update are correct.

• The products \(D\) and \(E\) are valid common denominators, with total binary length bounded by the input length.
• Initially, \(H=ED\) represents supplies, zero allocations, and zero elapsed time correctly.
• Minimizing \(R_g/K_g\) gives the correct exhaustion choice because the omitted factor \(D/H\) is common and positive.
• The formula for the stage duration is correct.
• Multiplying the denominator by \(K_e\) gives exactly the stated residual, allocation, and time updates.
• The minimizing property ensures that every updated residual numerator is nonnegative.
• Previously exhausted items remain exhausted.

The denominator bound \(H\leq ED^{m+1}\) is valid because each stage multiplies it by an integer between \(1\) and \(D\), and there are at most \(m\) stages.

Residual supplies, allocation entries, and elapsed time all lie in \([0,1]\), so their stored numerators are at most the common denominator. Comparison products and update products also have polynomial bit length.

The claimed \(O(\tau m^2)\) arithmetic-operation bound is consistent with scanning rankings and updating the allocation matrix in each of at most \(m\) stages. Standard exact integer arithmetic therefore yields the asserted polynomial running time.

7. Aggregates, metric promise, and cited context

The aggregate computation is correct. Multiplying the final allocation denominator by the cardinal-data denominators gives a common denominator of polynomial bit length. Cardinal-data numerators have input-bounded bit length, and summing \(\tau m\) terms preserves polynomial bit length.

The metric promise introduces no additional computational step: the task supplies the costs, and the algorithm needs no metric realization.

The convergence discussion is consistent with the asymptotic equivalence established by [Che–Kojima](https://www.columbia.edu/~yc2271/files/papers/psrp33-EMA.pdf). The output’s independent convergence argument handles its claimed input scope directly, so an unstated application of that paper is not carrying the proof.

The distinction between finite-instance expectations and limiting allocations is legitimate. The finite-instance hardness premise does not contradict the polynomial algorithm established here.

Required feedback

Only two expositional clarifications are needed: state the applicable Arzelà–Ascoli theorem, and explicitly invoke absolute continuity when integrating the derivative equations. Neither changes the construction, convergence argument, or complexity conclusion.

⟨structured verdict parsed — rendered above⟩