Feature-based Uncertainty Model for School Choice

In this work, we consider a school choice scenario where a student does not exactly know which college is better for her. Although it is hard for a student to obtain an exact preference, she can usually compare specific features of colleges, such as reputation, location, andcampusfacilities. Motivatedbythis, weproposeafeature-based uncertainty model for school choice where a student’s preference is based on a linear combination of her utilities over different features, and the coefficients of the combination are treated as random variables. Our main goal is to achieve a higher probability of stability (ProS) and incentive compatibility (IC) for students. Unfortunately, thesetwogoalsareincompatibleingeneral. Weshowthatastudentproposing deferred acceptance (DA) that prioritizes colleges with higher expected ranking can achieve a worst-case approximation ratio of (1/𝑛)𝑛 on ProS, while a DA with a carefully defined iterated comparison vector can guarantee the strongest achievable form of IC. Finally, we provide additional results for some specific restrictions on the model.

Authors

• Yao Zhang Northwestern Polytechnical University
• Makoto Yokoo Kyushu University

Keywords

• School Choice
• Uncertain Preferences
• Stability