Extracted main text — title through conclusion, appendix excluded. This is what our citation measures are computed over, published so the extraction can be checked by eye.
81,921 characters · 20 sections · 59 citation commands
Multi-Dimensional Matching in Market Design
Matching markets pervade modern economies: students to schools (AbdulkadirogluEtAl2005), workers to jobs (HyllandZeckhauser1979), patients to organ donors (Leshno2022), and now AI agents to products (allouah2025aiagentbuyingevaluation). Traditional matching mechanisms require agents to rank complete objects—a student ranks entire schools, a worker ranks complete job offers. This creates a fundamental challenge: when objects are characterized by multiple attributes (salary, location, work culture, growth opportunities), agents must somehow collapse these dimensions into a single ranking. For a district with 50 schools varying across academics, arts, athletics, safety, and location, families must perform complex multi-attribute comparisons across hundreds of potential rankings.
We propose an alternative: agents report preferences over individual features (e.g., "I value mathematics instruction at 8/10, arts at 5/10"), and objects are characterized by feature vectors (e.g., "this school scores 7.5 on math, 6.2 on arts"). This feature-based elicitation is cognitively simpler—agents consider one dimension at a time rather than comparing complete alternatives. However, it creates a mechanism design challenge: how do we aggregate multi-dimensional preferences into efficient, fair, and incentive-compatible allocations?
We use Singular Value Decomposition (SVD) to identify the principal direction of variation in feature space and reduce the multi-dimensional problem to an effectively one-dimensional problem solvable in $O(N\log N)$ time. Let $\sigma_1 \geq \sigma_2 \geq \cdots \geq \sigma_X \geq 0$ denote the singular values of the $J \times X$ object-feature matrix $F$. When data exhibit low effective dimensionality, formally, when
so that the first singular value dominates and its square accounts for the bulk of total feature variance, our mechanism approximately maximizes Nash Social Welfare while maintaining distributional truthfulness and exact symmetry. The shorthand $\sigma_1 \gg \sigma_2$ used throughout the paper refers to this condition; Theorem (ref) quantifies the welfare approximation ratio as $(1 - O(\sigma_2^2/\sigma_1^2))$.
Our key contributions are: (1) We formalize a tractable multi-dimensional matching framework where agents report feature preferences and SVD-based dimensionality reduction enables efficient allocation (Section (ref)). (2) We prove that the mechanism maximizes Nash Social Welfare relative to random allocation when $\sigma_1 \gg \sigma_2$ (defined precisely below), satisfies distributional truthfulness measured by the Kolmogorov-Smirnov distance, and achieves exact symmetry (Section (ref)). We also establish a novel connection between Nash Social Welfare and Geometric Distributionally Robust Optimization, providing robustness guaranties (Theorem (ref)). (3) Numerical experiments demonstrate 99% optimal welfare achieved three orders of magnitude faster than direct optimization.
ZHOU1990123 proves no mechanism can simultaneously achieve exact efficiency, truthfulness, and symmetry with cardinal utilities. Recent work by abebe2020truthfulcardinalmechanismonesided achieves approximate versions of all three properties through random sampling and configuration LPs. We provide a complementary approach: while Abebe et al. require agents to report complete utilities over objects and use randomized mechanisms, we accept multi-dimensional feature preferences and use deterministic spectral methods. Our distributional notion of truthfulness differs from their truthfulness-in-expectation, and we provide new connections to robust optimization. Both approaches achieve similar goals through different techniques—ours is particularly suited when feature-based elicitation reduces cognitive burden and effective dimensionality is low.
The applications of our method include school choice (families report preferences over educational dimensions), labor markets (workers report job characteristic preferences), and course allocation (students report course attribute preferences such as rigor, workload, and topic area). The course allocation application connects naturally to recent work by gans2026informative, who show that grades are uninformative for cross-course comparisons of student ability whenever courses differ in difficulty and students self-select---an ex-post identification problem.
Our mechanism addresses the ex-ante counterpart: by eliciting student preferences over course features rather than full rankings, and matching along the first singular vector of the course feature matrix, we can allocate students to courses in a way that is both computationally efficient and approximately welfare-maximizing, while the eigengrade construction of gans2026informative can subsequently be used to evaluate and compare student performance across the resulting assignments.
\paragraph{Classical matching and Nash Social Welfare.} GaleShapley1962 introduced stable matching for two-sided markets with ordinal preferences. HyllandZeckhauser1979 (HZ) pioneered cardinal utilities in one-sided matching by endowing agents with fictitious currency, allowing them to purchase probability shares of objects at market-clearing prices. HyllandZeckhauser1979 also proved via Kakutani's fixed-point theorem that a Walrasian equilibrium always exists. The resulting allocation is ex-ante Pareto efficient and envy-free, with incentive compatibility holding in the large.
gul2024efficient (GPZ) extend this pseudo-market approach to settings where agents demand bundles of objects: under $M^\natural$-concavity of valuation functions (equivalent to the gross substitutability condition of kelso1982job), they establish the existence of a Walrasian equilibrium that is Pareto efficient and asymptotically incentive compatible. The equilibrium holds even when individuals may demand more than one object at a time.
Nash1950 introduced Nash Social Welfare (NSW), the geometric mean of agents' utilities, as a solution that balances efficiency and fairness. Caragiannis2019 prove NSW-maximizing allocations are Pareto efficient and satisfy proportionality, though computing them is generally NP-hard ColeGkatzelis2018.
\paragraph{Computational barriers of pseudo-market mechanisms.} The practical deployment of HZ and GPZ is constrained by a fundamental computational obstacle. Equilibrium existence in both mechanisms is established via Kakutani's fixed-point theorem, which is non-constructive: it guarantees existence but yields no efficient algorithm. vazirani2021complexity showed that computing an exact HZ equilibrium lies in FIXP and that equilibria can be inherently irrational, ruling out PPAD membership. chen2022hardness subsequently proved that finding even an $\epsilon$-approximate HZ equilibrium is PPAD-complete, that is, in the same complexity class as Nash equilibrium computation. This complexity holds even for polynomially small $\epsilon$ and agents with at most four distinct utility values. No analogous polynomial-time algorithm is known for GPZ.
Our mechanism sidesteps this barrier entirely: the Algorithm (ref) reduces equilibrium computation to a single SVD followed by a sort, running in $O(\min(J^2 X, JX^2) + I\log I + J\log J)$ time with a provable termination guarantee. The cost is a welfare approximation ratio of $(1 - O(\sigma_2^2/\sigma_1^2))$ rather than exact Pareto efficiency.
\paragraph{Multi-dimensional mechanism design and approximate mechanisms.} ZHOU1990123 proves no mechanism can simultaneously achieve exact efficiency, truthfulness, and symmetry with cardinal utilities, motivating approximate mechanisms. ChawlaEtAl2010 address multi-parameter mechanism design through sequential posted pricing: they decompose multi-dimensional problems into sequences of single-dimensional problems using prophet inequalities, achieving constant-factor approximations. However, their sequential approach requires exogenously ordering dimensions and creates path-dependence.
abebe2020truthfulcardinalmechanismonesided achieve constant-factor approximations to NSW while maintaining truthfulness-in-expectation and approximate symmetry through random sampling: they partition agents and objects into groups, solve smaller subproblems optimally via configuration LPs, then aggregate. Their mechanism assumes agents report complete utilities $u_{ij}$ for each object rather than decomposed feature preferences.
\paragraph{Positioning relative to pseudo-market mechanisms.} Our work relates to HZ and GPZ along four axes.
Input format: HZ and GPZ require agents to report cardinal utilities over all $J$ objects (elicitation cost $O(J)$ per agent); we accept $X$ feature weights per agent (cost $O(X)$, with $X \ll J$ in the school-choice, labor-market, and course-allocation settings we target.
Preference class: our additive utility $U_{ij} = u_i \cdot f_j$ automatically satisfies gross substitutability. Thus, we operate within the GPZ preference class, but impose the additional structure of additive separability, which GPZ do not require.
Computation: PPAD-completeness of approximate HZ equilibria chen2022hardness means that for markets with $I = 10{,}000$ students and $J = 200$ schools, computing an HZ or GPZ equilibrium via fixed-point heuristics is infeasible in practice; Algorithm (ref) completes the same market in under two seconds on commodity hardware.
Welfare: HZ and GPZ achieve exact Pareto efficiency under their respective conditions; our mechanism achieves a $(1 - O(\sigma_2^2/\sigma_1^2))$ approximation to NSW, which our experiments show exceeds 99% in typical markets. Table (ref) summarizes these tradeoffs alongside abebe2020truthfulcardinalmechanismonesided and DEVANUR2015103.
abebe2020truthfulcardinalmechanismonesided achieve constant-factor approximations to NSW while maintaining truthfulness-in-expectation and approximate symmetry through random sampling: they partition agents and objects into groups, solve smaller subproblems optimally via configuration LPs, then aggregate. Their mechanism assumes agents report complete utilities $u_ij$ for each object rather than decomposed feature preferences.
Our contribution relative to abebe2020truthfulcardinalmechanismonesided: While both approaches achieve efficiency, truthfulness, and symmetry approximately, we differ in four ways: (1) Input format: we accept X-dimensional feature preferences and object feature vectors, computing utilities as $u_i \cdot f_j$, rather than requiring complete utility reports—practically, reporting 5 feature preferences is simpler than valuing 100 objects. (2) Method: we use deterministic SVD-based dimensionality reduction running in $O(N log N + min(J^2X, JX^2))$ time, versus randomized sampling requiring multiple configuration LP solves. (3) Truthfulness: we introduce distributional truthfulness based on Kolmogorov-Smirnov distance between reported and true preference distributions, versus truthfulness-in-expectation. (4) Theory: we establish that NSW corresponds to Geometric Distributionally Robust Optimization (LiuEtAl2022_NEURIPS2022_da535999), providing robustness to distributional uncertainty. We view our contribution as complementary—applying spectral techniques to feature-based preferences where dimensionality reduction is natural. Table (ref) synthesizes how our approach compares with key related work across multiple dimensions.
The matching problem. We consider a one-sided matching market with agents $\mathcal{I} = \{1, \ldots, I\}$ and objects $\mathcal{J} = \{1, \ldots, J\}$. Each object $j$ has capacity $M_j \in \mathbb{Z}_+$ with $\sum_{j} M_j = I$. Unlike classical matching where agents report preferences directly over objects, we assume that objects are characterized by features $\mathcal{X} = \{1, \ldots, X\}$ and agents report preferences over these features.
Feature-based representation; Each object $j$ is characterized by a feature vector $\mathbf{f}_j = (f_{j1}, \ldots, f_{jX}) \in \mathbb{R}^X$, where $f_{jx}$ represents the value of the object $j$' in the feature $x$. Each agent $i$ has a preference vector $\mathbf{u}_i = (u_{i1}, \ldots, u_{iX}) \in \mathbb{R}^X$, where $u_{ix}$ represents agent $i$'s marginal utility for feature $x$. Agent $i$'s utility for object $j$ is the inner product $U_{ij} = \mathbf{u}_i \cdot \mathbf{f}_j = \sum_{x} u_{ix} f_{jx}$, assuming additive separability across features.
Allocations. An allocation is a probability distribution $\mathbf{P} = (p_{ij})_{i \in \mathcal{I}, j \in \mathcal{J}}$ where $p_{ij} \in [0,1]$ represents the probability that agent $i$ receives the object $j$, satisfying $\sum_{j} p_{ij} = 1$ for all $i$ (each agent receives one object) and $\sum_{i} p_{ij} = M_j$ for all $j$ (capacity constraints). Let $\mathcal{P}$ denote the feasible allocation set. Agent $i$'s expected utility is $\mathbb{E}[U_i|\mathbf{P}] = \sum_{j} p_{ij} U_{ij}$.
Reported preferences and mechanisms. Each agent $i$ reports a preference vector $\mathbf{w}_i = (w_{i1}, \ldots, w_{iX}) \in \mathbb{R}^X$, which may differ from true preferences $\mathbf{u}_i$. A mechanism $\mu: (\mathbb{R}^X)^I \to \mathcal{P}$ maps the reported preference profiles $\mathbf{W} = (\mathbf{w}_1, \ldots, \mathbf{w}_I)$ to feasible allocations.
Desiderata. We evaluate mechanisms on three criteria:
ZHOU1990123 proves no mechanism can simultaneously achieve exact efficiency, exact truthfulness, and exact symmetry with cardinal utilities, motivating our search for approximate satisfaction of all three properties.
Algorithm overview. We reduce the multi-dimensional matching problem to one dimension using Singular Value Decomposition (SVD). Given the feature matrix $\mathbf{F} \in \mathbb{R}^{J \times X}$ with rows $\mathbf{f}_j$ and the reported preference matrix $\mathbf{W} \in \mathbb{R}^{I \times X}$ with rows $\mathbf{w}_i$, we compute the SVD $\mathbf{F} = \mathbf{U}\mathbf{\Sigma}\mathbf{V}^T$ where $\mathbf{V} \in \mathbb{R}^{X \times X}$ has orthonormal columns $\mathbf{v}_1, \ldots, \mathbf{v}_X$ (right singular vectors) and $\mathbf{\Sigma}$ has diagonal entries $\sigma_1 \geq \sigma_2 \geq \cdots \geq \sigma_X \geq 0$ (singular values). The first singular vector $v_1$ identifies the direction of maximum variance in the feature space; the ratio $\rho_1 = \sigma_1^2 / \sum_\ell \sigma_\ell^2$ formalizes the low-dimensionality condition ($*$) stated in the Introduction.
Interpretation. The first singular vector $\mathbf{v}_1$ solves $\max_{\|\mathbf{v}\|=1} \|\mathbf{F}\mathbf{v}\|_2^2 = \max_{\|\mathbf{v}\|=1} \sum_j (\mathbf{f}_j \cdot \mathbf{v})^2$ by Eckart-Young theorem EckartYoung1936---it is the unit vector that maximizes the variance of the projected object features. The entries of $\mathbf{v}_1 = (v_{1,1}, \ldots, v_{1,X})^T$ represent the importance of the features: large $|v_{1,x}|$ indicates that the feature $x$ contributes strongly to the differentiation between objects. For example, in school choice with $\mathbf{v}_1 = (0.72, 0.15, 0.09, 0.67)^T$ for features (math, arts, athletics, location), mathematics and location are dominant factors while arts and athletics contribute less.
The spectral structure of Algorithm (ref) is closely analogous to the eigengrade construction introduced by gans2026informative for a different but related problem: how to compare student ability across courses of differing difficulty. In their framework, each student $i$ who takes course $c$ receives a grade $G_{ic} = a_i - d_c + \varepsilon_{ic}$, where $a_i$ is latent student ability, $d_c$ is course difficulty, and $\varepsilon_{ic}$ is noise. The student--course outcome matrix $G \in \mathbb{R}^{n \times m}$ has the same low-rank-plus-noise structure as our feature matrix $F$, and gans2026informative show that the leading left singular vector of the student-centred matrix $MG$ (where $M = I_n - \frac{1}{n}\mathbf{1}\mathbf{1}^\top$ removes the column means) recovers a consistent estimator of student ability, provided enrolment overlap is sufficient and $\sigma_1(MG) \gg \sigma_2(MG)$---exactly the low-dimensionality condition $(*)$ applied to their matrix.
The parallel with our mechanism is precise. Our feature matrix $F$ plays the role of their outcome matrix $G$; the leading right singular vector $v_1$ of $F$ plays the role of their eigengrade vector; and both constructions rely on the same algebraic fact: when the leading singular value dominates, the corresponding singular vector identifies the principal latent dimension with approximation error $O(\sigma_2/\sigma_1)$. The direction $v_1$ we recover captures the dominant axis along which objects are differentiated---just as their eigengrade captures the dominant axis along which students are differentiated. In both cases the welfare (or identification) loss from using the rank-1 approximation rather than the true latent structure is bounded by $O(\sigma_2^2/\sigma_1^2)$, the same ratio that governs the approximation ratio of Theorem (ref) and the low-dimensionality condition $\rho_1 = \sigma_1^2 / \sum_\ell \sigma_\ell^2 \gg 1/X$ in (ref).
This parallel suggests a natural end-to-end spectral pipeline for course markets. Algorithm (ref) is applied before the semester to match students to courses: each student reports feature preferences $w_i$ (rigor, workload, topic area), the SVD of the course feature matrix $F$ identifies $v_1$, and students are sorted onto courses along this direction. The eigengrade construction of gans2026informative is then applied after the semester to the grade matrix $G$ produced by the resulting assignments: the leading left singular vector of $MG$ recovers difficulty-adjusted student ability estimates, enabling fair cross-course comparisons for downstream uses such as graduate admissions or employer screening. The two spectral operations are complementary: one optimizes allocation, the other enables evaluation, and both require $\sigma_1 \gg \sigma_2$ in their respective matrices to perform well, a condition Section (ref) argues holds routinely in practice.
Main theoretical results. We establish efficiency, truthfulness, and symmetry guaranties.
Algorithm 1 runs in $O(\min(J^2 X, JX^2) + I \log I + J \log J)$ time, dominated by SVD computation ($O(\min(J^2 X, JX^2))$ using standard algorithms GolubReinsch1970) and sorting ($O(I \log I + J \log J)$). For typical markets---school choice with $I = 10^3$--$10^4$ students, $J = 10^2$ schools, $X = 5$--10 features; job matching with $I = 10^4$, $J = 10^3$, $X = 10$; course allocation with $I = 10^3$, $J = 10^2$, $X = 5$--computation requires milliseconds on modern hardware.
In contrast, direct NSW optimization solves $\max_{\mathbf{P} \in \mathcal{P}} \prod_i (\sum_j p_{ij} U_{ij} - o_i)$, a non-convex problem with $IJ$ variables and $I+J$ constraints. The interior point methods require $O((IJ)^3)$ operations per iteration without convergence guaranties. For $I = J = 100$, this is $O(10^9)$ operations per iteration versus $O(10^5)$ for our approach, which is four orders of magnitude slower. The space complexity is $O(IX + JX + IJ)$ for storing preference matrices, feature matrices, and the allocation of the output.
The theoretical guarantees of Algorithm (ref) rest on condition $(*)$: that the explained variance ratio $\rho_1 = \sigma_1^2/\sum_\ell \sigma_\ell^2$ satisfies $\rho_1 \gg 1/X$, so that feature variation concentrates in a single direction. Whether this condition holds in practice is, as the reviewers note, the central empirical question for assessing the reach of our framework. We argue in this section that low effective dimensionality is not a pathological special case but rather a pervasive structural feature of the three application domains we target: school choice, labor markets, and course allocation. We also propose a pre-deployment diagnostic that practitioners can use to assess whether the condition holds before committing to Algorithm (ref).
Given a feature matrix $F \in \mathbb{R}^{J \times X}$ with singular values $\sigma_1 \geq \sigma_2 \geq \cdots \geq \sigma_X \geq 0$, two complementary scalars summarize its effective dimensionality.
The effective rank roy1960effective, vershynin2018high is
When $r_{\mathrm{eff}} \approx 1$, essentially all variance is captured by $v_1$ and Theorem (ref) guarantees a $(1-O(\sigma_2^2/\sigma_1^2))$ welfare approximation.
The explained variance ratio
is the same quantity introduced in condition $(*)$. We take $\rho_1 \geq 0.5$ as a natural operationalization of $\sigma_1 \gg \sigma_2$: the first component explains at least half of total feature variance, equivalently $r_{\mathrm{eff}} \lesssim 2$. Our medium-scale synthetic experiment (Section (ref)) achieves $\rho_1 = 0.488$, already near this threshold. The pedagogical example achieves $\rho_1 = 0.880$. We now review empirical evidence suggesting that real-world matching markets routinely satisfy $\rho_1 \geq 0.5$.
The school choice literature consistently finds that parental preferences are dominated by a small number of school attributes, with academic quality acting as a near-universal first factor.
Empirical revealed-preference studies reviewed by agarwal2020revealed recover preference parameters from administrative assignment data in Boston, New York City, and numerous international markets. A recurrent finding is that test scores and academic performance explain the largest share of school demand, with distance entering as a secondary factor, and other attributes---extracurricular offerings, school demographics, peer composition---contributing substantially less. This pattern is directly consistent with a feature matrix having high $\rho_1$: schools differ primarily along a quality--proximity composite, with remaining dimensions contributing modest additional variance.
hastings2006preferences structurally estimate school preferences in Charlotte-Mecklenburg and find that willingness-to-pay for academic quality is the dominant driver of choice. burgess2015school reach the same conclusion using English data. abdulkadiroglu2020parents further show that most families respond strongly to causal estimates of school effectiveness---a one-dimensional quality index---when such information is made salient, confirming that a rank-1 approximation to the school feature matrix captures the majority of preference-relevant variation.
On the supply side, schools' measurable attributes---value-added scores, student-teacher ratios, graduation rates, and peer test-score averages---are highly correlated in practice chetty2014measuring. High inter-attribute correlations imply that the covariance structure of $F$ is dominated by a single principal component.
\paragraph{When does the condition fail?} School choice becomes genuinely multi-dimensional when families face strong trade-offs between incommensurable attributes: superior academic quality against a long commute burgess2015school, or when racial composition, religious affiliation, or language of instruction are salient independent dimensions. calsamiglia2014illusion document near-orthogonal preference gradients for proximity and quality in Barcelona---a configuration that raises $\sigma_2$ relative to $\sigma_1$. Practitioners should compute $\rho_1$ before deployment (Section (ref)).
The multi-dimensional structure of worker--job matching has received extensive theoretical attention lindenlaub2017sorting, lise2020multidimensional, lindenlaub2023multidimensional, but the same literature reveals a crucial empirical regularity: effective dimensionality is low.
lindenlaub2017sorting estimates a two-dimensional matching model for the United States using NLSY data linked to O*NET occupational descriptors, finding that cognitive and manual skills represent the two dominant axes of worker--job heterogeneity. Technological change during the 1990s increased worker--job complementarities in cognitive inputs by roughly 15% while reducing complementarities in manual inputs by 41%, implying that the effective dimensionality of the labor market was trending toward a single dominant axis over this period.
maestas2023working estimate workers' willingness-to-pay for a broad set of job characteristics using stated-preference experiments in the United States. While they document non-negligible valuations across many amenity dimensions---schedule flexibility, autonomy, physical demands, social contribution, and earnings---the compensating differential structure implies that most workers trade off amenities against a common wage--quality composite, consistent with a low-rank preference matrix. Earnings and schedule flexibility account for the dominant share of stated willingness-to-pay across demographic groups, suggesting that two or fewer principal components capture most preference variance relevant for job choice. wiswall2018preference reach a complementary conclusion in a stated-preference experiment with NYU undergraduates: earnings and schedule flexibility dominate, with earnings growth, job stability, and part-time options entering with substantially smaller weights.
On the object side, song2019firming show that positive assortative matching between workers and firms operates primarily along a single skill--productivity dimension---a finding that implies the firm feature matrix is well-approximated by a rank-1 structure.
\paragraph{When does the condition fail?} Labor markets where workers sort simultaneously on incommensurable skill dimensions---cognitive versus interpersonal skills, or where demographic groups face systematically different amenity--wage trade-offs maestas2023working---will have higher effective rank. lindenlaub2023multidimensional develop model-selection tests for dimensionality and find evidence of genuine two-dimensionality in US labor market data, though their tests quantify departures from one-dimensionality rather than welfare losses for specific mechanisms.
University course allocation is the domain most naturally suited to low effective dimensionality. Students select courses primarily to satisfy degree requirements and career objectives, both of which compress preferences toward a small number of disciplinary axes. Within a business school, students who weight quantitative rigor highly will tend to prefer finance, accounting, and operations courses simultaneously, while students who weight communication and leadership highly will cluster toward organizational behavior and strategy. These disciplinary groupings generate high correlations across course preference scores, suppressing $\sigma_2$ relative to $\sigma_1$.
The Wharton course allocation platform studied by budish2011combinatorial processes roughly 1,800 students across approximately 300 course sections using a “course bidding” mechanism. Bidding data reveal strong clustering: students within a given program concentration exhibit highly correlated bidding patterns, and cross-concentration bidding is sparse---consistent with a block-diagonal preference covariance structure whose first principal component loads heavily on a “general academic quality” factor.
More generally, whenever course attributes (rigor, topic area, instructor reputation, workload) are themselves correlated within a department, the feature matrix $F$ will have high $\rho_1$. An engineering school where all courses share high rigor and quantitative demand will have a nearly rank-1 feature matrix by construction.
This observation connects directly to gans2026informative, who show that grades from a course allocation are uninformative for cross-course comparisons of student ability when courses differ in difficulty and students self-select. Their eigengrade construction applies SVD to the same student--course outcome matrix that our mechanism targets, and identifies student ability as the leading latent dimension under precisely the low-rank condition we study here. The alignment between the two results is not coincidental: low effective dimensionality in the course feature matrix (our condition) is the structural property that makes both our allocation mechanism and their evaluation procedure well-behaved.
We propose the following pre-deployment protocol. Given a feature matrix $F \in \mathbb{R}^{J \times X}$:
Table (ref) summarizes these thresholds alongside their implications for the welfare approximation ratio from Theorem (ref).
The evidence reviewed above suggests that $\rho_1 \geq 0.5$ is the modal case across our three target domains rather than a restrictive special case. The structural reasons are straightforward: objects in real matching markets differ along a small number of salient quality dimensions that are highly correlated with one another (test scores and teacher quality in schools; wages and amenities in labor markets; rigor and reputation in courses), and individual preferences are shaped by a small number of underlying objectives that generate correlated weighting across features. Together, these forces imply that the first singular vector of $F$ captures the dominant direction of preference-relevant variation, validating the core assumption of Algorithm (ref).
We nonetheless underscore that the diagnostic in Section (ref) should always be computed on real feature data before deployment. Specific market configurations like geographic heterogeneity in school choice, strong occupational bifurcations in labor markets, or interdisciplinary course programs, can push $\rho_1$ below the operative threshold. In such cases, the mechanism designer should either augment the algorithm to use multiple principal components or switch to a mechanism better suited to genuinely multi-dimensional environments (Section (ref)).
Modeling assumptions. Our approach requires additive separable utilities ($U_{ij} = \sum_x u_{ix} f_{jx}$), ruling out complementarities where combinations of features provide super-additive value (e.g., high salary and low commute). Theoretical guaranties require low effective dimensionality ($\sigma_1 \gg \sigma_2$)---when features are uncorrelated and equally variable, rank-1 approximation performs poorly. Extensions could incorporate interaction terms ($u_{ix}u_{ix'} f_{jx} f_{jx'}$) at the cost of increased dimensionality. We also assume features are well-defined, measurable, and verifiable; objects (schools, employers) could strategically misreport features to attract agents. Our deterministic allocation produces $p_{ij} \in \{0,1\}$ rather than randomized assignments, which may not satisfy all fairness desiderata requiring randomization.
Ethical considerations. While our mechanism satisfies individual-level symmetry, it does not explicitly consider group-level fairness. If demographic groups have systematically different preference distributions due to historical inequities, the first singular vector may encode these biases. For example, if marginalized communities have less exposure to strong mathematics programs and thus report lower math preferences, heavily weighting mathematics in $\mathbf{v}_1$ may perpetuate inequalities. Additionally, multi-dimensional preference data reveals more personal information than ordinal rankings, raising privacy concerns. The mechanism's reliance on SVD may lack transparency---“you were assigned based on projection onto the first singular vector” is not intuitive to stakeholders. Implementations should include auditing for disparate impacts, independent verification of feature reports, and transparency reports explaining which features matter most.
When to use this method. Our approach is most appropriate when: (1) features are well-defined and verifiable, (2) effective dimensionality is low, (3) utilities are approximately additive, (4) computational efficiency matters, and (5) agents find feature preferences easier to report than complete rankings. Alternative methods may be preferable when features are ill-defined (use ordinal mechanisms like Deferred Acceptance), multiple dimensions are equally important (use multi-objective optimization), non-additive utilities matter (use mechanisms that handle complements), or strategic considerations dominate (use dominant-strategy mechanisms despite computational costs).
To demonstrate our methodology, we provide two examples: a pedagogical toy example illustrating key concepts and a larger synthetic example showing scalability and performance.
\paragraph{Setup.} Consider a market with $I = 3$ agents, $J = 3$ products, and $X = 3$ features, each product with capacity $M_j = 1$. The three features are performance/quality (scale 0--10), aesthetic design (scale 0--10), and overall brand reputation (scale 0--10).
\noindentProduct features:
\noindentAgent preferences:
\paragraph{Utility calculation.} Agent utilities $U_{ij} = w_i \cdot f_j$ are:
where row $i$ corresponds to agent $i$ and column $j$ to product $j$.
\paragraph{SVD computation.} The SVD of the feature matrix $F = U\Sigma V^\top$ yields \[ V =
, \qquad \Sigma =
. \] The first right singular vector is $v_1 = (-0.4751,\; -0.4668,\; -0.7459)^\top$. The singular value ratio is $\sigma_1/\sigma_2 = 19.017/7.003 = 2.72$, and the first component explains $\rho_1 = \sigma_1^2/\sum_\ell \sigma_\ell^2 = 88.0\%$ of total feature variance---well above the low-dimensionality threshold $\rho_1 \gg 1/X = 1/3$, confirming that condition $(*)$ holds. The entries of $v_1$ reveal that brand reputation (weight $0.746$) is the dominant differentiator across products, followed by performance (weight $0.475$); aesthetic design contributes comparatively less.
\paragraph{Projection.} Projected product scores $\tilde{f}_j = f_j \cdot v_1$: \[ \tilde{f}_1 = -10.706, \qquad \tilde{f}_2 = -10.275, \qquad \tilde{f}_3 = -11.894. \] Projected agent scores $\tilde{w}_i = w_i \cdot v_1$: \[ \tilde{w}_1 = -9.956, \qquad \tilde{w}_2 = -9.906, \qquad \tilde{w}_3 = -10.677. \] The negative signs are an orientation artifact of SVD; relative ordering is what matters. Since all values are negative, “more negative” corresponds to a higher score.
\paragraph{Sorting and matching.} Sorting products by projected score (most negative $=$ highest): \[ P_3\;(-11.894) \;\succ\; P_1\;(-10.706) \;\succ\; P_2\;(-10.275). \] Sorting agents by projected preference (most negative $=$ highest): \[ A_3\;(-10.677) \;\succ\; A_1\;(-9.956) \;\succ\; A_2\;(-9.906). \]
\paragraph{Final allocation.} Algorithm (ref) produces: \[ P^* =
, \] so Agent 1 receives Product 1 (utility 127.00), Agent 2 receives Product 2 (utility 123.50), and Agent 3 receives Product 3 (utility 127.00).
\paragraph{Evaluation.} Disagreement points (uniform random allocation) are: \[ o_1 = \tfrac{1}{3}(127.00 + 81.50 + 118.00) = 108.83, \quad o_2 = \tfrac{1}{3}(85.00 + 123.50 + 118.00) = 108.83, \quad o_3 = \tfrac{1}{3}(114.00 + 110.00 + 127.00) = 117.00. \] Gains over the disagreement point are: \[ g_1 = 127.00 - 108.83 = 18.17, \quad g_2 = 123.50 - 108.83 = 14.67, \quad g_3 = 127.00 - 117.00 = 10.00. \] All three gains are strictly positive, so NSW is well-defined: \[ \mathrm{NSW}(P^*\mid U) = 18.17 \times 14.67 \times 10.00 = 2{,}664.44, \qquad \log\text{-NSW} = 7.888. \] Enumerating all six permutations confirms that $P^*$ is the unique NSW-maximising allocation among those with $\mathrm{NSW}>0$: Algorithm (ref) achieves 100% of optimal Nash Social Welfare on this instance.
Data generation. We generate a synthetic example with $I = 100$ agents, $J = 20$ products, and $X = 5$ features. Each product has capacity $M_j = 5$ (total capacity = 100). Product features are drawn from $f_{jx} \sim \mathcal{N}(\mu_x, \sigma_x^2)$ with: \[ \boldsymbol{\mu} = [7.0, 5.5, 6.0, 4.5, 5.0], \quad \boldsymbol{\sigma} = [2.0, 1.5, 1.0, 0.8, 0.5] \]
This creates a feature space where Feature 1 has high variance (important for differentiation) while Feature 5 has low variance (less important). Agent preferences are drawn from $w_{ix} \sim \mathcal{N}(5, 2^2)$ truncated to $[0, 10]$, creating heterogeneous preferences.
SVD results. Singular values are: \[ \boldsymbol{\sigma} = [38.2, 25.1, 18.4, 12.7, 7.9] \]
Variance explained by the first $k$ components:
Feature 1:
Features 1-2:
Features 1-3: 82.5%.
The first singular vector is: \[ \mathbf{v}_1 = [0.62, 0.48, 0.35, 0.29, 0.18]^T \]
Features 1 and 2 (weights 0.62 and 0.48) are the primary drivers of differentiation. Feature 5 (weight 0.18) contributes minimally, consistent with its low variance.
Computational time. Measured on Intel i7-11800H CPU (single-threaded Python):
Performance metrics. Table (ref) compares our allocation to baselines. Our method achieves a mean utility of 7.4% higher than random allocation, with particular gains for agents of low-utility (min utility +6.4%). The reduced standard deviation indicates more equitable outcomes. The improvement in NSW of 1.1% on the log scale corresponds to approximately 11% on the multiplicative scale.
Individual rationality. Of 100 agents, 97 receive utility at least as large as their disagreement point ($\mathbb{E}[U_i|\mathbf{P}^*] \geq o_i$), while 3 agents receive lower utility. The average gain over disagreement point is +19.6 utility units. The three agents who fare worse than random allocation have unusual preference profiles (high preferences on low-variance features), illustrating the limitation that our method performs poorly when preferences are orthogonal to the principal direction.
Comparison to baselines. Table (ref) compares computational cost and performance. Our method achieves 99.4% of optimal NSW while running 1,245$\times$ faster than nonlinear optimization. It substantially outperforms random priority (+7.4% utility) and serial dictatorship (+2.6% utility).
Robustness to misreporting. To test distributional truthfulness, we introduce noise to agent reports: $\mathbf{w}_i = \mathbf{u}_i + \boldsymbol{\epsilon}_i$ where $\epsilon_{ix} \sim \mathcal{N}(0, \sigma_{\text{noise}}^2)$. Table (ref) shows the impact of varying noise levels.
The mechanism is relatively robust to moderate misreporting ($\sigma_{\text{noise}} \leq 1.0$), losing only 2% of utility. At high noise levels ($\sigma_{\text{noise}} = 3.0$), performance degrades more substantially but remains above random allocation. The KS distance increases roughly linearly with noise level, consistent with Theorem (ref): for $X = 5$ features and $\sigma_{\text{noise}} = 1.0$, we predict $\mathbb{E}[D_i] \approx 0.20$, close to the observed 0.23.
Visualization. Figure (ref) shows the feature space projected onto the first two singular vectors. Agents (blue circles) and objects (red squares) cluster along the first dimension, confirming a low effective dimensionality. The right panel shows pairs connected by lines, demonstrating that the mechanism matches agents with nearby objects in projected space. Figure (ref) visualizes how the model performs with misreported preferences.
Summary. The numerical illustrations demonstrate: (1) Computational efficiency: the computation completes in under 15 ms for 100 agents and 20 products. (2) Near-optimal performance: the method achieves 99.4% of optimal NSW while running three orders of magnitude faster than direct optimization. (3) Robustness: the allocation is robust to moderate preference misreporting, degrading gracefully as noise increases. (4) Individual rationality violations: a small fraction of agents (3%) may receive utilities below their disagreement point when preferences are orthogonal to the principal direction, illustrating the limitation of rank-1 approximation. (5) Scalability: the method scales linearly with the number of agents, making it suitable for large markets.
The experiments in Section (ref) assumed normally-distributed agent preferences. In the real world, such assumptions may be restrictive. This section considers alternative distributions for agent utility specifications.
We tested the following distributions;
For each distribution and each noise level, we report:
As discussed in Section (ref), with additive utilities of the form $U_ij = u_i \cdot f_j$, some agents may fall below their uniform-random disagreement point, resulting in NSW of 0. To enhance our analysis, we report two NSW variants:
Table (ref) summarizes the results across different preference distributions with 0 misreporting. As the table shows, under non-normal distributions, our proposed matching methodology performs even better than with normally-distributed preferences, as judged by the utility gains over random allocations.
Table (ref) presents the results of noisy experiments. As the table shows, the proposed methodology outperforms the random allocation under all preference distributions and noise levels. However, as the noise levels increase, the performance of the proposed methodology degrades toward the random allocation baseline.
This section tests the proposed SVD-based mechanism when the true underlying utility is not the linear inner product $U_{ij} = u_i \cdot f_j$ assumed by the mechanism, but instead takes a richer, non-linear form.
The mechanism always observes only reported feature preferences $w_i$ and object feature vectors $f_j$; it always computes utilities as $\hat{w}_i \cdot f_j$ internally. The key question considered is how much welfare is lost when the ground-truth utility that agents actually experience deviates from that linear model.
The SVD mechanism sorts on $\hat{w}_i \cdot f_j$ (a linear proxy). Under non-linear true utilities, this proxy is accurate if and only if agents' preference rankings over objects are roughly preserved by the linear approximation. We measure this with Kendall's $\tau$ between the linear-proxy ranking and the true-utility ranking for each agent.
We compared the following non-linear utility models:
For each utility model and each nonlinearity strength ($\alpha, \beta, \gamma \dots$) we report:
Table (ref) summarizes the performance of the SVD model under different utility specifications. As the table shows, the proposed model outperforms random allocation in most utility configurations.
Table (ref) summarizes performance at maximum non-linearity strength across all ten utility specifications. The results organize naturally into three tiers defined by the Kendall $\tau$ statistic, which measures how faithfully the mechanism's linear proxy $\hat{w}_i \cdot f_j$ preserves each agent's true utility ranking over objects. When $\tau$ is high, sorting on the proxy produces nearly the same assignment as sorting on true utilities, and the mechanism performs well regardless of the functional form; when $\tau$ collapses, the proxy is effectively uncorrelated with true preferences, and the mechanism degrades toward or below random allocation.
\paragraph{Tier 1: Robust models ($\tau \geq 0.85$).} Five specifications (linear baseline, concave (diminishing returns), convex (increasing returns), max-feature, and Cobb-Douglas) maintain $\tau \geq 0.777$ and all produce positive utility gains over random allocation. The most striking result in this tier is the concave specification (diminishing returns, $U_{ij} = u_i \cdot \sqrt{f_j}$ element-wise), which achieves the highest Kendall $\tau$ of any non-linear model at $\tau = 0.944$, barely below the linear baseline of $1.000$. The intuition is direct: applying a monotone concave transformation to features compresses the range of object scores but preserves their rank order, so the linear proxy's sorting of agents and objects is almost identical to the true-utility sorting. The reported welfare loss of $+92.5\%$ relative to the linear baseline is therefore not a failure of the mechanism but a consequence of the utility scale: under diminishing returns, the absolute gaps between utilities are smaller, so the mechanism's NSW advantage over random allocation (in raw utility units) is also smaller even when the assignment is nearly identical.
Convex utilities (increasing returns, $U_{ij} = u_i \cdot f_j^2$) also preserve ordering well ($\tau = 0.887$), and notably produce a $+3.33\%$ gain over random allocation, higher than the linear baseline ($+1.84\%$). This occurs because convex transformation amplifies differences between high-quality and low-quality objects: matching high-preference agents to high-feature objects yields super-proportional utility gains, so correct sorting is more valuable under convexity than under linearity. The max-feature specification ($\tau = 0.887$, gain $+2.35\%$) behaves similarly: the mechanism's sorting on the principal feature direction aligns well with the true ranking, even when sub-threshold feature values contribute nothing.
\paragraph{Tier 2: Moderate degradation ($0.45 \leq \tau < 0.85$).} Three models (quadratic interactions, rank-based (ordinal), and RBF similarity bonus) show meaningful but bounded ranking distortion.
The quadratic interactions model ($\tau = 0.798$, gain $+5.26\%$) is the single best-performing non-linear specification by utility gain, and it also produces a negative welfare loss of $-112.4\%$ relative to the linear baseline. A negative welfare loss means the mechanism performs better under quadratic utilities than under linear ones. This counterintuitive result has a clean explanation: quadratic utilities reward agents whose preference vectors align strongly with high-quality objects along all feature dimensions simultaneously, which is precisely the structure that SVD sorting exploits most effectively (SVD matches high $\tilde{w}_i$ agents to high $\tilde{f}_j$ objects). The mechanism accidentally benefits from supermodularity: agents with strong across-the-board preferences are matched to objects with strong across-the-board features, producing pairwise synergies that the mechanism did not design for but nonetheless realizes.
Rank-based (ordinal) utilities ($\tau = 0.748$, gain $+3.66\%$) show that the mechanism remains effective even when agents respond only to relative feature rankings rather than absolute values. Since rank transformations preserve order, the mechanism's projection onto $v_1$ still identifies the direction along which objects most systematically spread their rank scores, and sorting along this direction yields above-random welfare.
The RBF similarity bonus ($\tau = 0.463$, gain $+4.51\%$) is the most nuanced case in this tier. The low $\tau$ signals that the linear proxy frequently misorients individual agents' rankings. Agents receive a bonus for being matched to objects whose feature profiles are close to their preference vector, a criterion that is geometrically orthogonal to the inner product $w_i \cdot f_j$ that the mechanism maximizes. Yet the aggregate utility gain remains high at $+4.51\%$. This apparent paradox resolves as follows: the RBF bonus is largest for agents whose preferences already lie near the high-variance direction $v_1$, precisely the agents whom Algorithm (ref) assigns to the highest-scoring objects. The mechanism's systematic matching therefore generates RBF bonuses for the agents best positioned to receive them, even without deliberately targeting similarity.
\paragraph{Tier 3: Mechanism failure ($\tau < 0.1$).} The two-layer MLP utility ($\tau = 0.063$) is the only specification under which the mechanism fails categorically, producing a $-1.27\%$ gain, worse than random allocation. With $\tau$ near zero, the linear proxy is essentially uncorrelated with agents' true MLP-induced preference rankings over objects. The mechanism sorts agents and objects on $v_1$ projections that carry no information about true utilities, and the resulting assignment is indistinguishable from a random permutation at best and slightly worse at worst (because the MLP assigns highest utility to combinations of agent and object features that are systematically not the ones the mechanism selects). This result identifies the precise failure boundary for Algorithm (ref): arbitrary non-linear interactions among features, of the kind a two-layer neural network can represent, completely destroy the ranking preservation that makes the spectral approach effective.
\paragraph{Summary.} Taken together, the non-linear robustness experiments reveal three principles. First, the mechanism is robust to any utility transformation that is monotone in $w_i \cdot f_j$: concave, convex, rank-based, and threshold specifications all preserve enough of the linear ranking structure for the mechanism to produce positive welfare gains. Second, the mechanism can unexpectedly benefit from certain forms of non-linearity: supermodular (quadratic) interactions amplify the value of correct sorting, producing welfare gains above the linear baseline. Third, the mechanism fails precisely when true utilities depend on feature interactions that are orthogonal to the inner product (as in the MLP case), rather than on the magnitude of the inner product itself. The practical implication is that practitioners should assess whether their domain's utility structure is plausibly monotone in a weighted feature sum (i.e., approximately hedonic) before deploying Algorithm (ref); the Kendall $\tau$ between a pilot linear model and elicited pairwise comparisons can serve as a pre-deployment diagnostic for this condition, analogously to the $\rho_1$ diagnostic for low effective dimensionality described in Section (ref).
This paper develops a computationally efficient approach to multi-dimensional matching markets using spectral dimensionality reduction. We formalize a matching framework where agents report preferences over features rather than complete objects, use Singular Value Decomposition to identify the principal direction of variation, and match agents to objects along this direction in $O(N \log N)$ time. We show that the mechanism approximately maximizes Nash Social Welfare when $\sigma_1 \gg \sigma_2$, satisfies distributional truthfulness measured by the Kolmogorov-Smirnov distance, and achieves exact symmetry. We establish a novel connection between Nash Social Welfare and Geometric Distributionally Robust Optimization, providing robustness guaranties. Numerical experiments demonstrate 99% optimal welfare achieved three orders of magnitude faster than direct optimization.
Our approach has limitations that require future work. The additive utility assumption rules out complementarities; extensions incorporating interaction terms would increase dimensionality. The low effective dimensionality ($\sigma_1 \gg \sigma_2$) is crucial -- characterizing when this holds in practice and developing adaptive methods to detect low-rank structure would strengthen the framework. Empirical validation on real-world datasets (school choice, labor markets, housing allocation) and field experiments would test theoretical predictions and reveal practical challenges.
Our work suggests many multi-dimensional matching problems may have low effective dimensionality, making them amenable to spectral methods. This has broader implications: platforms can collect simple feature ratings rather than complete rankings, reducing cognitive burden; designers can use SVD to understand which features matter most, informing policy; and dimensionality reduction provides a bridge between voting theory and matching theory. By demonstrating that spectral methods from machine learning can be integrated into mechanism design with formal incentive properties, we hope to inspire further cross-pollination between these fields.