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

Título traducido de la contribución: Elección de escuela: Implementación de Nash de emparejamientos estables a través de mecanismos de prioridad de rango

Paula Jaramillo, Cagatay Kayi, Flip Klijn

Resultado de la investigación: Documento de Trabajo

Resumen

Consideramos los problemas de elección de escuela (Abdulkadiro˘glu y S¨onmez, 2003) donde los estudiantes
se asignan a las escuelas públicas a través de un mecanismo de asignación centralizado. Nosotros
estudiar la familia de los llamados mecanismos de prioridad de rango, cada uno de los cuales es inducido por
un orden de pares de prioridad de rango. Siguiendo el orden correspondiente de pares, en cada
un 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 inmediata
es un mecanismo de prioridad de rango particular. Nuestro primer resultado principal es una caracterización
de la subfamilia de mecanismos de rango prioritario que Nash implementa el conjunto
de emparejamientos estables (es decir, justos) (Teorema 1). Demostramos que nuestra caracterización también
para la "subejecución" y la "supuesta ejecución" (Corolarios 3 y 4). Nuestro
el segundo resultado principal es un fuerte resultado de imposibilidad: en la información incompleta, no
El mecanismo de prioridad de rango implementa el conjunto de emparejamientos estables (Teorema 2).
Idioma originalEnglish (US)
Número de páginas30
EstadoPublished - 2017

Series de publicaciones

NombreBarcelona GSE Working Papers Series
N.º957

Huella dactilar

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

Citar esto

Jaramillo, P., Kayi, C., & Klijn, F. (2017). School Choice: Nash Implementation of Stable Matchings through Rank-Priority Mechanisms. (Barcelona GSE Working Papers Series; N.º 957).
Jaramillo, Paula ; Kayi, Cagatay ; Klijn, Flip. / School Choice: Nash Implementation of Stable Matchings through Rank-Priority Mechanisms. 2017. (Barcelona GSE Working Papers Series; 957).
@techreport{fb0c5cbe8d61419b97a2408cfdbfe560,
title = "School Choice: Nash Implementation of Stable Matchings through Rank-Priority Mechanisms",
abstract = "We consider school choice problems (Abdulkadiroğlu and S{\"o}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).",
author = "Paula Jaramillo and Cagatay Kayi and Flip Klijn",
year = "2017",
language = "English (US)",
series = "Barcelona GSE Working Papers Series",
number = "957",
type = "WorkingPaper",

}

Jaramillo, P, Kayi, C & Klijn, F 2017 'School Choice: Nash Implementation of Stable Matchings through Rank-Priority Mechanisms' Barcelona GSE Working Papers Series, n.º 957.

School Choice: Nash Implementation of Stable Matchings through Rank-Priority Mechanisms. / Jaramillo, Paula; Kayi, Cagatay; Klijn, Flip.

2017. (Barcelona GSE Working Papers Series; N.º 957).

Resultado de la investigación: Documento de Trabajo

TY - UNPB

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

AU - Jaramillo, Paula

AU - Kayi, Cagatay

AU - Klijn, Flip

PY - 2017

Y1 - 2017

N2 - 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).

AB - 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).

M3 - Working paper

T3 - Barcelona GSE Working Papers Series

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

ER -

Jaramillo P, Kayi C, Klijn F. School Choice: Nash Implementation of Stable Matchings through Rank-Priority Mechanisms. 2017. (Barcelona GSE Working Papers Series; 957).