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

<span class="mw-page-title-main">Random ballot</span> Electoral system with lottery among ballots

A random ballot or random dictatorship is a randomized electoral system where the election is decided on the basis of a single randomly-selected ballot. A closely-related variant is called random serialdictatorship, which repeats the procedure and draws another ballot if multiple candidates are tied on the first ballot.

<span class="mw-page-title-main">Liberal paradox</span> Paradox in social choice

The liberal paradox, also Sen paradox or Sen's paradox, is a logical paradox proposed by Amartya Sen which shows that no means of aggregating individual preferences into a single, social choice, can simultaneously fulfill the following, seemingly mild conditions:

  1. The unrestrictedness condition, or U: every possible ranking of each individual's preferences and all outcomes of every possible voting rule will be considered equally,
  2. The Pareto condition, or P: if everybody individually likes some choice better at the same time, the society in its voting rule as a whole likes it better as well, and
  3. Liberalism, or L : all individuals in a society must have at least one possibility of choosing differently, so that the social choice under a given voting rule changes as well. That is, as an individual liberal, anyone can exert their freedom of choice at least in some decision with tangible results.
<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.

<span class="mw-page-title-main">Dictatorship mechanism</span> Theoretical rule in social choice theory

In social choice theory, a dictatorship mechanism is a degenerate voting rule or mechanism where the result depends on only one person's preferences, without considering any other voters. A serial dictatorship is similar, but also designates a series of "backup dictators", who break ties in the original dictator's choices when the dictator is indifferent.

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

Market design is an interdisciplinary, engineering-driven approach to economics and a practical methodology for creation of markets of certain properties, which is partially based on mechanism design. In market design, the focus is on the rules of exchange, meaning who gets allocated what and by what procedure. Market design is concerned with the workings of particular markets in order to fix them when they are broken or to build markets when they are missing. Practical applications of market design theory has included labor market matching, organ transplantation, school choice, university admissions, and more.

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" and "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.