Preference respecting stable matchings in school choice problems

Abstract

Tercihe riayetli sabitlik adında, okullar için tolerans değerleri içeren ve hem okulların önceliklerine hem de öğrencilerin tercihlerine önem veren, yeni bir sabitlik nosyonu sunduk. Her okul seçimi problemi için bir tercihe riayetli sabit eşleşmenin var olduğunu ve Gale-Shapley sabit eşleşmesine Pareto-üstün olduğunu bulduk. Sınırlı-verimli bir tercihe riayetli sabit eşleşmeye ulaşmak için geliştirme çemberlerine dayanan, iki adımlı bir mekanizma geliştirdik. Mekanizmamız geniş bir sınıf mekanizmaların doğal bir genellemesi ve öğrenci-optimal Sabit Mekanizma ve Boston Mekanizması'nı özel vakalar olarak kapsamakta. Ayrıca, mekanizmanın stratejik özelliklerini tam ve eksik bilgi durumları altında inceledik ve tercihleri dürüst bildirmenin, öğrenciler için ordinal Bayes Nash Dengesi olduğunu bulduk.

We introduce a new stability notion called preference respecting stability that incorporates tolerance values for schools and attaches importance to both the preferences of students and the priorities of schools, and study its properties. We find that a preference respecting stable allocation exists in any school choice problem, and it Pareto-dominates the Gale-Shapley stable allocation. We construct a two part mechanism that depends on improvement cycles to reach a constrained efficient preference respecting stable allocation. Our mechanism is a natural generalization of a broad class of mechanisms and admits the student-optimal Stable Mechanism and the Boston Mechanism as special cases. We also study its strategic properties under complete and incomplete information settings and find that truthful reporting of preferences is an ordinal Bayesian Nash equilibrium for the students.