d4-conf-sagt-2024-0015

My lead is Fluid-RSD Welfare/Cost Evaluation, a high-multiplicity version of the paper’s expected-efficiency question. The anchor is Theorem 1, proved in Section 3 of this paper by reduction from the cited #P-completeness results for computing the RSD lottery matrix. It states that, given an assignment instance with \(n\) agents and \(n\) items, computing RSD’s exact expected social welfare in the value setting is #P-hard, and computing its exact expected social cost in the metric cost setting is also #P-hard. The paper’s proof encodes the entries of the lottery matrix into polynomial-bit values or metric costs, so an exact expected objective would reveal those entries.

Here is the regime I would mirror: a large housing or school assignment market in which many agents share a small set of complete value and preference profiles, and the available units fall into a small set of interchangeable item types. For example, a type includes an agent’s full value vector and ranking; in the metric cost version, it includes the agent’s location. Items of the same type have identical values or costs for every agent type, and their supply scales with the population. The number \(N\) of agents and items grows while the numbers of agent types \(\tau\) and item types \(r\) stay fixed or modest. This makes mass the natural unit for reporting outcomes: what matters is the share of each cohort assigned to each category.

Precisely, an instance gives finite sets \(T\) and \(G\), rational masses \(\mu_t\ge 0\) and supplies \(q_g\ge 0\), with \(\sum_t\mu_t=\sum_gq_g=1\). It also gives each agent type a strict ranking of item types and, in the value version, rational values \(v_t(g)\); or, in the metric version, rational metric costs \(c_t(g)\). Construct finite instances by taking \(N\mu_t\) agents of type \(t\) and \(Nq_g\) copies of item type \(g\), for \(N\) divisible by the mass denominators, and run the paper’s usual RSD.

The continuous question is to compute the exact per capita limit of the expected objective: \(\lim_{N\to\infty}\mathbb{E}[\mathrm{SW}(\mathrm{RSD}(I_N))]/N\), or \(\lim_{N\to\infty}\mathbb{E}[\mathrm{SC}(\mathrm{RSD}(I_N))]/N\). A solution includes the resulting mass allocation \(x_{tg}\), where \(x_{tg}\) is the share of the population of type \(t\) assigned to item type \(g\), as well as the objective \(\sum_{t,g}x_{tg}v_t(g)\) or \(\sum_{t,g}x_{tg}c_t(g)\). Each individual still receives one indivisible item; only the type level allocation is fractional.

The natural candidate for that limit is a deterministic priority flow. Give each agent type a rate \(\mu_t\) over priority time \(u\in[0,1]\). At each point, type \(t\) takes its highest ranked item type with remaining supply. Continue until an item type is exhausted, remove it, and continue with the remaining types and supplies. Between exhaustion events, the rates are constant; there are at most \(r\) such events. This defines \(x\) and the per capita objective by rational arithmetic. The further mathematical obligation is to prove that this flow gives the stated limit of finite RSD expectations. The priority coordinate is bookkeeping for the limit of random agent orderings; the object being continuized is the population.

I expect this question to be Class A: once the limit identity is established, the flow can be computed in time polynomial in \(\tau\), \(r\), and the input bit length. The mirror stays close to the authors’ question because it retains RSD, the assignment process, the same cardinal objective, and the same random priority mechanism in its finite approximants. It asks how that objective behaves per person in a large market of repeated types. The item supplies that scale with the population are a necessary co-modification of the model.

This covers Theorem 1’s value and metric cost branches, and makes no claim about mirroring the paper’s sampling bounds in Theorems 2–5. It also does not claim that the finite #P-hardness disappears for every instance regime. The main follow-up questions are whether the limit identity holds uniformly, what finite-\(N\) error bounds apply, and what changes when \(\tau\) grows with \(N\).

The weakest point is that the theorem’s hardness reduction starts from arbitrary assignment profiles and does not establish hardness in this repeated-type regime. The fluid model may erase the ordering fluctuations that make exact finite-instance expectations hard. That is a real boundary, but it does not undercut this as a mirror: the proposed question is explicitly about the large, repeated-type regime, and it asks about the same expected RSD welfare and cost the paper sets out to assess.