Week 7: Learning Across Boundaries

Week 7 Allocations: An Application of Gale-Shapley Algorithm

Rene Saran

Matching Students to Week 7 Projects: An Application of Gale-Shapley Algorithm

Week 7 is a distinctive aspect of the first-year curriculum at Yale-NUS College. From exploring apartheid, prejudice and discrimination in South Africa to delving into how memory works and is reflected in places and buildings in Singapore, the projects offer an amazing breadth of opportunities and possibilities. However, resources are limited – this is perhaps the first dismal lesson of any introductory economics class. In our context, this means that each Week 7 project offers only a limited quota of seats, and hence we have to find a way to ration in case there is excess demand for a project.

So how do we assign 250 students to 14 projects in a way that respects the quota of seats in each project? One possibility is to use a procedure similar to the ones used to admit students to public schools, donate kidneys to the needy, and match medical residents to hospitals: the Gale-Shapley algorithm described below gives us a solution worthy of the Nobel Prize in Economics (awarded to Lloyd S. Shapley and Alvin E. Roth in 2012).

Let’s first elaborate on the problem at hand. This is what we know: the number of students, the number of projects, and the quota of seats for each project. What we don’t know are the preferences of the students over projects. Therefore, we need a procedure that is strategy-proof (students cannot lie about their preferences in order to improve their chances of getting accepted at a higher ranked project). At the same time, we want our procedure to assign students to projects in such a way that the resulting assignment is efficient (so that we cannot find another assignment of students to projects that, when compared to the assignment obtained under our procedure, makes at least one agent – student or project – better off without making any other agent worse off) and respects the quota of seats in each project. The Gale-Shapley algorithm satisfies all these requirements.

The Gale-Shapley algorithm views students and projects as two sides of a market in which all agents (students and projects) enter their own rankings of the agents on the opposite side – students rank projects and projects rank students. In our case, projects do not have preferences over students – we like all of you equally! Nevertheless, we need to generate a ranking of students for each project in order to apply the algorithm. We can do that for each project by randomly picking students one-by-one, which will be the ranking of students by that project. We can generate 250 (factorial) rankings using this scheme, which is a number greater than 1 followed by 398 zeros! Therefore, this scheme allows different projects to have different rankings of students.[1] Next, we will ask each student to submit his/her ranking of all 14 projects. Once we have the rankings of all agents on both sides of the market, we will run the algorithm as follows:

Round 1

  • Step 1: Match each student to his or her top-ranked project.
  • Step 2: If there are more seats in a given project than the number of students that are matched to that project, then conditionally accept all students. If there are more students than seats, then fill the quota of seats by conditionally accepting those students that are ranked highest according to the project’s randomly generated ranking of students. Reject all others.

At the end of Round 1, some students will have been conditionally accepted into projects, while others will have been rejected. The next rounds will continue until all students are placed.

Iterative Rounds

  • Step 1: Match each rejected student to his or her next best project.
  • Step 2: For each project, compare the quota of seats with the total number of students that are either newly matched to the project or have been conditionally accepted by the project in previous rounds. The latter number reflects the demand for the project. If the demand for the project exceeds the quota of seats, go back to the project’s randomly generated ranking and fill the quota of seats by conditionally accepting those students with the highest ranks. Otherwise, conditionally accept all students.

This algorithm will stop when all students have been conditionally accepted by some project. At this point, CIPE will send notifications to all those students that were only conditionally accepted until then. This gives an assignment of students to projects.

[1] The definition of efficiency given above takes these ranking of students by projects as the true preferences of the projects. This is not true in our setting since projects are actually indifferent over students. So we should in fact use a stronger definition of efficiency: we cannot find another assignment of students to projects that, when compared to the assignment obtained under our procedure, makes at least one student better off without making any other studentworse off. It can be shown that Gale-Shapley algorithm is not efficient in this strong sense. One way out of this problem is to select one randomly generated ranking of students (i.e., 1 out of 210 rankings) and have all projects rank students according to the selected ranking. If we now run the Gale-Shapley algorithm, then the resulting assignment will be strategy proof and efficient in the strong sense. We will follow this procedure while trying to minimise the number of students who receive their lower ranked projects.