arXiv 19 May 2026 · cs.GT
arXiv:2605.22865 · PDF · DOI · OpenAlex · Extracted main text
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.
appendix boundary found by appendix_command · 100% of the source is main text. Read the extracted text to check this.
The works this paper leans on most, across its whole bibliography — not restricted to papers in our corpus. Ranked by composite intensity, which combines how often a work is mentioned, how many sections mention it, and how much of that falls in the main text rather than the appendix.
| Reference | Intensity | Mentions | Sections | Main text | |
|---|---|---|---|---|---|
| 1 | Gans, Joshua S. and Kominers, Scott Duke (2026) Informative Grading Requires Cross-Course Comparability | 1.000 | 6 | 3 | 100% |
| 2 | Hylland, Aanund and Zeckhauser, Richard (1979) The Efficient Allocation of Individuals to Positions | 1.000 | 5 | 3 | 100% |
| 3 | Rediet Abebe and Richard Cole and Vasilis Gkatzelis and Jason D. Har… (2020) A Truthful Cardinal Mechanism for One-Sided Matching | 0.874 | 6 | 2 | 100% |
| 4 | Lin Zhou (1990) On a conjecture by gale about one-sided matching problems | 0.843 | 3 | 3 | 100% |
| 5 | Liu, Jiashuo and Wu, Jiayun and Li, Bo and Cui, Peng (2022) Distributionally Robust Optimization with Data Geometry | 0.644 | 2 | 2 | 100% |
| 6 | Chawla, Shuchi and Hartline, Jason D. and Malec, David L. and Sivan,… (2010) Multi-parameter mechanism design and sequential posted pricing | 0.511 | 2 | 1 | 100% |
| 7 | Nikhil R. Devanur and Jason D. Hartline and Qiqi Yan (2015) Envy freedom and prior-free mechanism design | 0.511 | 2 | 1 | 100% |
| 8 | Carl Eckart and Gale Young (1936) The approximation of one matrix by another of lower rank | 0.511 | 2 | 1 | 100% |
| 9 | Burgess, Simon and Greaves, Ellen and Vignoles, Anna and Wilson, Deb… (2015) What Parents Want: School Preferences and School Choice | 0.511 | 2 | 1 | 100% |
| 10 | Chen, Thomas and Chen, Xi and Peng, Binghui and Yannakakis, Mihalis (2022) Computational Hardness of the Hylland–Zeckhauser Scheme | 0.511 | 2 | 1 | 100% |
Showing the top 10 of 37 scored citations.