Jyotirmoy
Bhattacharya
Admissions to the
undergraduate programs of Delhi University happen through a chaotic,
decentralized system which imposes unnecessary work and uncertainty on colleges
and students every year. It does not have to be so. There exists more than half
a century of scholarship and practice on designing systems that match two
groups of entities such as colleges and students while taking into account the
preferences of all participants. It is time that Delhi University looks
seriously into implementing such a system for its admission process.
Here is how the present system
works. For every program of study that it offers, each college publishes a
cut-off percentage of marks. Every applicant whose average marks in their best
four subjects in the school-leaving examinations are above the announced
cut-off percentage is then eligible to join that program. Different cut-off
percentages apply to students depending on whether they belonged to the arts,
science or commerce streams in school.
Sometimes programs impose additional conditions such as a minimum
percentage of marks in mathematics or English.
Since there is a common pool
of students applying to different colleges and programs, not all students who
are offered admissions in a program join. So the process has to be run in
multiple rounds. Colleges start with high cutoffs and based on the actual
number of admissions in each round they must reduce the cut-offs to fill the
remaining seats. As the cut-offs fall, students who get offers from their more
preferred programs leave the colleges they had joined in the earlier rounds,
creating new vacancies which have to be filled in later rounds.
of students applying to different colleges and programs, not all students who
are offered admissions in a program join. So the process has to be run in
multiple rounds. Colleges start with high cutoffs and based on the actual
number of admissions in each round they must reduce the cut-offs to fill the
remaining seats. As the cut-offs fall, students who get offers from their more
preferred programs leave the colleges they had joined in the earlier rounds,
creating new vacancies which have to be filled in later rounds.
This process, perhaps unconsciously,
is a distorted form of the matching algorithm suggested by the mathematicians
David Gale and Lloyd Shapley in a landmark 1962 paper.[1]
The version of Gale and Shapley’s “deferred acceptance” algorithm that is
closest to the current process would work as follows: We refer to a distinct
college/programme combination (say Economics (Hons.) in Hindu College) as a
‘program’. We assume that each programme has a ranking over students and each
student has a ranking over programs.We do not assume that each program has
the same ranking over students or each student has the same ranking over
programs. While it is easy to see that different students have different
preferences, heterogeneity of preferences among programs is also natural. A
science program may prefer students who had science in school to students who
had economics, while an economics programme may have the opposite preference.
is a distorted form of the matching algorithm suggested by the mathematicians
David Gale and Lloyd Shapley in a landmark 1962 paper.[1]
The version of Gale and Shapley’s “deferred acceptance” algorithm that is
closest to the current process would work as follows: We refer to a distinct
college/programme combination (say Economics (Hons.) in Hindu College) as a
‘program’. We assume that each programme has a ranking over students and each
student has a ranking over programs.We do not assume that each program has
the same ranking over students or each student has the same ranking over
programs. While it is easy to see that different students have different
preferences, heterogeneity of preferences among programs is also natural. A
science program may prefer students who had science in school to students who
had economics, while an economics programme may have the opposite preference.
Suppose that the i-th
program has q(i) seats. There is a sequence of rounds. At the beginning of
the first round each program i makes an admission offer to the q(i)
students that it prefers most among all applicants. Each student who receives
an offer tentatively accepts the offer from the programme that they most
prefer and reject the rest. Suppose that programme i received n(i,1) rejections
in the first round. Then in the second round it makes an offer to its most
preferred n(i,1) applicants to whom it has not made an offer yet. Once
again each student chooses the most preferred option among the offers they have
received in this round as well as the offer they may have tentatively accepted
in the last round. They then reject the remaining offers (including possibly
the one they had tentatively accepted in the last round, if they now have a
better offer). The process gets repeated as long as any program has any
eligible applicant left. Since there is only a finite list of students, the
process must necessarily end after a finite number of rounds. Once the process
ends, students who have a tentatively accepted offer accept this offer finally.
program has q(i) seats. There is a sequence of rounds. At the beginning of
the first round each program i makes an admission offer to the q(i)
students that it prefers most among all applicants. Each student who receives
an offer tentatively accepts the offer from the programme that they most
prefer and reject the rest. Suppose that programme i received n(i,1) rejections
in the first round. Then in the second round it makes an offer to its most
preferred n(i,1) applicants to whom it has not made an offer yet. Once
again each student chooses the most preferred option among the offers they have
received in this round as well as the offer they may have tentatively accepted
in the last round. They then reject the remaining offers (including possibly
the one they had tentatively accepted in the last round, if they now have a
better offer). The process gets repeated as long as any program has any
eligible applicant left. Since there is only a finite list of students, the
process must necessarily end after a finite number of rounds. Once the process
ends, students who have a tentatively accepted offer accept this offer finally.
Gale
and Shapley showed that the matching produced is “stable”: for every
college-student pair not matched to each other, it is either the case that the
college finds the student inferior to the students it already has or the
student find the college inferior to the one it already has. Thus no
college-student pair has an incentive to disregard the assignment produced by
the algorithm and come to a private arrangement. This is a desirable property
for the acceptability of the system.
and Shapley showed that the matching produced is “stable”: for every
college-student pair not matched to each other, it is either the case that the
college finds the student inferior to the students it already has or the
student find the college inferior to the one it already has. Thus no
college-student pair has an incentive to disregard the assignment produced by
the algorithm and come to a private arrangement. This is a desirable property
for the acceptability of the system.
Since
Gale and Shapley’s paper, there has been a lot of theoretical work on this
problem as well as many practical implementations. The 2012 Sveriges Riksbank
Prize in Economic Sciences in Memory of Alfred Nobel went to Shapley and Alvin
Roth for their work in this area. In his work in the 1980s Roth had shown that
the procedure used by the central clearinghouse that matched medical students
to hospital residencies in the US was closely related to the Gale-Shapley
algorithm. Later Roth worked to improve this matching process which is now
known as the “National Resident Match Program”. Roth and others have also
implemented matching markets for many other problems such as school admissions
and organ donations.[2]
The design of matching markets is very much a mature area of economic practice
today.
Gale and Shapley’s paper, there has been a lot of theoretical work on this
problem as well as many practical implementations. The 2012 Sveriges Riksbank
Prize in Economic Sciences in Memory of Alfred Nobel went to Shapley and Alvin
Roth for their work in this area. In his work in the 1980s Roth had shown that
the procedure used by the central clearinghouse that matched medical students
to hospital residencies in the US was closely related to the Gale-Shapley
algorithm. Later Roth worked to improve this matching process which is now
known as the “National Resident Match Program”. Roth and others have also
implemented matching markets for many other problems such as school admissions
and organ donations.[2]
The design of matching markets is very much a mature area of economic practice
today.
In
all these applications of the Gale-Shapley algorithm the matching is carried
out by a centralised agency. All parties submit their preferences to this
agency and the multiple rounds of the algorithm are carried out by a computer
program using these preferences as inputs. The final result is then
communicated to the participants.
all these applications of the Gale-Shapley algorithm the matching is carried
out by a centralised agency. All parties submit their preferences to this
agency and the multiple rounds of the algorithm are carried out by a computer
program using these preferences as inputs. The final result is then
communicated to the participants.
In
contrast the version of Gale-Shapley used in Delhi University admissions
requires actual humans to act out each round of the process. Instead of offers
we have cut-off percentages. Instead of tentative acceptances we have students
carrying out all the formalities of joining a college. Instead of rejecting
tentatively accepted offers we have students cancelling admissions to colleges
they had been admitted to in earlier rounds and then joining new ones.
contrast the version of Gale-Shapley used in Delhi University admissions
requires actual humans to act out each round of the process. Instead of offers
we have cut-off percentages. Instead of tentative acceptances we have students
carrying out all the formalities of joining a college. Instead of rejecting
tentatively accepted offers we have students cancelling admissions to colleges
they had been admitted to in earlier rounds and then joining new ones.
Not
only does this ‘manual’ implementation create unnecessary labour and paperwork
for colleges and students, it also means that only a distorted version of
Gale-Shapley can be implemented.
only does this ‘manual’ implementation create unnecessary labour and paperwork
for colleges and students, it also means that only a distorted version of
Gale-Shapley can be implemented.
Each
round of cut-offs in the Delhi University system must last at least a couple of
days. This is because in each round, students must find out the new cut-off
percentages from public announcements and then visit possibly two colleges: the
one they are rejecting and the one they are tentatively accepting. Colleges too
need time to admit students and cancel admissions. This means that relatively
few rounds of cutoffs are possible in the time available between the
announcements of results and the beginning of the college year. For example, in 2014 only ten rounds were
possible. The process began on the 1st of July and the tenth round
of cut-offs were announced on the 24th of July.
round of cut-offs in the Delhi University system must last at least a couple of
days. This is because in each round, students must find out the new cut-off
percentages from public announcements and then visit possibly two colleges: the
one they are rejecting and the one they are tentatively accepting. Colleges too
need time to admit students and cancel admissions. This means that relatively
few rounds of cutoffs are possible in the time available between the
announcements of results and the beginning of the college year. For example, in 2014 only ten rounds were
possible. The process began on the 1st of July and the tenth round
of cut-offs were announced on the 24th of July.
Given the small number of
feasible rounds, programs cannot afford to make only as many offers in a round
as they have vacancies left. Unless a college is highly preferred by many
students, it knows that many of its offers will be rejected. Thus, if it makes
only as many offers in each round as it has vacancies, it may find that it has
many unfilled vacancies when the time for admissions ends. Therefore, in
practice programs make many more offers than they have vacancies. To decide how
many more, programs must make estimates of the rejection rate. This introduces
an unnecessary uncertainty. Those running admissions must act like speculators,
trying to gauge the “pulse of the market”. If they are too liberal with offers
they many find themselves having to admit more students than they have
resources for. If they are too conservative, the matching process makes very
slow progress in that round. This slow progress would not be a problem for the
Gale-Shapley algorithm since there can be as many rounds as required. But it is
a problem in the time-limited Delhi University process since slow progress
means that the process might come to an end with vacancies unfilled
simultaneously with eligible students un-admitted.
feasible rounds, programs cannot afford to make only as many offers in a round
as they have vacancies left. Unless a college is highly preferred by many
students, it knows that many of its offers will be rejected. Thus, if it makes
only as many offers in each round as it has vacancies, it may find that it has
many unfilled vacancies when the time for admissions ends. Therefore, in
practice programs make many more offers than they have vacancies. To decide how
many more, programs must make estimates of the rejection rate. This introduces
an unnecessary uncertainty. Those running admissions must act like speculators,
trying to gauge the “pulse of the market”. If they are too liberal with offers
they many find themselves having to admit more students than they have
resources for. If they are too conservative, the matching process makes very
slow progress in that round. This slow progress would not be a problem for the
Gale-Shapley algorithm since there can be as many rounds as required. But it is
a problem in the time-limited Delhi University process since slow progress
means that the process might come to an end with vacancies unfilled
simultaneously with eligible students un-admitted.
More than half a century after
Gale and Shapley’s paper, in a city like Delhi with so many economists and mathematicians,
and with the Delhi School of Economics being part of Delhi University, one
would expect that the cut-off process would have already been replaced by a
central match that would save both students and colleges much trouble.
Gale and Shapley’s paper, in a city like Delhi with so many economists and mathematicians,
and with the Delhi School of Economics being part of Delhi University, one
would expect that the cut-off process would have already been replaced by a
central match that would save both students and colleges much trouble.
In fact there is an even
stronger argument in favour of moving towards a centralised match. A better
outcome for students can be produced by a mirror image of the “deferred
acceptance” algorithm described above. In this version, instead of programs
making offers, it is students who in each round put forward their names to
their most preferred programme which has not rejected them yet. In each round,
a programme with capacity q tentatively accepts it most preferred q
students from among the students tentatively accepted earlier and the proposals
received in the current round and rejects the rest.
stronger argument in favour of moving towards a centralised match. A better
outcome for students can be produced by a mirror image of the “deferred
acceptance” algorithm described above. In this version, instead of programs
making offers, it is students who in each round put forward their names to
their most preferred programme which has not rejected them yet. In each round,
a programme with capacity q tentatively accepts it most preferred q
students from among the students tentatively accepted earlier and the proposals
received in the current round and rejects the rest.
For
this version of deferred acceptance in which students make proposals, Gale and Shapley proved: “Every
applicant is at least as well off under the assignment given by the deferred
acceptance procedure as he would be under any other stable assignment” (ibid, Theorem 2).
this version of deferred acceptance in which students make proposals, Gale and Shapley proved: “Every
applicant is at least as well off under the assignment given by the deferred
acceptance procedure as he would be under any other stable assignment” (ibid, Theorem 2).
A simple example illustrates
this. Suppose that there are two programs A and B with a capacity
of one each and two students X and Y. Suppose student X
prefers A to B and Y prefers B to A. Suppose
program A prefers Y to X and program B prefers X
to Y. Then if programs propose A will make an offer to Y
and B will make an offer to X and this will also be the final
assignment since neither student will reject their offer as they have just one
offer. On the other hand if students propose then X will propose to A
and Y will propose to B and this will be the final assignment
since each college has just as many proposals as vacancies. One can check that
both the assignments are stable, but the second assignment makes both the
students better off compared to the first.
this. Suppose that there are two programs A and B with a capacity
of one each and two students X and Y. Suppose student X
prefers A to B and Y prefers B to A. Suppose
program A prefers Y to X and program B prefers X
to Y. Then if programs propose A will make an offer to Y
and B will make an offer to X and this will also be the final
assignment since neither student will reject their offer as they have just one
offer. On the other hand if students propose then X will propose to A
and Y will propose to B and this will be the final assignment
since each college has just as many proposals as vacancies. One can check that
both the assignments are stable, but the second assignment makes both the
students better off compared to the first.
However, the student-proposes
version of the algorithm would be much harder to run manually than the
college-proposes version. Rather than publishing just a small number of cut-off
percentages each program would have rank the list of proposals received (which
would change from round to round) and put up lists of tentatively accepted
students in each round. A student tentatively accepted in one round might
possibly be rejected in a later round so all students would be uncertain
regarding their final position and would have to be ready to make new offers as
long as the admission process continues. This seems impractical. Thus a move to
a centralized match is justified not just for the sake of removing the
unnecessary work of the manual system but also to allow a move to be made to
the student-proposes algorithm from a program-proposes algorithm.
version of the algorithm would be much harder to run manually than the
college-proposes version. Rather than publishing just a small number of cut-off
percentages each program would have rank the list of proposals received (which
would change from round to round) and put up lists of tentatively accepted
students in each round. A student tentatively accepted in one round might
possibly be rejected in a later round so all students would be uncertain
regarding their final position and would have to be ready to make new offers as
long as the admission process continues. This seems impractical. Thus a move to
a centralized match is justified not just for the sake of removing the
unnecessary work of the manual system but also to allow a move to be made to
the student-proposes algorithm from a program-proposes algorithm.
It is not that Delhi
University does not have experience with centralized admission matches. In fact
when I was a student there in the late 90s, Delhi University did run a central
match for seats reserved for students from the Scheduled Castes and
Tribes. I’m not sure if it still does. But
this central match had a problem.
University does not have experience with centralized admission matches. In fact
when I was a student there in the late 90s, Delhi University did run a central
match for seats reserved for students from the Scheduled Castes and
Tribes. I’m not sure if it still does. But
this central match had a problem.
The Gale-Shapley algorithm
requires that the computer be provided with each colleges ranking of all
students and each students ranking of all colleges. The ranking of students by
colleges is easy since colleges rank students by a mechanical formula like the
average marks in the best four subjects adjusted by a fixed amount depending on
the stream of the students.
requires that the computer be provided with each colleges ranking of all
students and each students ranking of all colleges. The ranking of students by
colleges is easy since colleges rank students by a mechanical formula like the
average marks in the best four subjects adjusted by a fixed amount depending on
the stream of the students.
The ranking of colleges by
students follows no such simple pattern. The number of programs that a student
must rank is large: there are a few dozen colleges with a few dozen courses
each. It may be impractical to ask students to rank all possible combinations
as required by the Gale-Shapley algorithm. The system run for SC students asked
students to list only about a dozen course-college combinations in order of
preference. The result was that students who aimed too high would not get
selected in any of their choices and lower-ranked colleges would have vacant
seats, so university still had to run multiple rounds of matching. On the other
hand the students who aimed too low would miss out on better opportunities that
would be captured by more ambitious students.
students follows no such simple pattern. The number of programs that a student
must rank is large: there are a few dozen colleges with a few dozen courses
each. It may be impractical to ask students to rank all possible combinations
as required by the Gale-Shapley algorithm. The system run for SC students asked
students to list only about a dozen course-college combinations in order of
preference. The result was that students who aimed too high would not get
selected in any of their choices and lower-ranked colleges would have vacant
seats, so university still had to run multiple rounds of matching. On the other
hand the students who aimed too low would miss out on better opportunities that
would be captured by more ambitious students.
To implement Gale-Shapley for
Delhi University one would have to address this problem of eliciting
preferences. It is not possible to simply assume that students’ preferences are
lexicographic over colleges and courses in either order. That is one cannot
assume that students have separate ranking of colleges and courses and decide
in one of two ways: the prefer any course in a higher ranking college to any
other course in a lower ranked college; or, they prefer a higher ranked course
in any college to a lower ranked course in any other college. Rather we have to
allow for arbitrary rankings over college-course combinations.
Delhi University one would have to address this problem of eliciting
preferences. It is not possible to simply assume that students’ preferences are
lexicographic over colleges and courses in either order. That is one cannot
assume that students have separate ranking of colleges and courses and decide
in one of two ways: the prefer any course in a higher ranking college to any
other course in a lower ranked college; or, they prefer a higher ranked course
in any college to a lower ranked course in any other college. Rather we have to
allow for arbitrary rankings over college-course combinations.
At this point Delhi University’s
move to an online application system comes to the rescue. The system could ask
begin with one of the lexicographic orders discussed above: ask for a ranking
of colleges and courses and ask the student whether they consider the college
and course more important. Rank all college and course combinations that the
student is eligible for using this lexicographic preference but then allow the
student to manually edit the resulting ordering in any way they wish. By would
allow for arbitrary preferences while still giving students a good starting
point to start from.
move to an online application system comes to the rescue. The system could ask
begin with one of the lexicographic orders discussed above: ask for a ranking
of colleges and courses and ask the student whether they consider the college
and course more important. Rank all college and course combinations that the
student is eligible for using this lexicographic preference but then allow the
student to manually edit the resulting ordering in any way they wish. By would
allow for arbitrary preferences while still giving students a good starting
point to start from.
Futuristically, we can think
of an intelligent application system that tries to infer a student’s
preferences by offering the students few cleverly chosen pairwise comparisons.
The student would then be offered the option of manually correcting the
preferences inferred by the system. By allowing a final manual check, a poor
implementation of the preference inference system would only mean some more
corrections will have to be made by students. Also, to the extent that there is
some similarity in how students rank college and programs, the preference
inference system can learn from the manual corrections to ask better questions
and make better inferences in the future. While there is research in the area
of machine learning of systems that learn rankings, I am not aware of any
currently used system that learns rankings interactively in this way.
of an intelligent application system that tries to infer a student’s
preferences by offering the students few cleverly chosen pairwise comparisons.
The student would then be offered the option of manually correcting the
preferences inferred by the system. By allowing a final manual check, a poor
implementation of the preference inference system would only mean some more
corrections will have to be made by students. Also, to the extent that there is
some similarity in how students rank college and programs, the preference
inference system can learn from the manual corrections to ask better questions
and make better inferences in the future. While there is research in the area
of machine learning of systems that learn rankings, I am not aware of any
currently used system that learns rankings interactively in this way.
But the rationalisation of the
DU admission process is a well-defined problem where economists and mathematicians
of Delhi can pool together their skills to create a great deal of social
benefit.
DU admission process is a well-defined problem where economists and mathematicians
of Delhi can pool together their skills to create a great deal of social
benefit.
[1] Gale D. and L.S.
Shapley (1962), “College Admissions and the Stability of Marriage”, The American Mathematical Monthly, 69(1).
Shapley (1962), “College Admissions and the Stability of Marriage”, The American Mathematical Monthly, 69(1).
[2] See Roth’s Nobel
lecture and his recent popular book, Roth, Alvin (2015).Who Gets What — and Why: The New Economics of
Matchmaking and Market Design, Houghton Mifflin Harcout.
lecture and his recent popular book, Roth, Alvin (2015).Who Gets What — and Why: The New Economics of
Matchmaking and Market Design, Houghton Mifflin Harcout.
Jyotirmoy Bhattacharya is Assistant Professor at Ambedkar University, Delhi.
