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

Paula Jaramillo, Cagatay Kayi, Flip Klijn

Research output: Working paper

Abstract

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).
Original languageEnglish (US)
Number of pages30
StatePublished - 2017

Publication series

NameBarcelona GSE Working Papers Series
No.957

Fingerprint

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

Cite this

Jaramillo, P., Kayi, C., & Klijn, F. (2017). School Choice: Nash Implementation of Stable Matchings through Rank-Priority Mechanisms. (Barcelona GSE Working Papers Series; No. 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, no. 957.

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

2017. (Barcelona GSE Working Papers Series; No. 957).

Research output: Working paper

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