Posted on 6th March 2019

David Gale and Lloyd S. Shapley. College Admissions and the Stability of Marriage. The American Mathematical Monthly, Vol. 69, No. 1 (Jan., 1962), pp. 9-15.

This paper studies the College Admissions problem, now more frequently referred to as the *Hospital/Residents problem* (HR). Please see The Hospitals/Residents problem (HR) for more information.

- The
*Deferred-Acceptance Algorithm*(more commonly known in the Computer Science field as the*Gale-Shapley Algorithm*). - In this algorithm, each resident starts by applying to their favourite hospital. For hospital h
_{j}, the top c_{j}applicants (if there are that many) are added to h_{j}'s waiting list, with all other applicants being rejected. Rejected applicants now apply to their next favourite hospital. At each step, hospitals keep the top c_{j}applicants (again, if there are that many) from the set of new applicants and their waiting list. The algorithm will terminate when all applicants are either on a waiting list or have been rejected but have no more hospitals to apply to. At this point the set of residents on each hospital's waiting list is accepted, and the resultant allocation is a stable matching. Time complexity: O(m), where m is the total length of the applicants preference lists. - The Gale-Shapley Algorithm may be run using either residents or hospitals as applicants. If residents are applicants then the algorithm is known as the
*Resident-Oriented Gale-Shapley Algorithm*(RGS). The resultant stable matching is*resident-optimal*in which each resident gains their best ranked hospital in any stable matching. - Similarly, if hospitals are the applicants, the algorithm is known as the
*Hospital-Oriented Gale-Shapley Algorithm*(HGS) which outputs a*hospital-optimal*stable matching (with an analogous definitions to above). - Although not explicitly mentioned in the paper, it is important to note that the
*resident-optimal*stable matching is also*hospital-pessimal*in that each hospital gains their worst set of residents in any stable matching. An analogous condition holds for the*hospital-optimal*stable matching. - Every instance of HR admits at least one stable matching.

This is a seminal paper on matching problems and describes the first formal definition of HR. In 2012, Lloyd S. Shapley and Alvin E. Roth were awarded the Nobel Prize in Economics for their work in this area.