B. The proofs of Proposition 1, Theorem 1, and Theorem 2
The following Lemma will be used in the rest of the proofs.
Proof
Assume for a contradiction that there is another matching \(\mu '\) Pareto dominating \(\mu \). We first claim that for some college c, \(\mu '_c\ne \mu _c\). Assume for a contradiction that \(\mu '_c=\mu _c\) for each college c. This means that for some student i with \(\mu '^C_i=\mu ^C_i=c\), either \(\mu '_i=(c,D)\) and \(\mu _i=(c,N)\) or \(\mu '_i=(c,N)\) and \(\mu _i=(c,D)\). Suppose \(\mu '_i=(c,N)\) and \(\mu _i=(c,D)\). This means that \((c,N) \mathrel {P_i} (c,D)\), contradicting our supposition. Thus, consider \(\mu '_i=(c,D)\) and \(\mu _i=(c,N)\). We have \((c,D) \mathrel {P_i} (c,N)\). By the stability (hence, non-wastefulness) of \(\mu \). we have \(|\mu ^d_c|=q^d_c\). This, as well as \(\mu _c=\mu '_c\) for each college c, implies that for some student j, we have \(\mu _j=(c,D)\) and \(\mu '_j=(c,N)\). This, however, falls into the previous case, yielding a contradiction. Thus, we conclude that \(\mu _c\ne \mu '_c\) for some college c.
Let \(i\in \mu '_c\setminus \mu _c\). Note that as \(\mu '\) Pareto dominates \(\mu \), it means that \(\mu '_c \succ _c \mu _c\). Suppose \(\mu '_i=(c,N)\). By the non-wastefulness of \(\mu \), \(|\mu _c|=q_c\). On the other hand, by the responsiveness of \(\succ _c\), for some student \(j\in \mu '_c\setminus \mu _c\), we have \(i \succ _c j\). Thus, we have \((c,N) \mathrel {P_i} \mu _i\), where \(\mu ^C_i\ne c\), and \(i \succ _c j\) for some \(j\in \mu _c\). This, however, contradicts the stability of \(\mu \). Next, suppose that \(\mu '_i=(c, D)\). As the same as above, for some student \(j\in \mu '_c\setminus \mu _c\), we have \(i \succ _c j\). If \(\mu _j=(c, D)\), then it contradicts the stability of \(\mu \). Thus, \(\mu _j=(c,N)\). If \(|\mu ^d_c|< q_c\), it constitutes a contradiction to the stability of \(\mu \). Suppose that \(|\mu ^d_c|=q_c\). This implies that there exists some student \(h\in \mu ^d_c\) such that \(\mu '_h\ne \mu _h\). Moreover, from above, \(\mu '_h\ne (c,N)\). This, along with the responsiveness, in turn, implies that for some such student \(h\in \mu ^d_c\) and \(\mu '^C_h \ne c\), we have \(i \succ _c h\). Thus, we have \((c,D) \mathrel {P_i} \mu _i\), \(i \succ _c h\), and \(\mu _h=(c,D)\), contradicting the stability of \(\mu \). Therefore, \(\mu \) is efficient, finishing the proof. \(\square \)
Proof of Theorem 1
In each step, some rejected student applies to her next best acceptable college-accommodation pair. This, along with the fact that there are finitely many students and college-accommodation types, implies that DDA terminates in a finite step. By its construction, no student receives more than one college-accommodation assignment, and no college has more students than its capacity and gives more dorms than its capacity. All these show that DDA terminates in a finite step, producing a matching; hence it is a well-defined mechanism.
Let us next show that DDA is stable. No student ever applies to her unacceptable alternatives, implying that it is individually rational. Students apply in order of their preferences. A student with a dorm demand at a college is never rejected whenever the college has an available enrollment and dorm quota. If she does not have a dorm demand, then the college never rejects her unless it already fills the quota. All these mean that DDA is non-wasteful.
Let us next show that DDA is C-fair. Let P be a problem and \(DDA(P)=\mu \). Let us consider a pair of students i, j with \(\mu ^C_i=c\) and \(\mu ^C_j=c'\) with \(c\ne c'\). Let \(j \succ _c i\). Suppose that \(\mu ^A_i=D\) and \((c,t) \mathrel {P_j} \mu _j\) for some \(t\in \{D,N\}\). This means that student j applies to either (c, D) or (c, N) in DDA. This, along with \(j \succ _c i\), means that \(\mu _j \mathrel {P_j} (c,N)\). Because otherwise, she would have received (c, N) at DDA at most at the expense of student i. Hence, we have \((c,D) \mathrel {P_j} \mu _j \mathrel {P_j} (c,N)\). This means that \(j\in D^c(P)\). On the other hand, \(j \succ _c i\); hence \(j \succ '_c i\). This, in turn, means that student j has a priority against student i in both the seat allocation at college c and its dorm assignment. This, however, contradicts our supposition.
Suppose \(\mu ^A_i=N\) and \((c,N) \mathrel {P_j} \mu _j\). In DDA, student j applies to (c, N), but is rejected. As \(j \succ _c i\) and \(\mu _i=(c,N)\), it cannot happen, yielding a contradiction.
Suppose \(\mu ^A_i=N\), \((c,D) \mathrel {P_j} \mu _j\) and \(|\mu ^d_c|< q_c\). Student j applies to (c, D) in DDA. Moreover, \(\mu _j \mathrel {P_j} (c, N)\), because, otherwise, we reach a contradiction from above (recall that \(\mu ^C_j=c'\ne c\), hence \(\mu _j\ne (c,N)\)). Thus, we have \((c,D) \mathrel {P_j} \mu _j \mathrel {P_j} (c,N)\), hence \(j\in D^c(P)\).
As \(j \succ _c i\), student j is rejected by college c because of dorm shortage. This, as well as \(j\in D^c(P)\), shows that all the tentatively dorm-receiving students at college c by the rejection of student j are more preferred to the latter by college c. Hence, in particular, they all have a better artificial ranking than student j, implying that they are all in \(D^c(P)\). On the other hand, \(|\mu ^d_c|< q^d_c\) implies that some of these students are rejected by college c for the sake of another, say k, applying to college c without a dorm demand. Thus, student k does not compete for a dorm at college c. From above, all the tentatively dorm receivers after the rejection of student j have a better ranking than student j, implying that each is preferred to student i by college c. This, as well as \(\mu _i=(c,N)\), shows that none of them is rejected for the sake of student k as they are better ranked than student i, and student k does not have a dorm demand. This implies that college c cannot have an excess dorm, contradicting \(|\mu ^d_c| < q^d_c\). Therefore, \(\mu \) is C-fair.
Let us next show that \(\mu \) is D-fair. Suppose for a pair of students i, j, we have \(\mu ^C_i=\mu ^C_j=c\) for some college c, \(\mu ^A_i=D\), \(\mu ^A_j=N\), \((c,D) \mathrel {P_j} \mu _j\), and \(j \rhd _c i\). As \((c,D) \mathrel {P_j} \mu _j=(c,N)\), student j also applies for (c, D) in DDA. Hence, both compete for a dorm. This, as well as the fact that student i obtains a dorm, shows that \(i \succ '_c j\). Thus, either \(i\in D^c(P)\) and \(j\notin D^c(P)\) or \(i \succ _c j\). This shows that \(\mu \) is D-fair. Hence, \(\mu \) is stable, so is DDA.
By the definition of
DDA, no student receives a dorm at a college unless she demands it. That is, for each student
i with
\(\mu _i=(c,D)\) for some college
c, we have
\((c,D) \mathrel {P_i} (c,N)\). Thus, we can invoke Lemma
1 to conclude that
\(\mu \) is efficient, and so is
DDA. Example
2 reveals that
DDA is not student-optimal stable.
\(\square \)
The Lemma below will be used in the proof of Theorem
2.
Proof
Let us consider Step k in SDDA. Let us suppose that \((i,c)\in N^k\) (note that \(N^k\ne \emptyset \), because, otherwise, the algorithm terminates with the final outcome of \(\mu ^{k-1}\)), and student i is rejected for her (c, D) application not earlier than any such pair in \(N^k\). This means that \(\mu ^{k-1}_i=(c,N)\), and she is rejected for her (c, D) application latest among all such pairs in the previous step’s DDA application. As she is rejected latest, she receives the same rejections in Step k’s DDA application in SDDA, showing that \(\mu ^k_i=(c,N)\). Moreover, in Step k, the rejection rule for (c, D) is relaxed. This is because in order for a student j to receive (c, D) in the previous step, she has to be ranked better than student i with respect to \(\succ '_c\). But in Step k, she can have a better ranking than student i based on \(\succ '_c\) or \(j \rhd _c i\). This, in turn, implies that no student receives an extra rejection in Step k’s DDA application compared to the previous step. Thus, for each student j, \(\mu ^k_j \mathrel {R_j} \mu ^{k-1}_j\).
Suppose \((i,k)\in N^k\), and student i is rejected for her (c, D) application latest among all such pairs in \(N^k\). From above, we have \(\mu ^k_i=(c,N)\). Suppose for a contradiction that \(\mu ^t_i\ne (c,N)\) for some \(t>k\). This means that for some \((j,c')\in N^t\), we define artificial preferences for student j, causing student i to receive a better assignment (from above, we know that students are never worse off after each step). This means that student j’s \((c',D)\) application causes a rejection cycle, placing student i at (c, N). Moreover, as it is a rejection cycle, once student i receives (c, N), someone else is rejected from (c, N), and so on. These rejections ultimately lead student j to be rejected from \((c',D)\). This shows that in Step \(k-1\), where student i’s preferences are changed in SDDA, student j is rejected from \((c',D)\) in a later step than that in which student i is rejected from (c, D). However, as j’s preferences are not changed in Step k, student j does not receive \((c',N)\) in Step \(k-1\), but in some later step. But then, this means that student j starts receiving \((c',N)\) after some student h’s preferences are changed in SDDA through removing \((c'',D)\) for some college \(c''\). By the same token as above, it means that student h is rejected for \((c'',D)\) in a later step than student j’s rejection from \((c',D)\). If student h receives \((c'',N)\) in Step t, then student j’s preferences are not changed in this step, a contradiction. Thus, student h does not receive \((c'',N)\) in Step t. Note that all the students i, j, h are different from each other, as the step in which each is rejected from her relevant college-dorm application is different. If we continue applying the same arguments above for student h, we need to find a different student in each step, which is not possible due to the finite number of students. Thus, it eventually leads to a contradiction, showing that \(\mu ^t_i=(c,N)\) for each \(t\ge k\), finishing the proof. \(\square \)
Proof of Theorem 2
Let us consider \(N^k\) in some Step k in SDDA. If it is non-empty, we consider the pairs \((i,c)\in N^k\) who are rejected for her dorm application by college c not earlier than any such pair in \(N^k\). We then define an artificial preference for student i where she reports (c, D) unacceptable. This implies that (i, c) cannot be included in \(N^{k+1}\). As both students and colleges are finite, it shows that \(N^k\) comes to be empty after some step, hence SDDA terminates in a finite time. As no student receives more than one assignment, and no college admits more students than its quota and gives more dorms than its dorm capacity in DDA (this clearly holds for the slight DDA modifications in the SDDA steps), the SDDA outcome in its terminal round is a matching. Hence, we conclude that SDDA is a well-defined mechanism.
Let us next show that
SDDA is stable. Let
P and
\(\mu \) be a problem and its outcome at
P. In each
SDDA step, students only apply to their acceptable alternatives, meaning that they would never rather be unassigned. Hence,
\(\mu \) is individually rational. Let us next show that
\(\mu \) is non-wasteful. From Theorem
1, we know that
\(\mu ^0\) is non-wasteful. Let us consider the Step 1 outcome of
SDDA,
\(\mu ^1\). We claim that
\(\mu ^1\) is non-wasteful. If
\(\mu ^1=\mu ^0\), then there is nothing to prove. Otherwise,
\(N^1\ne \emptyset \), and the preferences of some students from
\(N^1\) are changed, as defined in
SDDA. Let us suppose that student
i is one of them, and (
c,
D) is put at the very end of her preferences. Assume for a contradiction that
\(\mu ^1\) is wasteful. The rejection rules are the same as in
DDA for each college accommodation pairs except those removed from the preferences. Thus, the only possibility is the existence of a waste at some college-accommodation pair that is removed from the preferences. However, if a student
j is rejected by (
c,
D) because
\(i \succ '_c j\) and
\(i \rhd _c j\), then he cannot obtain it in
DDA as well (because
\(i \succ '_c j\) and student
i is rejected for (
c,
D)). In this case, the same rejections occur in Step 1’s
DDA as the original
DDA, causing the same matching. This, along with the non-wastefulness of
\(\mu ^0\), implies that
\(\mu ^1\) is non-wasteful. If we apply the same arguments for
\(\mu ^1\) and
\(\mu ^2\), we conclude that
\(\mu ^2\) is non-wasteful, and so on. Thus,
SDDA is non-wasteful.
Let us next show that
\(\mu \) is
C-fair. From Lemma
2, we know that if (
c,
D) is removed from the preferences of student
i, then
\(\mu _i=(c,N)\). Moreover, student
i continues to apply all the college-accommodation pairs except (
c,
D) in
SDDA. Thus, she cannot violate
C-fairness. On the other hand, all the other students whose preferences are not changed in
SDDA already apply to all alternatives in order of their preferences; thus, they do not violate
C-fairness. All these show that
\(\mu \) is
C-fair.
To show its D-fairness, let us consider a pair of students i, j such that \(\mu ^C_i=\mu ^C_j=c\), \(\mu ^A_i=D\), \(\mu ^A_j=N\), and \((c,D) \mathrel {P_j} (c,N)\). Then, by SDDA definition, either \(i \succ '_c j\) or \(i \rhd _c j\) (the latter arises if (c, D) is demoted in student j’s preferences in SDDA. Otherwise, the former is always the case). Thus, D-fairness is never violated, showing that SDDA is D-fair. Hence, SDDA is stable.
By the definition of
SDDA, no student receives a dorm at a college unless she demands it. Thus, for each student
i with
\(\mu _i=(c,D)\), we have
\((c,D) \mathrel {P_i} (c,N)\). Thus, by Lemma
1,
\(\mu \) is efficient, and so is
SDDA.
From Lemma
2,
SDDA outcome is always at least weakly better than
DDA’s for each student. We lastly show that
SDDA is student-optimal stable. Assume for a contradiction that it is not. By following above, if we write
\(\mu \) for the
SDDA outcome at problem
P, there exists another stable matching
\(\mu '\) such that for each student
i,
\(\mu '_i \mathrel {R_i} \mu _i\), where it holds strictly for some student. Let
\(W=\{i\in S:\ \mu '_i \mathrel {P_i} \mu _i\}\). By our supposition,
\(W\ne \emptyset \). Let
\(i\in W\). By the individual rationality of
\(\mu \),
\(\mu '_i\ne \emptyset \). Let us write
\(\mu '_i=(c,t)\in C\times A\). Because of the non-wastefulness of
\(\mu \), there exists another student
\(j\in W\) such that
\(\mu _j=\mu '_i=(c,t)\). For the same reason, for some student
\(k\in W\), we have
\(\mu _k=\mu '_j\). That is, for each
\(i\in W\), there exists another student
\(j\in W\) such that
\(\mu _j=\mu '_i\). That is, the students in
W are better off by trading their assignments under
\(\mu \) with each other. In other words, there are beneficial cyclic trades at
\(\mu \) among those in
W. Moreover, once we implement these trades among the students in
W, we obtain
\(\mu '\). Note that as
\(\mu '\) is at least weakly better than
\(\mu \) for the student side, for each student
\(i\notin W\), we have
\(\mu _i=\mu '_i\).
In SDDA, students apply to the college-accommodation pairs in decreasing order of their preferences. This means that the students in W apply for their assignments under \(\mu '\). However, in SDDA, students in W receive their inferior options under \(\mu \), causing the beneficial cyclic trades discussed above. Moreover, these trades are stability preserving because of the stability of \(\mu '\). This shows that the rejection rule in SDDA is more than what is needed for stability, implying that some student, say i, is rejected for (c, D) and ultimately receives (c, N). This is because, otherwise, D-fairness requires that no student j receives (c, D) whenever \(i \succ '_c j\), implying that SDDA exactly requires what is needed for stability. Thus, in SDDA, some student receives (c, N) after being rejected by (c, D) for some college c. This, however, cannot be possible as (c, D) is ranked as unacceptable in the artificial preferences of student i in SDDA. Hence, \(\mu \) is student-optimal stable, and so is SDDA.\(\square \)
C. Proofs of Proposition 2 and Proposition 3
Proof of Proposition 3
Let us consider six students \(i_1,..,i_6\) and three colleges \(c_1, c_2, c_3\). Let \(q_{c_1}=q_{c_2}=2\), and \(q_{c_3}=q^d_{c_3}=q^d_{c_1}=q^d_{c_2}=1\).
\(\begin{array}{|c|c|c|c|c|c|c|c|c|c|} \hline P_{i_1} &{} P_{i_2} &{} P_{i_3} &{} P_{i_4} &{} P_{i_5} &{} P_{i_6} &{} \succ _{c_1} &{} \succ _{c_2} &{} \succ _{c_3} &{} \rhd _{c_2}\\ \hline (c_3, N) &{} (c_2,D) &{} (c_2,D) &{} (c_2, N) &{} (c_1, D) &{} (c_1,N) &{} i_1 &{} i_6 &{} i_3 &{} i_3\\ (c_1,D) &{} (c_3, N) &{} (c_3, N) &{} \emptyset &{} \emptyset &{} (c_2, D) &{} i_5 &{} i_2 &{} i_1 &{} i_2\\ (c_1, N) &{} (c_2, N) &{} \emptyset &{} \vdots &{} \vdots &{} \emptyset &{} \vdots &{} i_3 &{} \vdots &{} \vdots \\ \emptyset &{} \emptyset &{} &{} &{} &{} &{} &{} \vdots &{} &{}\\ \hline \end{array}\)
In the problem above, DDA outcome, say \(\mu \), is such that \(\mu _{i_1}=(c_1, N)\), \(\mu _{i_2}=(c_2,N)\), \(\mu _{i_3}=(c_3,N)\), \(\mu _{i_4}=\emptyset \), \(\mu _{i_5}=(c_1,D)\), and \(\mu _{i_6}=(c_2,D)\). Let us next consider a false preferences for student \(i_1\), say \(P'_{i_1}\), where \(P'_{i_1}:\ (c_1, D), \emptyset \). It is immediate to see that \(DDA_{i_1}(P'_{i_1}, P_{-i_1})=(c_1,D)\), benefiting student \(i_1\), hence DDA is manipulable at P.
Let us next consider SDDA at P. Its outcome, say \(\mu '\), is such that \(\mu '_{i_1}=(c_3,N)\), \(\mu '_{i_2}=(c_2,N)\), \(\mu '_{i_3}=(c_2,D)\), \(\mu '_{i_4}=\emptyset \), \(\mu '_{i_5}=(c_1,D)\), and \(\mu '_{i_6}=(c_1,N)\). In SDDA, \((c_2,D)\) is removed from the preferences of student \(i_2\), causing a different matching from DDA’s to emerge (it is the only preference change done in SDDA). As \(i_1, i_3, i_5, i_6\) already obtain their top alternatives; they do not have an incentive to manipulate SDDA. On the other hand, it is easy to verify that none of the students \(i_2\) and \(i_4\) can manipulate SDDA. Hence, SDDA is not manipulable at P, whereas DDA is.
Let us next consider a problem with three students, \(i_1, i_2, i_3\), and two colleges, \(c_1, c_2\). Let \(q_{c_1}=2\), \(q_{c_2}=1\), \(q^d_{c_1}=1\), and \(q^d_{c_2}=1\). The preferences and priorities are as follows:
\(\begin{array}{|c|c|c|c|c|c|} \hline P_{i_1} &{} P_{i_2} &{} P_{i_3} &{} \succ _{c_1} &{} \succ _{c_2} &{} \rhd _{c_1}\\ \hline (c_2, N) &{} (c_1,D) &{} (c_1,D) &{} i_1 &{} i_3 &{} i_3\\ (c_1,D) &{} (c_2, N) &{} \emptyset &{} i_2 &{} i_1 &{} i_2\\ \emptyset &{} (c_1, N) &{}\vdots &{} \vdots &{} \vdots &{} \vdots \\ \hline \end{array}\)
The DDA outcome at the problem, say \(\mu \), is such that \(\mu _{i_1}=(c_2, N)\), \(\mu _{i_2}=(c_1, D)\), and \(\mu _{i_3}=\emptyset \). Student \(i_3\) cannot manipulate DDA at P, and all the others already obtain their best alternative. Hence, DDA is not manipulable at P.
Let us next consider SDDA. Its outcome at P, say \(\mu '\), is the same as \(\mu \) above. Let us consider \(P'_{i_3}: (c_1,D), (c_2, N), \emptyset \). We have \(SDDA(P'_{i_3}, P_{-i_3})=\mu ''\) where \(\mu ''_{i_1}=(c_2, N)\), \(\mu ''_{i_2}=(c_1, N)\), and \(\mu ''_{i_3}=(c_1, D)\), benefiting the misreporting student \(i_3\). Through misreporting, student \(i_3\) causes student \(i_2\) to receive \((c_1,N)\), leading SDDA to remove \((c_1,D)\) from her preferences. Thus, SDDA is manipulable at P, whereas DDA is not. This finishes the proof. \(\square \)