1. Introduction

In many countries, public school systems have historically operated as monopolies, with the goal of fulfilling the objectives set by legislatures and educational institutions. However, educational policymakers in countries like the America have increasingly recognized the need for educational reforms, particularly in response to the school choice debate initiated by economist Milton Friedman in 1955 [1]. School choice refers to a range of programs that aim to empower parents to select the schools their children attend. Under traditional school choice systems, the mechanisms assign students to schools according to their residential districts, regardless of individual preferences or school quality. Wealthy parents already have a choice in the schools their children attend since they can afford to relocate to a place with better educational options or enrol them in a private school, but in the United States, access to these options is constrained by a lack of financial resources. School choice policies aim to enhance education quality by expanding options, particularly for parents without the financial capacity to exercise choice, and broaden students’ access to high-quality education, no matter what their socioeconomic background are. Advocates of school choice believe that granting autonomy to public schools can lead to better educational outcomes by allowing schools to tailor their approaches to meet the needs of students and parents.They also argue for providing parents with more information to make informed choices.

However, the impact of these market-based reforms on social capital and overall educational welfare is still debated among scholars.Social capital refers to the networks, relationships, and trust that contribute to positive social and educational outcomes.Some argue that school choice can enhance social capital by empowering parents and increasing their involvement in their children's education. Others suggest that it may lead to increased segregation and reduced support for the public school system. In short, based on laws of different states and countries, there are several ways for students to be admitted to colleges or universities, accordingly, in the language of economics, different matching systems should be applied. Thus, present work is going to compare different matching mechanisms, especially in the context of school choice model, and analyze the pros and cons of them in various real-world situations, and put forward some suggestions for the school, parents and the government in order to offer students a better welfare.

2. Mechanisms on School Choice Problem

2.1. Background Description

In education, school choice is literally one of the most heated topic. The school choice model is a one-sided matching where only one of two sets of agents have preferences over the other and act strategically, while the other set of agents do not have preferences and do not act strategically. This model is commonly used for allocating seats in public schools, centralized university admissions, and the allocation of vacant house, based on priorities [2]. In this model, the welfare of students is the primary concern, and priorities, such as neighborhood proximity or sibling enrollment, are predetermined and not strategically reported. Due to the limitations of assigning each student to their top choice school, mechanisms need to be designed to allocate students to schools in a fair and efficient manner [3].

In this problem, Students (denoted by i) and schools (denoted by s) are the two sets of agents. Each student has a preference list (which is often strict in theory) over the public schools, and there’s a maximum quota (denoted by qs) of the number of available seats for each school. A matching in this context is a mapping that determines students are assigned to a particular school or just stay unassigned. It is important to note that a school is only mapped to a student if the student chooses the school and is chosen by the school, and the maximum quota (qs) is the constraint that a school’s capacity of students.

Before introducing the important mechanisms in literature, the definition of some properties of the matching outcome need to be explained. The core concept of the school choice literature is elimination of justified envy. No unassigned pair of a student and a school (i, s), where student i prefers school s to his or her present assignment meanwhile he or she has a higher priority compared to an student in school s, exists. It is obvious that in the context of school choice problem the concept elimination of justified envy is similar to the concept stable in college admission problem[3]. The definition of a feasible matching is that every student whom a school assigns is acceptable to the school. What’s more, the definition of an individually rational(IR) matching is that no student would rather be unassigned than accept his or her present assignment, and a matching is considered non-wasteful when every student prefers his or her present assignment to some other school with at least one available seat. A matching is stable if it is non-wasteful, individually rational, and eliminates justified envy [4]. Besides, a matching ν is Pareto dominated by matching µ if µ assigns every student a weakly better match and a strictly better match for one student at least. The definition of a Pareto efficient matching is that it is not Pareto dominated by any other matching. Since only the students’ welfare is considered in the context of school choice problem, the student-optimal (stable) matching is not Pareto dominated by any other (stable) matching. The strategy-proofness of a mechanism is that no student can gain a better assignment, that is, be admitted to a school with higher priority, from misreporting. If misreporting makes him or her better off compared with being truthful, then the mechanism is vulnerable to a student’s strategic manipulation.

In the mechanisms to be described, the algorithm receives preference lists of schools’ ranking from the students and the number of available seats of each school. The students’ have distinct rankings without ties. In the event of ties, the mechanism breaks them arbitrarily. Using this information, the mechanism then generates a matching that assigns students to schools according to their preference list and the maximum quota of the schools. It aims to optimize the allocation of students to schools according to their stated preferences and the constraints imposed by the school capacities. In order to simplify and unite the notation, suppose a school choice problem (i, s, qs, P (priority), PL (Preference List)) is given in the description of following mechanisms [5].

2.2. The Student-Proposing Defer Acceptance (DA) Mechanism

Step 1. Every i make a proposal to the school which is his or hers top choice. Each school s places the first qs applicants and also the acceptable ones on its hold list, and rejects the rest. Decrease a school’s quota by one if it accepts a student.

Step k. A student who is rejected by a school at step k-1 can make a proposal to their next favorite school. Each school s places the first qs applicants and also the acceptable ones on its hold list, and rejects the rest. Decrease a school’s quota by one if it accepts a student.

End. The mechanism stops operating when all students are accepted, or all schools have reached their maximum quota. Leave the remaining students unassigned.

The DA mechanism is one of the most classic mechanism in matching theory. Due to its stable outcome and strategy-proofness, DA mechanism is applied in many real-life problems, including school-choice problem. Although the stable match that is best for all the students, and they are the ones whose welfare should be cared about, DA mechanism does not possess Pareto efficiency due to the mutual exclusivity between efficiency and stability [6]. The student-proposing Defer Acceptance (DA) mechanism has another name, student-optimal DA mechanism. According to its name, it eliminates justified envy, and any other mechanism that possesses the property of elimination of justified envy is Pareto dominated by this [7].

The DA mechanism is a widely used algorithm for matching students to schools based on their preferences. It involves a series of proposals and rejections until a stable matching is reached. Kesten’s mechanism (EADA mechanism) introduced efficiency adjustments to the DA mechanism, which in turn were further simplified by Tang and Yu while maintaining the same matching outcomes [8, 9]. The modification by Tang and Yu demonstrates that it is possible to enhance the efficiency of Kesten’s algorithm. The improved algorithm provides a more efficient and simplified approach for studying the school choice problem. In general, the Defer Acceptance (DA) mechanism is a well-behaved mechanism [3].

2.3. The Top Trading Cycle (TTC) Mechanism

Step 1. If a student s has a top choice among the schools, point from he or she to that school. If not, the student points to himself or herself, indicating a preference to remain unassigned. Every school point to the highest priority student for the school. This creates a set of student-school preferences. There must be at least one cycle (a student pointing to himself or herself is also considered one). These cycles represent potential assignments. For each cycle, the school offers a seat to the student points to it, or a student leaves unassigned if he or she is pointing to himself or herself. If there are no more available seat of a school, remove that school from consideration [2].

Step k. For each unassigned student, if he or she has a top choice among the remaining schools, point from he or she to that school. If not, the student points to himself or herself, indicating a preference to be unassigned. For each remaining school, the highest priority student for that school is pointed from it. There must be one cycle at least (a student pointing to himself or herself is also considered one). These cycles represent potential assignments. For each cycle, the school offers a seat to the student points to it, or a student leaves unassigned if he or she is pointing to himself or herself. If there are no more available seat of a school, remove that school from consideration.

End. The mechanism stops operating when all students are accepted, or all schools have reached their maximum quota. Leave the remaining students unassigned.

The Top Trading Cycle (TTC) mechanism is a popular one used in school choice problems to allocate students to schools. It is a strategy-proof mechanism, meaning that it incentivizes truthful reporting of preferences from both students and schools. Overall, the TTC mechanism offers a valuable combination of Pareto efficiency, strategy-proofness for students, and adaptability to handle type-specific quotas when necessary. By incorporating the quotas into the algorithm, the mechanism can still maintain both constrained strategy-proofness and Pareto efficiency. This ensures that the assignment remains fair and efficient while adhering to the specified quotas.

By using the TTC algorithm, school choice systems aim to achieve efficient and fair allocations while respecting the preferences of both students and schools.

2.4. The Boston (BOS) mechanism

Step 1. The mechanism only considers the 1st choice of each student. For each school s, find the students that put the school on his or her 1st choice. The school s assigns seats to those students in turn based on their priorities at s until all of the qs seats of the school s have been assigned, or, there is no other student who has put the school on his or her 1st choice and is acceptable to s.

Step k. For all of the remaining students, the mechanism only considers the kth choices of them. For each remaining school s, find the students that put the school on his or her kth choice. The school s assigns seats to those students in turn based on their preference rankings at s until all of the qs seats of the school s have been assigned, or, there is no student left who has put the school as on his or her kth choice and is acceptable to s [10].

End. The mechanism stops operating when all students are accepted, or all schools have reached their maximum quota. Leave the remaining students unassigned.

The Boston mechanism, also known as the “Boston mechanism with tie-breaking,” aims to assign students to their top choice schools as much as possible. However, it is not considered strategy-proof because students may misreport their preferences strategically to increase their chances of getting their top choice school [10].

This issue arises when the mechanism uses tie-breaking rules to resolve situations where multiple students have the same top choice school. In such cases, students may strategically manipulate their preferences to improve their chance of being assigned to their top choice school.

As a result, the Boston Public Schools guide advises parents to consider strategic preference submissions. This means that parents may be advised to list their preferred schools in a way that maximizes their chances of being assigned to their top choice school, even if it may not accurately reflect their true preferences.1

This strategic behavior can undermine the fairness and reliability of the assignment process, as it may result in students not being assigned to their genuine top choice schools. Researchers and policymakers have been working on developing alternative mechanisms that are both strategy-proof and efficient to address these concerns.

2.5. The Serial Dictatorship (SD) Mechanism

Step 1. Students are matched at the top of the priority order with his or her top choice school. After the student is assigned, he is removed from the priority order, and the respective school’s maximum quota is decreased by one. If there are no more available seat of a school, remove that school from consideration.

Step k. Based on the school priority list, the highest priority remaining students are assigned to the top-ranked school on her preference list that still has available capacity.

End. The mechanism stops operating when all students are accepted, or all schools have reached their maximum quota. Leave the remaining students unassigned.

The SD mechanism is the only mechanism presented that has all the desirable properties: elimination of justified envy, Pareto efficiency, and strategy-proof [11]. However, it can only be applied to some of the one-side matching problems with universally accepted, open and transparent priority order. In this context, schools are not strategy agents, but just choose students based on their home address, which school his or her siblings are attending, and so on. Thus, even though SD mechanism could generate a theoretical superior outcome, it is barely applied in real-life school-choice system. Nonetheless, if there is a clear priority order, for example, score of college admission exam, it is absolutely feasible and fair.

3. Conclusion and Suggestions

Despite there are various mechanisms, all of them have advantages and disadvantages. However, in the real-life situation, the actual system may be far more complicated than just applying a mechanism on students’ preference list. It could be a hybrid mechanism, considering many associated factors. Thus, for the sake of improve the welfare of the students, the government should take a global view of the location of indigenous schools, the overall preference of students, the “under-demanded schools” and so on. Besides, governments are supposed to support research and initiatives concerning school-choice mechanism innovation and improvement. Allocating sufficient funding to ensure quality education for all students, including resources for extracurricular activities, mental health support, and professional development for teachers. Enhance transparency by providing clear and easily understandable information about the school selection process, eligibility criteria, and available options. Ensure that students and parents have access to comprehensive information about schools, including their performance, curriculum, extracurricular activities, and support services.

For the parents, they should establish open communication channels with the school, actively engaging in regular discussions about their children’s progress and stay informed about their child's education, including school policies and resources, to actively advocate for their best interests.

For the schools to be picked, fair is of primary importance. They need to provide equal opportunities for all students, regardless of their background or abilities. Academically, design mechanisms that promote fairness and equity in school assignments, minimizing biases and discriminatory practices and regularly review and evaluate the allocation mechanisms to identify and rectify any unfairness or unintended consequences. Recognize that different regions or communities may have unique needs and preferences when it comes to school choice mechanisms. Thus, the process of designing mechanisms can be adapted and customized accordingly. Consider allowing for flexibility in the allocation process, such as accommodating late enrollments or transfers, addressing special needs, or making provisions for changes in student preferences.