College Admissions and the Stability of Marriage

Posted on 6th March 2019

What paper?

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.

Context

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.

Main contributions

  • 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 hj, the top cj applicants (if there are that many) are added to hj'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 cj 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.

Why is it important?

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.

Posts