School-choice mechanism

Last updated

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. [1] It is used to automate the process of school choice. The most common school-choice mechanisms are variants of the deferred-acceptance algorithm and random serial dictatorship.

Contents

Relation to other matching mechanisms

School choice is a kind of a two-sided matching market, like the stable marriage problem or residency matching. 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 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 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. [2]

Efficiency-adjusted deferred-acceptance

Onur Kesten [2] 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. [3]

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

Related Research Articles

In mathematics, economics, and computer science, the stable marriage 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 the elements of one set to the elements of the other set. A matching is not stable if:

<span class="mw-page-title-main">Alvin E. Roth</span> American academic (born 1951)

Alvin Eliot Roth is an American academic. He is the Craig and Susan McCaw professor of economics at Stanford University and the Gund professor of economics and business administration emeritus at Harvard University. He was President of the American Economic Association in 2017.

In social choice theory, a dictatorship mechanism is a rule by which, among all possible alternatives, the results of voting mirror a single pre-determined person's preferences, without consideration of the other voters. Dictatorship by itself is not considered a good mechanism in practice, but it is theoretically important: by Arrow's impossibility theorem, when there are at least three alternatives, dictatorship is the only ranked voting electoral system that satisfies unrestricted domain, Pareto efficiency, and independence of irrelevant alternatives. Similarly, by Gibbard's theorem, when there are at least three alternatives, dictatorship is the only strategyproof rule.

<span class="mw-page-title-main">Market design</span>

Market design is a practical methodology for creation of markets of certain properties, which is partially based on mechanism design. In some markets, prices may be used to induce the desired outcomes — these markets are the study of auction theory. In other markets, prices may not be used — these markets are the study of matching theory.

The National Resident Matching Program (NRMP), also called The Match, is a United States-based private non-profit non-governmental organization created in 1952 to place U.S. medical school students into residency training programs located in United States teaching hospitals. Its mission has since expanded to include the placement of U.S. citizen and non-U.S. citizen international medical school students and graduates into residency and fellowship training programs. In addition to the annual Main Residency Match that in 2021 encompassed more than 48,000 applicants and 38,000 positions, the NRMP conducts Fellowship Matches for more than 60 subspecialties through its Specialties Matching Service (SMS). The NRMP is sponsored by a board of directors that includes medical school deans, teaching hospital executives, graduate medical education program directors, medical students and residents, and one public member.

In mathematics, economics, and computer science, the Gale–Shapley algorithm is an algorithm for finding a solution to the stable matching problem. It is named for David Gale and Lloyd Shapley, who published it in 1962, although it had been used for the National Resident Matching Program since the early 1950s. Shapley and Alvin E. Roth won the 2012 Nobel Prize in Economics for work including this algorithm.

<span class="mw-page-title-main">Arunava Sen</span> Indian researcher and teacher

Arunava Sen is a professor of economics at the Indian Statistical Institute. He works on Game Theory, Social Choice Theory, Mechanism Design, Voting and Auctions.

Top trading cycle (TTC) is an algorithm for trading indivisible items without using money. It was developed by David Gale and published by Herbert Scarf and Lloyd Shapley.

In economics, dichotomous preferences (DP) are preference relations that divide the set of alternatives to two subsets: "Good" versus "Bad".

Approximate Competitive Equilibrium from Equal Incomes (A-CEEI) is a procedure for fair item assignment. It was developed by Eric Budish.

Fair random assignment is a kind of a fair division problem.

Random priority (RP), also called Random serial dictatorship (RSD), is a procedure for fair random assignment - dividing indivisible items fairly among people.

A simultaneous eating algorithm(SE) is an algorithm for allocating divisible objects among agents with ordinal preferences. "Ordinal preferences" means that each agent can rank the items from best to worst, but cannot (or does not want to) specify a numeric value for each item. The SE allocation satisfies SD-efficiency - a weak ordinal variant of Pareto-efficiency (it means that the allocation is Pareto-efficient for at least one vector of additive utility functions consistent with the agents' item rankings).

Various experiments have been made to evaluate various procedures for fair division, the problem of dividing resources among several people. These include case studies, computerized simulations, and lab experiments.

Truthful resource allocation is the problem of allocating resources among agents with different valuations over the resources, such that agents are incentivized to reveal their true valuations over the resources.

Course allocation is the problem of allocating seats in university courses among students. Many universities impose an upper bound on the number of students allowed to register to each course, in order to ensure that the teachers can give sufficient attention to each individual student. Since the demand for some courses is higher than the upper bound, a natural question is which students should be allowed to register to each course.

In economics and social choice theory, a no-justified-envy matching is a matching in a two-sided market, in which no agent prefers the assignment of another agent and is simultaneously preferred by that assignment.

In economics and computer science, the house allocation problem is the problem of assigning objects to people with different preferences, such that each person receives exactly one object. The name "house allocation" comes from the main motivating application, which is assigning dormitory houses to students. Other commonly used terms are assignment problem and one-sided matching. When agents already own houses, the problem is often called a housing market. In house allocation problems, it is assumed that monetary transfers are not allowed; the variant in which monetary transfers are allowed is known as rental harmony.

Donor coordination is a problem in social choice. There are several donors, each of whom wants to donate some money. Each donor supports a different set of targets. The goal is to distribute the total donated amount among the various targets in a way that respects the donors' preferences.

In mechanism design, a regret-free truth-telling mechanism 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 mechanism incentivizes agents who want to avoid regret to report their preferences truthfully.

References

  1. ↑ Abdulkadiroğlu, Atila; Sönmez, Tayfun (June 2003). "School Choice: A Mechanism Design Approach". American Economic Review. 93 (3): 729–747. doi:10.1257/000282803322157061. hdl: 10161/2090 . ISSN   0002-8282. S2CID   15609227.
  2. 1 2 Kesten, Onur (2010). "School Choice with Consent". The Quarterly Journal of Economics. 125 (3): 1297–1348. doi:10.1162/qjec.2010.125.3.1297. ISSN   0033-5533. JSTOR   27867511.
  3. ↑ Chen, Yiqiu; Möller, Markus (2021). "Regret-Free Truth-telling in School Choice with Consent". SSRN Electronic Journal. doi:10.2139/ssrn.3896306. ISSN   1556-5068. S2CID   236911018.
  4. ↑ Cerrone, Claudia; Hermstrüwer, Yoan; Kesten, Onur (2022-07-01). "School Choice with Consent: An Experiment".{{cite journal}}: Cite journal requires |journal= (help)
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.