2014/07/09 by Sampath Kannan, Jamie Morgenstern, Kannan, Sampath +5
Computer Science · Decision Sciences · Economics, Econometrics and Finance · #Auction Theory and Applications #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #Game Theory and Voting Systems #Privacy-Preserving Technologies in Data #cs.GT
paper · pdf · doi:10.48550/arxiv.1407.2640
openalex publication_date 2014/07/09 · arxiv created 2014/10/24 · arxiv updated 2014/10/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.