Fixing Education, One Algorithm at a Time

Associate Professor Yash Kanoria helped design an algorithm to fill seats in India’s top tech schools, with implications for the US school system.

Print this page
Kanoria teaches analytics and marketplace design at the Business School. His work has helped fill seat vacancies across India's premier tech schools.

Among the most select universities in the world, the prestigious Indian Institutes of Technology are considered the Ivy League of India. The schools have an admission rate of less than 1 percent for the 1.2 million annual applicants who, in many cases, have spent a small fortune on specialized coaching to gain admission.

Which made it all the more puzzling and frustrating that, until recently, about 6 percent of available seats at the Indian Institutes of Technology (IITs) were consistently unfilled — a problem that Yash Kanoria, the Sidney Taurel Associate Professor of Business, spent more than three years working to correct through innovative changes to the seat allocation process.

“It’s a serious issue that seats were going vacant at these top institutions even though there were so many people who wanted these seats,” says Kanoria, who teaches in the Decision, Risk, and Operations Division. “Now with our new process, the IIT seats are almost entirely filled.”

Working with Surender Baswana and Utkarsh Patange of IIT Kanpur, Partha Pratim Chakrabarti of IIT Kharagpur, and Sharat Chandran of IIT Bombay, Kanoria designed a system that has reduced vacancies at the IITs by nearly 75 percent, according to their paper, which is forthcoming in the journal Interfaces. Named a finalist for the 2018 Daniel H. Wagner Prize for Excellence in Operations Research Practice, the research points at a way forward for how other schools in India and around the world can fill seats and boost educational opportunities.

“It’s a large-scale project in one of the most populous countries in the world for some of the most desirable educational opportunities,” says Kanoria. “It’s important in terms of fueling the growth of the country to have well-trained people, and certainly there’s no excuse for wasting seats.”

A global problem

How to efficiently fill school seats is a problem beyond India, also affecting public education systems across the United States where students must apply centrally and get “matched” to a school. Each year in New York City, about 80,000 eighth graders are matched by algorithm to high schools throughout the city. San Francisco also uses an algorithm to match thousands of children every year to seats in more than a hundred programs.

The challenge in the US, and also in India, is that candidates receive offers from outside the centralized public school system after the main centralized admissions process is conducted. This makes the overall process dynamic and in flux.

Because of the complex task of dynamic matching in school choice — not to mention the political bureaucracy — seats in desired schools go unfilled while students are left with subprime options. In New York City, about 10 percent of eighth graders allotted seats ultimately choose not to enroll in a public high school, creating a last-minute dash for administrators to fill empty seats. As of the last several years, according to Kanoria, city administrators gave up entirely on trying to fill the vacated seats, seemingly a consequence of the logistical problems. Meanwhile in San Francisco, some families opt out of the public school system because of all the paperwork and time required.

Kanoria’s work suggests there is a better way. The associate professor became involved in the overhaul of his country’s seat allocation system for engineering colleges in 2013, after it came under court order to reform in response to a public interest lawsuit over the legacy system’s inefficiencies. Kanoria was familiar with the system, having graduated from IIT-Bombay in 2007 at the top of his class; by 2013, he says, “I was developing a research agenda in marketplace design into which this project fit perfectly.”

India’s fix

The challenge was to merge the admission process of the IITs (which ranked candidates in one way), with the admission process of other centrally funded engineering colleges (which ranked candidates in a different way), in order to improve efficiency in filling seats by bringing candidates’ “outside” options into a single centralized system. Kanoria proposed an approach based on the Deferred Acceptance (DA) algorithm — a centerpiece of the 2012 Nobel Prize in Economics awarded to Lloyd Shapley and Alvin Roth. DA collects candidates’ preference ranking over programs, and then — on a computer — each candidate virtually applies successively to her most preferred program from which she has not yet been rejected, until there are no more rejections.

Over 18 months, Kanoria’s team developed a transparent DA-based algorithm to match undergraduate applicants to the 35,000 available seats in more than 500 programs across India’s public technical universities, while accounting for a web of affirmative action rules and other complexities. The team also created the Joint Seat Allocation Authority, known as JoSAA, to manage the admissions process.

Among the innovations of their algorithm were ways to more fairly reserve seats to meet diversity quotas and a more efficient way to “dereserve” unfilled quota seats. Other modifications — such as conducting seven rounds of admissions before classes begin, allowing applicants to withdraw upon receiving outside offers of admission, and conducting a centralized special round to fill remaining vacancies after classes began — further boosted matches and lowered vacancies.

Since the changes were implemented in 2015, vacancies at the 23 IITs have fallen 75 percent to under 200 seats per year, out of 10,000 available.

However, vacancies remain high at the 31 National Institutes of Technology (NITs) and 23 Indian Institutes of Information Technology (IIITs), with nearly a quarter of their 25,000 seats remaining unfilled when classes begin and 10 percent remaining unfilled even after the special allocation round — largely because of a lack of safeguards to ensure seriousness of candidates. For example, these schools, unlike the IITs, allow accepted applicants to withdraw from the process at the last minute and retake the entrance exam a year later.

These ongoing vacancies in India’s public tech schools represent a waste of educational resources and taxpayer money that Kanoria is still fighting to fix. He is now pushing for the Ministry of Human Resource Development, which oversees the public education system, to update the admissions process with a few simple rule changes that would help fill seats.

“As a market designer, it pains me greatly to see these resources flushed into the Indian Ocean,” says Kanoria. “Engineering is one of the most sought-after degrees to get in India, and these are the top institutions. People invest a lot of time, energy, and money to prepare for the entrance exam and try to get the best seat.”  

‘Impactful research’

Along with the work in India, Kanoria has also studied how to improve matching in school choice in the US, where schools face a similar challenge of candidates dropping out of the system at a late stage in the admissions process.

In a separate paper that Kanoria authored with Irene Lo of Stanford University, Itai Feigenbaum of the City University of New York, and Jay Sethuraman of Columbia University’s Department of Industrial Engineering and Operations Research, the researchers mathematically show that one way to improve efficiency in the seat allocation process is by reversing the lottery order before filling vacated seats. The lottery here is the one used to break ties between students who have identical priority at a school.

“This small change would reduce how many students are being reassigned between rounds,” says Lo, who was earning her doctorate from Columbia at the time of the research. “It hopefully reduces the administrative costs and the burden to students.”

Based on simulation experiments with New York City admissions data, only half as many incoming high schoolers would need to be reassigned to new schools under the proposed reverse lottery method, which would translate to savings in time and effort for administrators, students, and parents. The researchers are now in talks with officials from the New York City Department of Education about implementing the design in select kindergartens on a trial basis.

To effect this kind of change in any public education system takes an ambitious and determined research team, says Costis Maglaras, the David and Lyn Silfen Professor of Business and former chair of the Decision, Risk, and Operations Division. He lauded the work as an example of how insights in marketplace design can go beyond boosting bottom lines to being societally beneficial.

“Education is one of the most important things that society can do to elevate itself over time,” says Maglaras. “This is an important problem, it touches hundreds of thousands of students, so I think this research can be impactful.”

About the researcher

Yash Kanoria

Yash Kanoria is an Associate Professor of Business in the Decision, Risk and Operations division at Columbia Business School, working primarily on matching markets...

Read more.
articles by Topic