We next describe our second class of mechanisms, which we call multi-stage (MS) mechanisms. To run stage 1 of MS-GS/TTC, we temporarily “remove” a group of studentsR1 and run standard GS or TTC on the remaining studentsR0\R1 (where R0 = S). Letting R1 be the bottommost ∑
l∈Lpl individuals according to ML, we know that regardless of how the students in R0 \R1 are matched, there are enough students in R1 to achieve a feasible matching by the end of the mechanism. After running GS/TTC on the students in R0\R1, we let these subjects’ assignments be final and they are taken off the market along with their assigned seats. Then, we repeat the process analogously for the subsequent stages.
7.4.1 Multi-stage GS/TTC (MS-GS/TTC)
For the MS mechanisms, we return to the original model (S, L, p, q,≻S,≻L,≻M L).
Recall that without loss of generality, the master list ranks students s1 ≻M L s2 ≻M L
· · · ≻M L sn. Since the description of MS is rather simple, we formally define MS-GS and MS-TTC simultaneously.
Start by setting R0 = S, p1l = pl, and ql1 = ql for all l ∈ L. In addition, let rk = ∑
l∈Lpkl be the number of students that will be reserved in Rk for k ≥ 1. Let M denote the matching that will be produced at the end of MS-GS/TTC. Initially, setM(t) = ∅ for all t∈S∪L.
Definition 52 [MS-GS/TTC]
Round k ≥1 (Repeat 1.-3. until all students are matched)
1. Set Rk = {sn−rk+1, sn−rk+2, . . . , sn}, i.e., Rk is the bottom rk students according to ≻M L.
2. Now, run the standard GS/TTC mechanism on the students in Rk−1\Rk with maximum quotas for the labs equal to (qkl)l∈L.
3. Obtain Mk as the matching of GS/TTC and M =M ∪Mk. 4. The parameters for each lab are reduced:
• qlk+1 =qlk− |Mk(l)|,
• pk+1l = max{0, pkl − |Mk(l)|}.
• rk+1 =∑
l∈Lpk+1l . At the end of each round, if∑
l∈Lpk+1l = 0, then all labs have reached their minimum quotas, and we can simply run GS/TTC on the remainingrk students with maximum quotas for the labs equal to (qlk+1)l∈L. If rk =∑
l∈Lpk+1l >0, then we can simply run GS/TTC on the remaining students rk students with maximum quotas for the labs equal to (pk+1l )l∈L.
Example 19 [MS-TTC] Consider the same instance of Example 18. Since the sum of the minimum quotas is ∑
l∈Lpl = 3, we temporarily remove students s3, s4, and s5 according to ML. We then run the standard TTC mechanism with no minimum quotas on students s1 and s2. At the end of this first stage, the assignments are as follows:
l1− {s1}, l2− {s2}, l3− ∅.
Thus, there are three students remaining, and l3 hasn’t yet reached its minimum quota. Accordingly, we now run TTC on s3 and s4, temporarily removing s5. At the end of this stage, the assignments are as follows:
l1− {s1}, l2− {s2, s3, s4}, l3− ∅.
Now, s5 must be assigned s5 tol3. The final matching produced by the mechanism is
l1− {s1}, l2− {s2, s3, s4}, l3− {s5}.
If the number of assigned students at each stage is always one, it is clear that MS-GS/TTC is equivalent to SD. As the number increases, MS-MS-GS/TTC is more likely to take into account the individual preferences of labs, and it eventually becomes far from SD.
We determine the number of students who must be removed in each round as the sum of the minimum quotas. This method, however, is conservative. For example, assume there are 15 students and 10 labs, whose minimum quotas are 1 and maximum quotas are 2. Then, we actually need only to remove 5 students, not 10, because no
matter how the first 10 students are allocated, the minimum quotas of at least 5 labs must be satisfied, and the remaining 5 students can fill the minimum quotas of the other 5 labs. Thus, we develop a dynamic programming based method to calculate
|Rk|, i,e., lower bounds on the number of students who must be removed in each round k in order to fulfill all the minimum quotas. We omit the details due to space constraints, but the Simulations in Section 7.5 use the optimized values for rk.
Let us discuss the properties of MS-GS and MS-TTC in turn. First, MS-GS is strategy-proof and eliminates all strong justified envy.
Theorem 44 MS-GS is strategy-proof for students.
Proof Consider a student s and fix the preferences of the other students. Let k be the round at which s is assigned if he submits his true preferences ≻s. Now, if he submits any false preferences ≻′s, he will be assigned in the same round k, with the exact same other studentsS\∪
kRk, and with the same maximum quotas for the labs (qkl)l∈L. Round k is then just GS on the set of students S\∪
kRk with quota vector (qkl)l∈L, which is strategy-proof.
Theorem 45 MS-GS eliminates all strong justified envy.
Proof Consider two students s ∈ S\∪
kRk, and s′ ∈ S \∪
k′Rk′. Assume that s envies s′. Let l = M(s) and l′ = M(s′), so that l′ ≻s l. It is clear that k ≥ k′ (if not, then s is assigned before s′, and must have applied to lab l′ and been rejected;
this means that lab l′ has reached its maximum quota by round k, and, since these assignments are permanent, s′ could not have been assigned l′ in a later round). If k = k′, both s and s′ are assigned in the same round. However, GS in round k eliminates all justified envy amongst those students assigned in roundk, and thus the envy of s is not justified. Next, when k > k′, we have s′ ≻M L s, and thus the envy of student s is again not justified.
Second, we note that MS-TTC is again strategy-proof and Pareto efficient.
Theorem 46 MS-TTC is strategy-proof.
The proof proceeds exactly as in the proof that MS-GS is strategy-proof, replacing MS-GS with MS-TTC.
Theorem 47 MS-TTC is Pareto efficient.
Proof Suppose there is some agent si who was part of the first stage of the MS-TTC mechanisms and that si did not get her first choice. If si is to be made strictly better off, she must take someone’s seat who was matched in an earlier round, and thus make this person worse off. Thus, no agent in the first stage can be part of any Pareto-improving trade. Now, if some agent sj in the second stage is to be made strictly better off, she again must make someone matched in an earlier round and/or stage strictly worse off by taking his seat. Carrying this argument through to the last stage, it is clear that MS-TTC is efficient.