School Choice: Nash Implementation of Stable Matchings through Rank-Priority Mechanisms Working Paper

abstract

  • Consideramos los problemas de elección de escuela (Abdulkadiro˘glu y S¨onmez, 2003) donde los estudiantesse asignan a las escuelas públicas a través de un mecanismo de asignación centralizado. Nosotrosestudiar la familia de los llamados mecanismos de prioridad de rango, cada uno de los cuales es inducido porun orden de pares de prioridad de rango. Siguiendo el orden correspondiente de pares, en cadaun mecanismo de prioridad de rango considera un par de prioridad de rango y empareja un par de prioridad de rango disponible.a una escuela sin llenar si el estudiante y la escuela clasifican y dan prioridad a cada uno de ellos.otro de acuerdo con el par de prioridades de rango. El Boston o la aceptación inmediataes un mecanismo de prioridad de rango particular. Nuestro primer resultado principal es una caracterizaciónde la subfamilia de mecanismos de rango prioritario que Nash implementa el conjuntode emparejamientos estables (es decir, justos) (Teorema 1). Demostramos que nuestra caracterización tambiénpara la "subejecución" y la "supuesta ejecución" (Corolarios 3 y 4). Nuestroel segundo resultado principal es un fuerte resultado de imposibilidad: en la información incompleta, noEl mecanismo de prioridad de rango implementa el conjunto de emparejamientos estables (Teorema 2).
  • 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 (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).

publication date

  • 2017/1/1

keywords

  • Acceptance
  • Assignment
  • Impossibility
  • Incomplete information
  • Nash implementation
  • Public schools
  • School choice
  • Stable matching

number of pages

  • 30