# Approximately Stable, School Optimal, and Student-Truthful Many-to-One Matchings (via Differential Privacy)

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Jul 2014.

## Built on by (most cited first, 1 of 1)

- [Private Multi-Task Learning: Formulation and Applications to Federated Learning](https://mlsanity.com/paper/2108.12978/) (2021)

## Abstract (arXiv)

We present a mechanism for computing asymptotically stable school optimal matchings, while guaranteeing that it is an asymptotic dominant strategy for every student to report their true preferences to the mechanism. Our main tool in this endeavor is differential privacy: we give an algorithm that coordinates a stable matching using differentially private signals, which lead to our truthfulness guarantee. This is the first setting in which it is known how to achieve nontrivial truthfulness guarantees for students when computing school optimal matchings, assuming worst- case preferences (for schools and students) in large markets.