Identifying and Quantifying (Un)Improvable Students
The Deferred Acceptance (DA) mechanism can generate inefficient placements. Although Pareto-dominant mechanisms exist, it remains unclear which and how many students could improve. We characterize the set of unimprovable students and show that it includes those unassigned or matched with their least preferred schools. Nevertheless, by proving that DA's envy digraph contains a unique giant strongly connected component, we establish that almost all students are improvable, and furthermore, they can benefit simultaneously via disjoint trading cycles. Our findings reveal the pervasiveness of DA's inefficiency and the remarkable effectiveness of Pareto-dominant mechanisms in addressing it, regardless of the specific mechanism chosen.
Code (0)
등록된 구현이 없습니다.
Tasks
validMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Improvable Students in School Choice
The Deferred Acceptance algorithm (DA) frequently produces Pareto inefficient allocations in school choice problems. While a number of efficient mechanisms that Pareto-dominate DA are available, a normative question rema…
BlockingImprovable Gap Balancing for Multi-Task Learning
In multi-task learning (MTL), gradient balancing has recently attracted more research interest than loss balancing since it often leads to better performance. However, loss balancing is much more efficient than gradient …
Deep Reinforcement LearningMulti-Task LearningOn Privately Estimating a Single Parameter
We investigate differentially private estimators for individual parameters within larger parametric models. While generic private estimators exist, the estimators we provide repose on new local notions of estimand stabil…
Quantifying the relationship between student enrollment patterns and student performance
Simplified categorizations have often led to college students being labeled as full-time or part-time students. However, at many universities student enrollment patterns can be much more complicated, as it is not uncommo…
SchedulingTowards Identifying and Managing Sources of Uncertainty in AI and Machine Learning Models - An Overview
Quantifying and managing uncertainties that occur when data-driven models such as those provided by AI and machine learning methods are applied is crucial. This whitepaper provides a brief motivation and first overview o…
BIG-bench Machine Learning