Fair Metric Distortion for Matching with Preferences

The strongest mirror is to keep the paper’s metric-distortion model intact while replacing the named agents and item copies by agent and item mass. The continuity is therefore in the population and seat supply, not in the metric, the outcome space, or the uncertainty model.

Let \(P\) be finitely many agent types and \(Q\) finitely many item types. An instance consists of masses \(\mu_p\) and \(\nu_q\), each summing to \(1\), together with a complete ordinal ranking of \(Q\) for every \(p\in P\). A solution is a transport plan \(x_{pq}\ge 0\) satisfying \(\sum_q x_{pq}=\mu_p\) and \(\sum_p x_{pq}=\nu_q\). Each unit of mass is assigned one item type; \(x\) is a flow, not a lottery experienced by an individual.

For a consistent metric \(d\), the cost distribution induced by \(x\) assigns mass \(x_{pq}\) to distance \(d(p,q)\). Thus the continuous analogues of the paper’s objectives are the total cost \(\Phi_1(x,d)=\sum_{p,q}x_{pq}d(p,q)\), the maximum cost \(\Phi_\infty(x,d)=\operatorname{ess\,sup}_{x_{pq}>0}d(p,q)\), and the top-\(\theta\) cost \(\Phi_\theta(x,d)\), the total distance of the worst \(\theta\)-fraction of matched mass. Define distortion by comparing \(\Phi(x,d)\) with the minimum over all feasible transport plans, then taking the supremum over metrics consistent with the ordinal rankings.

This is a natural high-multiplicity regime for the paper: millions of students divided into a few preference cohorts, and schools or courses represented by many interchangeable seats. A type can mean, for example, students from the same neighbourhood with the same school ranking, or seats at the same campus. The relevant regime is \(N\gg |P|+|Q|\), not merely “matching in general.” Rational masses have an exact two-way dictionary with finite instances: multiply all masses and flows by a common denominator \(N\) to obtain \(N\) named agents and items, and quotient any replicated finite instance back into types.

The paper contains no named NP-hardness, membership-in-\(\mathrm P\), or parameterized-complexity theorem. Its strongest computational content is instead in approximation guarantees and lower bounds for mechanisms. I would use the following three anchors.

The lead anchor is Theorem 2 in §4.1, \(\Cref{thm:mod-rep-match-ub-topk}\), proved in this paper. It states that the size-promotion version of RepMatch guarantees worst-case top-\(k\) distortion \(O\!\left(k^2(n/k)^{\log_2 3}\right)\). The immediately derived consequences are worst-case fairness ratio \(O(n^2)\) and worst-case max-distortion \(O(n^{\log_2 3})\), written in the introduction as \(O(n^{1.58})\).

The corresponding continuous problem is:

*Continuous RepMatch–Top-Mass.* Given \((P,Q,\mu,\nu,\succ)\) and \(\theta\in(0,1]\), run the mass version of RepMatch. Clusters carry agent mass; a representative’s “top \(|S|\) items” becomes the first item mass of size \(\mu(S)\) in that representative’s ranking; two clusters merge when those prefixes overlap in positive item mass; the larger-mass cluster supplies the representative. The output is a feasible transport plan \(x\). Determine the worst-case ratio \(\Phi_\theta(x,d)/\min_y\Phi_\theta(y,d)\) over all consistent metrics and type-mass profiles, and obtain the best bound as a function of \(\theta\), the number of types, and the mass encoding length.

This is recognisably the authors’ problem: it is still ordinal metric matching, still RepMatch’s representative-and-favorite-items idea, and still asks how well an ordinal mechanism approximates the metric optimum. The finite theorem’s proof is encouraging because its central invariant uses cluster sizes, triangle inequalities, and top-\(k\) costs rather than the identities of individual agents. I would expect the fixed-type mass version to be Class A: transport and top-mass objectives are linear programs, and the representative procedure has a finite type-level description. The nontrivial task is to obtain a bound expressed in type parameters rather than by expanding a denominator-\(N\) mass profile into \(N\) individuals.

The second anchor is Theorem 3 in §4.2, \(\Cref{thm:mod-rep-match-lb-topk}\), also proved here. It states that RepMatch with worst-case tie-breaking can produce a matching with worst-case top-\(k\) distortion \(\Omega(kn)\). Its stated corollary is worst-case max-distortion \(\Omega(n)\) and worst-case sum-distortion \(\Omega(n^2)\).

The continuous version is:

*Continuous RepMatch Tie-Breaking Lower Bound.* Given a finite type-mass profile, the size-promotion mass version of RepMatch, and a top-mass parameter \(\theta\), determine the supremum top-\(\theta\) distortion over consistent metrics and permitted tie-breakings. In particular, decide whether the paper’s lower bound survives when repeated agents and items are represented directly by mass.

Here the transfer is especially convincing. In the paper’s construction, take \(N=2^\ell\), agent types \(A_0,\ldots,A_\ell\), and item types \(B_0,\ldots,B_\ell\), with masses \(\mu(A_0)=1/N\), \(\mu(A_t)=2^{t-1}/N\), and the same masses for \(B_t\). There are only \(O(\log N)\) types. The same line metric and rankings make a worst-case tie-breaking send all \(A_\ell\)-mass away from \(B_\ell\). For \(\theta=k/N\), the bad matching has top-\(\theta\) cost at least \(k/2\), while the optimum has top-\(\theta\) cost \(1/N\), giving exactly the finite ratio \(\Omega(kN)\). Thus this obstruction is not caused by having \(N\) unrelated people; its combinatorics live in a logarithmic number of cohorts and metric levels. I expect this anchor to fall in Class B: the lower-bound phenomenon transfers to the continuum rather than dissolving.

The third anchor is Theorem 4 in §5, \(\Cref{thm:max-distortion-lower-bounds}\), proved here. It states that every deterministic matching mechanism has worst-case max-distortion at least \(7\). The proof uses one ordinal instance with eight agents and eight items and eight consistent metrics; whichever item the mechanism assigns to the root item, one of those metrics makes that assignment cost \(7\), while the optimum max cost is \(1\).

The continuous problem is:

*Continuous Deterministic Max-Distortion.* Given a finite ordinal type-mass profile, output a deterministic transport plan using only the masses and rankings. Determine the minimum possible worst-case max-distortion over all such mechanisms, where the adversary chooses a consistent metric after seeing only the ordinal instance.

The lower bound survives with exactly eight agent types and eight item types, each of mass \(1/8\). Duplicate every agent and item in the paper’s construction arbitrarily many times, or directly use the eight mass atoms. The root item has mass \(1/8\), so some positive amount of it must be assigned to some agent type \(p_i\). Choosing the paper’s metric \(d_i\) makes every positive mass assigned from \(p_i\) to the root incur cost \(7\), whereas an optimal transport has maximum cost \(1\). The essential maximum therefore remains at least \(7\). This is again a Class B transfer for the lower bound, while the upper-bound side remains open. The paper’s conjecture that a constant-distortion deterministic mechanism may exist gives a plausible Class A target for the continuous problem.

This mirror covers the paper’s central sum-versus-max question, its RepMatch upper bound, its RepMatch failure mode, and its universal max-distortion lower bound. It does not pretend to continuize the metric space or replace matching by probabilistic social choice. The fractional transport plan is forced by aggregating a large population and a large seat supply; every individual mass element still receives an integral item.

My weakest point is the RepMatch upper-bound anchor. The paper’s proof starts from atomic singleton clusters and uses \(n\) directly in its weight recurrence. A type-compressed nonatomic implementation may alter tie-breaking and may require a new normalization involving the smallest positive type mass. Thus Theorem 2 does not automatically become a denominator-free theorem merely by replacing counts with measures. That is a real technical gap.

It does not undermine the broader mirror. The paper’s setting explicitly includes school and course assignment, the high-multiplicity scenario is convincing there, and Theorem 4 gives an exact continuous lift with only eight types. The honest positive claim is therefore not that every finite bound survives unchanged, but that fair metric matching with ordinal preferences has a well-posed continuous-population version whose main algorithmic question is meaningful, whose lower bounds have genuine high-multiplicity transfers, and whose remaining difficulty is precisely the kind of continuous optimization and type-level mechanism design the ChoCo programme is meant to expose.