A Protocol For College Admission¶
Next, we are going to talk about a generalization of the stable marriage problem. The problem we’re going to talk about is a generalization of the one done in lecture. In the new problem, there are N students \(s_1, s_2, \dots , s_N and M\) universities \(u_1, u_2, \dots , u_M\).
University \(u_i\) has \(n_i\) slots for students, and we’re guaranteed that \(\sum_{i=1}^M n_i = N\). Each student ranks all universities (no ties) and each university ranks all students (no ties).
Design an algorithm to assign students to universities with the following properties
Every student is assigned to one university.
\(\forall i, u_i\) gets assigned \(n_i\) students.
- There does not exist \(s_i, s_j , u_k, u_l\) where \(s_i\) is assigned to \(u_k\), \(s_j\) is assigned to \(u_l\),
\(s_j\) prefers \(u_k\) to \(u_l\), and \(u_k\) prefers \(s_j\) to \(s_i\).
- It is student-optimal. This means that of all possible assignments satisfying the first three properties,
the students get their top choice of university amongst these assignments. The algorithm will be a slight modification of the mating algorithm given in lecture.
Before we can say anything about our algorithm, we need to show that it terminates. Show that the algorithm terminates after NM + 1 days
The algorithm terminates when each university has every slot filled with students. Each iteration, students ‘apply’ to the university they rank highest that they haven’t crossed off already. If a university has more applicants than slots, they order the applicants by their own ranking. They then reject any that exceed the number of slots they have available (so lowest ranked get rejected first).
This means at least one student is rejected by one university on each iteration. If there are no rejections, it means every slot is filled, so the algorithm terminates.
Since there are N students and M universities, each student can try each university at most, once (which gives us \(N \cdot M\)). At this point every student will have found a match, so the algorithm terminates. \(\blacksquare\)
Next, we will show that the four properties stated earlier are true of our algorithm. To start, let’s show the following: if during some day a university \(\ u_j\ \) has at least \(\ n_j\ \) applicants, then when the algorithm terminates it accepts exactly \(\ n_j\ \) students.
When a university receives any application, the university is those applicants top choice so far. This means, unless they are rejected by the university, they will still be applying to it on the next iteration.
Since \(n_j\) refers to the capacity of the university, The university will only reject students \(n_j + 1\) and beyond. This means there are still \(n_j\) applicants for whom \(u_j\) is their top choice, and so they will apply on the next iteration.
By this, we can conclude that there will be at least \(n_j\) applications for university \(u_j\) when the algorithm terminates. \(\blacksquare\)
Next, show that every student is assigned to one university.
Invariant: If a university, \(u_i\) rejects a student, \(s_j\), it’s because there are \(n_i\) students ranked higher than \(s_j\) also applying.
Proof: Suppose there are less than \(n_i\) students also applying. Then \(u_i\) still has space for \(s_j\), so it doesn’t reject \(s_j\). Therefore the invariant is vacuously true. \(\square\)
Theorem: Every student is assigned to one university.
Proof: By contradiction. Assume, when the algorithm terminates there exists a student rejected by all universities. That means every university has higher ranked students. But since the algorithm has terminated, it means every university has every slot filled. By since \(\sum_{i=1}^M n_i = N\) that can’t be possible, which is a contradiction. So we can conclude that every student is assigned to one university. \(\blacksquare\)
Next, show that for all i, \(\ u_i\ \) gets assigned \(\ n_i\ \) students.
Proof By contradiction. Assume, when the algorithm terminates there exists a university \(u_i\), for some \(i \le M\), that has x applicants, for some x less than \(n_i\). Since the algorithm has terminated we can assume no students have been rejected, and no universities has more applicants than slots. But since \(\sum_{i=1}^M n_i = N\), we know that there are \(N - n_i\) slots available at other universities, and \(N - x\) students applying to other universities. Since x is less than \(n_i\), then \(N - n_i < N - x\), which means there are less slots available than applicants. So by the algorithm, some of them will be rejected. So the algorithm cannot have terminated. This is a contradiction, so we can conclude that all universities get assigned a full roster of students. \(\blacksquare\)
Before continuing, we need to establish the following property. Suppose that on some day a university \(\ u_j\ \) has at least \(\ n_j\ \) applicants. Define the rank of an applicant \(\ s_i\ \) with respect to a university \(\ u_j\ \) as \(\ s_i\) ’s location on \(\ u_j\) ’s preference list. So, for example, \(\ u_j\) ’s favorite student has rank 1. Show that the rank of \(\ u_j\) ’s least favorite applicant that it says “Maybe, …” to cannot decrease (e.g., going from 1000 to 1005 is decreasing) on any future day.
Note that \(\ u_j\) ’s least favorite applicant might change from one day to the next.
If \(s_i\) was previously the least favourite accepted applicant, and there were at least \(n_j\) applicants, then all slots were filled.
If a student is not rejected, they continue to apply to the same university, because that university is currently their top choice, so the next iteration those \(n_j\) students will continue to apply to \(u_j\).
Suppose another student, \(s_k\) applies on the next iteration as well. If \(s_k\) is preferred by the university, then \(s_i\) will by bumped off the list, in favour of the next highest ranked student (which may or may not be \(s_k\)).
Suppose \(s_k\) was ranked lower than \(s_i\), then the university would prefer \(s_i\) over \(s_k\), so they would reject \(s_k\) because there are no more slots left.
So the least favourite applicant’s ranking can get no lower than \(s_i\)’s ranking. \(\blacksquare\)
Next, show there does not exist \(\ s_i, s_j, u_k,\ and\ u_l\ \) where \(\ s_i\ \) is assigned to \(u_k\), \(s_j\ \) is assigned to \(u_l\), \(s_j\ \) prefers \(\ u_k\ \) to \(\ u_l\ \), and \(\ uk\ \) prefers \(\ s_j\ \) to \(\ s_i\ \). Note that this is analogous to a “rogue couple” considered in lecture.
Proof: By contradiction.
Suppose we have a student, \(s_r\) and a university \(u_g\) that are not matched up, and form a rogue couple.
Case 1: \(u_g\) rejected \(s_r\) for another student. But then \(u_g\) has a preferred match, so they are not a rogue couple.
Case 2: The algorithm terminated before \(s_r\) applied to \(u_g\). But then \(s_r\) was accepted by a university they prefer over \(u_g\), so they are not a rogue couple.
This proves that for any pair, there are no rogue couples. \(\blacksquare\)
Finally, we show in a very precise sense that this algorithm is student-optimal. As in lecture, define the realm of possibility of a student to be the set of all universities u, for which there exists some assignment satisfying the first three properties above, in which the student is assigned to u. Of all universities in the realm of possibility of a student we say that the student’s favorite is optimal for that student.
Show that each student is assigned to its optimal university.
Suppose we have student \(s_i\) that is the first to not be assigned their optimal university, \(u_k\). \(u_k\) must have rejected \(s_i\) in favour of \(n_k\) other students \(s_a \dots s_j\) where \(n_k\) is the maximum capacity of \(u_k\).
Since \(s_i\) was the first to be rejected by their optimal university, All students in \(s_a \dots s_j\) haven’t been rejected by their optimal university, and so must rank \(u_k\) better than or equal to their optimal university.
Since \(u_k\) is in \(s_i\)’s realm of possibility, there must be some stable matching, S, where \(s_i\) could be assigned to \(u_k\).
We know \(u_k\) ranks all of the students in \(s_a \dots s_j\) better than \(s_i\). However, in S, one of the students in \(s_a \dots s_j\), let’s say \(s_j\), would have to be matched with another university, \(u_l\), which it ranks worse than \(u_k\), since by accepting \(s_i\), there would be no space for \(s_j\).
So \(s_j\) prefers \(u_k\) to \(u_l\), and \(u_k\) prefers \(s_j\) to \(s_i\). This forms a rogue couple, which contradict the three properties above.
Therefore, there cannot exist a stable matching where \(s_i\) is rejected by their optimal choice. It follows then, that any given student’s true optimal choice is the university they were not rejected from, which is the one they end up with. \(\blacksquare\)