Bio

Jamie Morgenstern is a Warren Fellow at the University of Pennsylvania. She received her PhD in Computer Science at Carnegie Mellon University, advised by Avrim Blum. Her research interests include mechanism design, learning theory, and applications of differential privacy to questions in economics. During her Ph.D., she received a Simons Award for Graduate Students in Theoretical Computer Science, an NSF Graduate Research Fellowship, and a Microsoft Graduate Women’s scholarship.

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

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

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.