Gale-Shapley Algorithm: College Admissions Problem

Description

This function computes the Gale-Shapley algorithm and finds a solution to the college admissions problem. In the student-optimal college admissions problem, n students apply to m colleges, where each college has s slots.

Usage

galeShapley.collegeAdmissions(studentUtils = NULL, collegeUtils = NULL,
  studentPref = NULL, collegePref = NULL, slots = 1,
  studentOptimal = TRUE)

Arguments

Details

The algorithm works analogously to galeShapley.marriageMarket. The Gale-Shapley algorithm works as follows: Students ("the proposers") sequentially make proposals to each of their most preferred available colleges ("the reviewers"). A college can hold on to at most s proposals at a time. A college with an open slot will accept any application that it receives. A college that already holds on to s applications will reject any application by a student that it values less than her current set of applicants. If a college receives an application from a student that it values more than its current set of applicants, then it will accept the application and drop its least preferred current applicant. This process continues until all students are matched to colleges.

The Gale-Shapley Algorithm requires a complete specification of students' and colleges' preferences over each other. Preferences can be passed on to the algorithm in ordinal form (e.g. student 3 prefers college 1 over college 3 over college 2) or in cardinal form (e.g. student 3 receives payoff 3.14 from being matched to college 1, payoff 2.51 from being matched to college 3 and payoff 2.13 from being matched to college 2). Preferences must be complete, i.e. all students must have fully specified preferences over all colleges and vice versa.

In the version of the algorithm that is implemented here, all individuals – colleges and students – prefer being matched to anyone to not being matched at all.

The algorithm still works with an unequal number of students and slots. In that case some students will remain unmatched or some slots will remain open.

Value

A list with elements that specify which student is matched to which college and who remains unmatched. Suppose there are n students and m colleges with s slots. The list contains the following items:

• matched.students is a vector of length n whose ith element contains college that student i is matched to. Students that remain unmatched will be listed as being matched to college NA.

• matched.colleges is a matrix of dimension m by s whose jth row contains the students that were admitted to college j. Slots that remain open show up as being matched to student to NA.

• unmatched.students is a vector that lists the remaining unmatched students This vector will be empty whenever n<=m*s.

• unmatched.colleges is a vector that lists colleges with open slots. If a college has multiple open slots, it will show up multiple times. This vector will be empty whenever m*s<=n.

Examples

ncolleges = 10
nstudents = 25

# randomly generate cardinal preferences of colleges and students
collegeUtils = matrix(runif(ncolleges*nstudents), nrow=nstudents, ncol=ncolleges)
studentUtils = matrix(runif(ncolleges*nstudents), nrow=ncolleges, ncol=nstudents)

# run the student-optimal algorithm
results.studentoptimal = galeShapley.collegeAdmissions(studentUtils = studentUtils,
                              collegeUtils = collegeUtils,
                              slots = 2,
                              studentOptimal = TRUE)
results.studentoptimal

# run the college-optimal algorithm
results.collegeoptimal = galeShapley.collegeAdmissions(studentUtils = studentUtils,
                              collegeUtils = collegeUtils,
                              slots = 2,
                              studentOptimal = FALSE)
results.collegeoptimal

# transform the cardinal utilities into preference orders
collegePref = sortIndex(collegeUtils)
studentPref = sortIndex(studentUtils)

# run the student-optimal algorithm
results.studentoptimal = galeShapley.collegeAdmissions(studentPref = studentPref,
                             collegePref = collegePref,
                             slots = 2,
                             studentOptimal = TRUE)
results.studentoptimal

# run the college-optimal algorithm
results.collegeoptimal = galeShapley.collegeAdmissions(studentPref = studentPref,
                             collegePref = collegePref,
                             slots = 2,
                             studentOptimal = FALSE)
results.collegeoptimal

Results