Wednesday, July 8, 2015

Let's take the grind out of Delhi University admissions and make it more student-friendly in the bargain

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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

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.

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.

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.

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.

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.

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.

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.

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.

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.

[1]              Gale D. and L.S. 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.

Jyotirmoy Bhattacharya is Assistant Professor at  Ambedkar University, Delhi.

No comments:

Post a Comment

Comments are subject to moderation. It may take some time to appear in the blog.