School choice: Nash implementation of stable matchings through rank-priority mechanisms

Authors: Paula Jaramillo, Çaǧatay Kayı and Flip Klijn

Journal of Mathematical Economics, Vol. 95, August, 2021

We consider school choice problems (Abdulkadiroğlu and Sönmez, 2003) where students are assigned to public schools through a centralized assignment mechanism. We study the family of so-called rank-priority mechanisms, each of which is induced by an order of rank-priority pairs. Following the corresponding order of pairs, at each step a rank-priority mechanism considers a rank-priority pair and matches an available student to an unfilled school if the student and the school rank and prioritize each other in accordance with the rank-priority pair. The Boston or immediate acceptance mechanism is a particular rank-priority mechanism. Our first main result is a characterization of the subfamily of rank-priority mechanisms that Nash implement the set of stable matchings (Theorem 1). Our second main result is a strong impossibility result: under incomplete information, no rank-priority mechanism implements the set of stable matchings

This paper originally appeared as Barcelona School of Economics Working Paper 957