galeShapley.collegeAdmissions {matchingR}

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

studentUtils

is a matrix with cardinal utilities of the students. If there are n students and m colleges, then this matrix will be of dimension m by n. The i,jth element refers to the payoff that student j receives from being matched to college i.

collegeUtils

is a matrix with cardinal utilities of colleges. If there are n students and m colleges, then this matrix will be of dimension n by m. The i,jth element refers to the payoff that college j receives from being matched to student i.

studentPref

is a matrix with the preference order of the proposing side of the market (only required when studentUtils is not provided). If there are n students and m colleges in the market, then this matrix will be of dimension m by n. The i,jth element refers to student j's ith most favorite college. Preference orders can either be specified using R-indexing (starting at 1) or C++ indexing (starting at 0).

collegePref

is a matrix with the preference order of the courted side of the market (only required when collegeUtils is not provided). If there are n students and m colleges in the market, then this matrix will be of dimension n by m. The i,jth element refers to individual j's ith most favorite partner. Preference orders can either be specified using R-indexing (starting at 1) or C++ indexing (starting at 0).

slots

is the number of slots that each college has available. If this is 1, then the algorithm is identical to galeShapley.marriageMarket. slots can either be a integer or a vector. If it is an integer, then all colleges have the same number of slots. If it is a vector, it must have as many elements as there are colleges where each element refers to the number of slots at a particular college.

studentOptimal

is TRUE if students apply to colleges. The resulting match is student-optimal. studentOptimal is FALSE if colleges apply to students. The resulting match is college-optimal.

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 when all students get matched.

• 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 all college slots get filled.

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