Description Usage Arguments Details Value Examples
This function computes the GaleShapley algorithm and finds a solution to the
college admissions problem. In the studentoptimal college admissions
problem, n
students apply to m
colleges, where each college has
s
slots.
1 2 3 4 5 6 7 8 
studentUtils 
is a matrix with cardinal utilities of the students. If
there are 
collegeUtils 
is a matrix with cardinal utilities of colleges. If there
are 
studentPref 
is a matrix with the preference order of the proposing
side of the market (only required when 
collegePref 
is a matrix with the preference order of the courted side
of the market (only required when 
slots 
is the number of slots that each college has available. If this
is 1, then the algorithm is identical to

studentOptimal 
is 
The algorithm works analogously to galeShapley.marriageMarket. The
GaleShapley 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 GaleShapley 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.
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 i
th
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 j
th 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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46  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 studentoptimal algorithm
results.studentoptimal < galeShapley.collegeAdmissions(
studentUtils = studentUtils,
collegeUtils = collegeUtils,
slots = 2,
studentOptimal = TRUE
)
results.studentoptimal
# run the collegeoptimal 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 studentoptimal algorithm
results.studentoptimal < galeShapley.collegeAdmissions(
studentPref = studentPref,
collegePref = collegePref,
slots = 2,
studentOptimal = TRUE
)
results.studentoptimal
# run the collegeoptimal algorithm
results.collegeoptimal < galeShapley.collegeAdmissions(
studentPref = studentPref,
collegePref = collegePref,
slots = 2,
studentOptimal = FALSE
)
results.collegeoptimal

Loading required package: Rcpp
$unmatched.students
[1] 7 12 17 19 24
$unmatched.colleges
integer(0)
$matched.colleges
[,1] [,2]
[1,] 20 11
[2,] 1 8
[3,] 5 18
[4,] 10 15
[5,] 21 6
[6,] 25 13
[7,] 23 22
[8,] 2 14
[9,] 16 3
[10,] 4 9
$matched.students
[,1]
[1,] 2
[2,] 8
[3,] 9
[4,] 10
[5,] 3
[6,] 5
[7,] NA
[8,] 2
[9,] 10
[10,] 4
[11,] 1
[12,] NA
[13,] 6
[14,] 8
[15,] 4
[16,] 9
[17,] NA
[18,] 3
[19,] NA
[20,] 1
[21,] 5
[22,] 7
[23,] 7
[24,] NA
[25,] 6
$unmatched.colleges
integer(0)
$unmatched.students
[1] 7 12 17 19 24
$matched.colleges
[,1] [,2]
[1,] 20 11
[2,] 8 1
[3,] 18 5
[4,] 10 13
[5,] 21 6
[6,] 25 15
[7,] 22 23
[8,] 14 2
[9,] 3 16
[10,] 9 4
$matched.students
[,1]
[1,] 2
[2,] 8
[3,] 9
[4,] 10
[5,] 3
[6,] 5
[7,] NA
[8,] 2
[9,] 10
[10,] 4
[11,] 1
[12,] NA
[13,] 4
[14,] 8
[15,] 6
[16,] 9
[17,] NA
[18,] 3
[19,] NA
[20,] 1
[21,] 5
[22,] 7
[23,] 7
[24,] NA
[25,] 6
$unmatched.students
[1] 7 12 17 19 24
$unmatched.colleges
integer(0)
$matched.colleges
[,1] [,2]
[1,] 20 11
[2,] 1 8
[3,] 5 18
[4,] 10 15
[5,] 21 6
[6,] 25 13
[7,] 23 22
[8,] 2 14
[9,] 16 3
[10,] 4 9
$matched.students
[,1]
[1,] 2
[2,] 8
[3,] 9
[4,] 10
[5,] 3
[6,] 5
[7,] NA
[8,] 2
[9,] 10
[10,] 4
[11,] 1
[12,] NA
[13,] 6
[14,] 8
[15,] 4
[16,] 9
[17,] NA
[18,] 3
[19,] NA
[20,] 1
[21,] 5
[22,] 7
[23,] 7
[24,] NA
[25,] 6
$unmatched.colleges
integer(0)
$unmatched.students
[1] 7 12 17 19 24
$matched.colleges
[,1] [,2]
[1,] 20 11
[2,] 8 1
[3,] 18 5
[4,] 10 13
[5,] 21 6
[6,] 25 15
[7,] 22 23
[8,] 14 2
[9,] 3 16
[10,] 9 4
$matched.students
[,1]
[1,] 2
[2,] 8
[3,] 9
[4,] 10
[5,] 3
[6,] 5
[7,] NA
[8,] 2
[9,] 10
[10,] 4
[11,] 1
[12,] NA
[13,] 4
[14,] 8
[15,] 6
[16,] 9
[17,] NA
[18,] 3
[19,] NA
[20,] 1
[21,] 5
[22,] 7
[23,] 7
[24,] NA
[25,] 6
Add the following code to your website.
For more information on customizing the embed code, read Embedding Snippets.