# Multi-Dimensional Matching

arXiv: https://arxiv.org/abs/2609.29958 · HTML: https://mlsanity.com/paper/2609.29958/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 5 of its 47 references that are in the map.
- First posted on arXiv 24 Sep 2026.

## Builds on (most cited first, 5 of 5)

- [Justified Representation in Approval-Based Committee Voting](https://mlsanity.com/paper/1407.8269/) (2014)
- [What Is Your AI Agent Buying? Evaluation, Biases, Model Dependence, & Emerging Implications for Agentic E-Commerce](https://mlsanity.com/paper/2508.02630/) (2025)
- [Finding a Collective Set of Items: From Proportional Multirepresentation to Group Recommendation](https://mlsanity.com/paper/1402.3044/) (2014)
- [Convex Program Duality, Fisher Markets, and Nash Social Welfare](https://mlsanity.com/paper/1609.06654/) (2016)
- [A Truthful Cardinal Mechanism for One-Sided Matching](https://mlsanity.com/paper/1903.07797/) (2019)

## Abstract (arXiv)

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.