Social Welfare in One-Sided Matchings: Random Priority and Beyond

The strongest positive case is a high-multiplicity version of the paper’s main one-sided matching problem. The lead anchor is Theorem 1, proved in this paper rather than cited. It states that, under both unit-range and unit-sum cardinal valuations, random priority has approximation ratio \( \Theta(n^{-1/2}) \). It also states that random priority is asymptotically optimal among truthful-in-expectation mechanisms and among all ordinal mechanisms: no mechanism in either class can achieve better than \(O(n^{-1/2})\).

The continuous mirror is a repeated-market version of one-sided matching. There are finitely many item classes \(M=\{1,\ldots,q\}\), with supply masses \( \rho_j\ge 0 \) satisfying \( \sum_j\rho_j=1 \). There is a finite set \(T\) of complete valuation types. A type \(t\) specifies the agent’s entire normalized valuation vector \(u_t:M\to[0,1]\), or a unit-sum vector, together with its induced strict ranking. A society is a distribution \( \mu\in\Delta(T) \), where \( \mu_t \) is the fraction of agents of type \(t\).

Each unit of agent mass still receives exactly one indivisible item copy. The quantities \(x_{t,j}\) are only aggregate masses: \(x_{t,j}\) is the mass of type \(t\) receiving an item of class \(j\). Feasibility requires \( \sum_j x_{t,j}=\mu_t \) and \( \sum_t x_{t,j}=\rho_j \). Thus the optimal welfare is the transportation-LP value \(W^*(\mu,\rho)=\max_x\sum_{t,j}x_{t,j}u_t(j)\). The fractional object is the description of a large population, not an individual’s bundle.

The natural continuous analogue of random priority is the fluid limit of random serial dictatorship. Take markets with \(N\mu_t\) agents of type \(t\) and \(N\rho_j\) copies of item \(j\), run random priority, divide the expected assignment counts by \(N\), and let \(N\) tend to infinity through values for which all counts are integral. Equivalently, agents have independent uniform priorities in \([0,1]\), and an infinitesimal agent receives its most-preferred item class whose remaining supply is positive. Denote the limiting allocation by \(x^{\mathrm{RP}_\infty}\).

I would name the resulting problem High-Multiplicity One-Sided Matching Welfare:

Given rational valuation types \(T\), a rational item-supply vector \(\rho\), and a society distribution \(\mu\), compute the welfare \(W(x^{\mathrm{RP}_\infty})\) and compare it with \(W^*(\mu,\rho)\). In the mechanism-design version, compute the worst-case ratio of \(x^{\mathrm{RP}_\infty}\) over all \(\mu\), and determine whether any anonymous ordinal continuum mechanism, or any limit of truthful-in-expectation finite mechanisms, achieves a larger worst-case ratio. A solution consists of an allocation kernel \(x_{t,j}\), its welfare ratio \(W(x)/W^*\), and, for the mechanism-design version, either a mechanism with the claimed guarantee or a matching impossibility certificate.

This is recognisably the authors’ problem. It retains one-sided assignment, indivisible items, unrestricted cardinal utility subject to canonical normalization, aggregate social welfare, random priority, ordinal mechanisms, and truthful-in-expectation mechanisms. The only forced co-modification is that one item becomes a repeated item class with per-capita supply. That is precisely what a high-multiplicity matching market means; it is not a switch to divisible outcomes. A plausible regime is school or housing allocation: millions of applicants fall into a few preference-and-utility cohorts, while each school or housing category has many equivalent seats. Here \(N\) is very large, \(q\) and \(\tau=|T|\) are moderate, and agents of the same type are genuinely indistinguishable for the mechanism.

For this mirror I expect the fixed-instance computation to be Class A. The optimum is a transportation LP with \(O(q\tau)\) variables. The fluid random-priority allocation can be computed by sweeping through the at most \(q\) events at which an item class is exhausted; between events, the type masses choosing each currently available class are fixed. Thus its welfare is computable by a finite piecewise-linear calculation. The harder follow-up is the global optimization over all societies and all ordinal mechanisms. That may expose a continuum-specific boundary, especially when \(q\) and \(\tau\) are part of the input.

The paper’s \(n^{-1/2}\) expression should not simply be copied into the mirror. In the continuous regime there is no population-size parameter left: \(N\) has become a scale, while \(q\) and \(\tau\) describe the actual combinatorial instance. The paper’s lower-bound profiles use many individually distinguished items and carefully arranged agent types, so their exact asymptotics may disappear when there are only finitely many item classes. That is the weakest point of the case. A referee could reasonably say that the mirror changes the asymptotic object too much to preserve Theorem 1 numerically.

But that is also the substantive question the continuization programme is designed to ask: does the paper’s welfare loss come from the underlying matching problem, or from one-copy-per-item and one-agent-per-label multiplicity? The continuous problem tests whether the \( \Theta(n^{-1/2}) \) barrier survives as a structural limitation, collapses under high multiplicity, or is replaced by a new dependence on \(q\), \(\tau\), and \(\rho\). Further questions include whether fluid random priority remains optimal among ordinal mechanisms, whether truthful-in-expectation imposes an additional loss, and how quickly finite repeated markets converge to the continuum allocation.