###
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.

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.

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

the same ranking over students or each student has the same ranking over

programs.

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.

*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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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).

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

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.

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.

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.

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.

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.

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.

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.

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.

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.

Shapley (1962), “College Admissions and the Stability of Marriage”,

*The American Mathematical Monthly,*69(1).

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.

Matchmaking and Market Design,

*Jyotirmoy Bhattacharya is Assistant Professor at Ambedkar University, Delhi.*