Multi-Dimensional Matching

Irene Aldridge

econ.EMSep 24, 2026

Multi-Dimensional Matching

Authors: Irene Aldridge

Abstract

We study a matching mechanism where agents and objects are described by features rather than complete rankings. A single spectral projection reduces the problem to a one-dimensional sort, computable in O(N log N) time. We prove that on descaled features and preferences, our algorithm obtains the exact Nash Social Welfare (NSW) optimum within the projected space, with an unconditional utilitarian-welfare guarantee and a conditional NSW guarantee. The proposed mechanism is stable against exogenous noise but not strategy-proof; we provide an explicit profitable misreport. On an agentic AI shopping application, the diagnostics correctly anticipate both a success and a failure case. A 100-instance robustness study confirms the findings.

Figures & tables

Work	Input format	Method	Truthfulness
Hylland and Zeckhauser [28]	Cardinal $u_{ij}$	Market clearing	Not guaranteed
Chawla et al. [12]	Multi-parameter bundles	Sequential posted pricing	Truthful-in-expectation
Devanur et al. [15]	Cardinal $u_{ij}$	Random assignment, config. LP	Not primary focus
Abebe et al. [3]	Cardinal $u_{ij}$	Random sampling	Truthful-in-expectation
This work	Feature prefs. $u_{ix}$ , $f_{jx}$	SVD projection	Noise-stable, not strategyproof

Table 1: Comparison to related work. Unlike prior approximate mechanisms, our truthfulness column reports what Section 4 actually proves, not an aspirational label.

Mechanism	Mean $\log\mathrm{NSW}_{\epsilon}$	95% CI half-width	Mean IR viol. (of 10)
Random	6.52	$\pm 1.23$	5.03
Serial Dictatorship	17.95	$\pm 1.72$	1.48
Our Method	17.37	$\pm 1.70$	1.56
Utilitarian-Optimal	20.01	$\pm 1.67$	1.28

Table 2: Figures underlying Figure 2 .

Explore similar work

Multi-Dimensional Matching in Market Design
May 19, 2026Irene AldridgeDistribution Matching Matching Markets
Irene Aldridge
Learn to Match: Two-Sided Matching with Temporally Extended Feedback
Jun 4, 2026Haijing Zong, Yancheng Liang, Boyang Zhou +1Distribution Matching Matching Markets
Department of Economics, University of Washington, Seattle, United States · Paul G. Allen School of Computer Science & Engineering, University of Washington, Seattle, United States
Probably Correct Optimal Stable Matching under Two-Sided Uncertainty
Jul 6, 2026Andreas Athanasopoulos, Anne-Marie George, Christos DimitrakakisDistribution Matching Matching Markets
University of Neuchâtel, Neuchâtel, Switzerland · University of Oslo, Oslo, Norway

May 19, 2026, cs.GTJ/K move · Enter open · S save

Multi-Dimensional Matching in Market Design

Irene Aldridge

Distribution Matching Matching Markets Distributionally-Robust Optimization Efficient Planning

Open paper AskPDF arXiv

This paper proposes a computationally efficient mechanism for multi-dimensional matching markets where agents report preferences over object features rather than complete utility assessments. We use Singular Value Decomposition (SVD) to identify the principal direction of variation in feature space and match agents to objects along this dimension, reducing a complex multi-dimensional problem to an effectively one-dimensional problem solvable in

O(N \log N)

time. We show that when data exhibit low effective dimensionality, our mechanism approximately maximizes Nash Social Welfare, satisfies distributional truthfulness, and achieves symmetry. We establish a novel connection between Nash Social Welfare and Geometric Distributionally Robust Optimization, providing robustness guaranties. Numerical experiments demonstrate that our approach achieves 99% optimal welfare while running three orders of magnitude faster than direct optimization. The framework applies naturally to school choice, labor markets, and course allocation, where feature-based elicitation reduces the cognitive burden on agents.

Abstract

Explore similar work

Multi-Dimensional Matching in Market Design

Learn to Match: Two-Sided Matching with Temporally Extended Feedback

Probably Correct Optimal Stable Matching under Two-Sided Uncertainty