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

We consider school choice problems (Abdulkadiroglu 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 (i.e., fair) matchings (Theorem 1). We show that our characterization also holds for \sub-implementation" and \sup-implementation" (Corollaries 3 and 4). Our second main result is a strong impossibility result: under incomplete information, no rank-priority mechanism implements the set of stable matchings (Theorem 2).

• Autores: Jaramillo Vidales, Paula; Kayi, Cagatay; Klijn, Flip
• Tipo de recurso: Work document
• Fecha de publicación: 2017
• Institución: Universidad de los Andes
• Repositorio: Séneca: repositorio Uniandes
• Idioma: eng
• OAI Identifier: oai:repositorio.uniandes.edu.co:1992/8726
• Acceso en línea: http://hdl.handle.net/1992/8726
• Palabra clave: Asignación escolar; Mecanismos clasificación-prioridad; Implementación de Nash; Problemas de asignación (Programación); Investigación operacional; C78, D61, D78, I20
• Rights: openAccess
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/