A school-choice mechanism is an algorithm that aims to match pupils to schools in a way that respects both the pupils' preferences and the schools' priorities. It is used to automate the process of

school choice School choice is a term for education options that allow students and families to select alternatives to traditional public schools. School choice options include scholarship tax credit programs, open enrollment laws (which allow students to att ...

. The most common school-choice mechanisms are variants of the deferred-acceptance algorithm and random serial dictatorship.

Relation to other matching mechanisms

School choice is a kind of a two-sided matching market, like the

stable marriage problem In mathematics, economics, and computer science, the stable matching problem is the problem of finding a stable matching between two equally sized sets of elements given an ordering of preferences for each element. A matching is a bijection from ...

residency matching Residency may refer to: * Artist-in-residence, a program to sponsor the residence and work of visual artists, writers, musicians, etc. * Concert residency, a series of concerts performed at one venue * Domicile (law), the act of establishing or m ...

. The main difference is that, in school choice, one side of the market (namely, the schools) are not strategic. Their priorities do not represent subjective preferences, but are determined by legal requirements, for example: a priority for relatives of previous students, minority quotas, minimum income quotas, etc.

Strategic considerations

A major concern in designing a school-choice mechanism is that it should be

strategyproof In mechanism design, a strategyproof (SP) mechanism is a game form in which each player has a weakly-dominant strategy, so that no player can gain by "spying" over the other players to know what they are going to play. When the players have private ...

for the pupils (as they are considered to be strategic), so that they reveal their true preferences for schools. Therefore, the mechanism most commonly used in practice is the Deferred-acceptance algorithm with pupils as the proposers. However, this mechanism may yield outcomes that are not

Pareto-efficient In welfare economics, a Pareto improvement formalizes the idea of an outcome being "better in every possible way". A change is called a Pareto improvement if it leaves at least one person in society better off without leaving anyone else worse ...

for the pupils. This loss of efficiency might be substantial: a recent survey showed that around 2% of the pupils could receive a school that is more preferred by them, without harming any other student. Moreover, in some cases, DA might assign each pupil to their second-worst or worst school.

Efficiency-adjusted deferred-acceptance

Onur Kesten suggested to amend DA by removing "interrupters", that is, (student, school) pairs in which the student proposes to the school, causes the school to reject another student, and rejected later on. This "Efficiency Adjusted Deferred Acceptance" algorithm (EADA) is Pareto-efficient. Whereas it is not stable and not strategyproof for the pupils, it satisfies weaker versions of these two properties. For example, it is

regret-free truth-telling In mechanism design, a regret-free truth-telling mechanism (RFTT, or regret-free mechanism for short) is a mechanism in which each player who reveals his true private information does not feel regret after seeing the mechanism outcome. A regret-free ...

. Interestingly, in lab experiments, more pupils report their true preferences to EADA than to DA (70% vs 35%). EADA is about to be used in

Flanders Flanders ( or ; ) is the Dutch language, Dutch-speaking northern portion of Belgium and one of the communities, regions and language areas of Belgium. However, there are several overlapping definitions, including ones related to culture, la ...

References

{{Reflist Mechanism design Education economics